{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,24]],"date-time":"2025-07-24T11:50:53Z","timestamp":1753357853704},"reference-count":17,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2015,6]]},"abstract":"<jats:p> We revisit the [Formula: see text] Hausdorff Voronoi diagram of clusters of points in the plane and present a simple two-pass plane sweep algorithm to construct it. This problem is motivated by applications in the semiconductor industry, in particular, critical area analysis and yield prediction in VLSI design. We show that the structural complexity of this diagram is [Formula: see text], where [Formula: see text] is the number of given clusters and [Formula: see text] is a number of specially crossing clusters, called essential. Our algorithm runs in [Formula: see text] time and [Formula: see text] space, where [Formula: see text] reflects a slight superset of essential crossings, [Formula: see text], and [Formula: see text] is the total number of crossing clusters. For non-crossing clusters ([Formula: see text]) or clusters with only a small number of crossings ([Formula: see text]) the algorithm is optimal. The latter is the case of interest in the motivating application, where [Formula: see text]. This is achieved by augmenting the wavefront data structure of the plane sweep, and a preprocessing step, based on point dominance, which is interesting in its own right. <\/jats:p>","DOI":"10.1142\/s0218195915500089","type":"journal-article","created":{"date-parts":[[2015,7,21]],"date-time":"2015-07-21T02:06:51Z","timestamp":1437444411000},"page":"123-141","source":"Crossref","is-referenced-by-count":4,"title":["The L\u221e Hausdorff Voronoi Diagram Revisited"],"prefix":"10.1142","volume":"25","author":[{"given":"Evanthia","family":"Papadopoulou","sequence":"first","affiliation":[{"name":"Faculty of Informatics, USI - Universit\u00e0 della Svizzera, italiana Lugano, Switzerland"}]},{"given":"Jinhui","family":"Xu","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, State University of New York at Buffalo, USA"}]}],"member":"219","published-online":{"date-parts":[[2015,7,20]]},"reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009296"},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2010.11.004"},{"key":"p_6","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523236"},{"key":"p_8","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187733"},{"key":"p_9","doi-asserted-by":"publisher","DOI":"10.1007\/BF02189323"},{"key":"p_10","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840357"},{"key":"p_12","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2009.03.002"},{"key":"p_13","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(93)90033-3"},{"key":"p_14","doi-asserted-by":"publisher","DOI":"10.1137\/0214021"},{"key":"p_16","doi-asserted-by":"publisher","DOI":"10.1109\/43.920683"},{"key":"p_17","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1095-0"},{"key":"p_18","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2010.2100550"},{"key":"p_19","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195913600121"},{"key":"p_20","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195901000626"},{"key":"p_21","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195904001536"},{"key":"p_24","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00179-4"},{"key":"p_25","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9704-9"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195915500089","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T23:48:57Z","timestamp":1565135337000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195915500089"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6]]},"references-count":17,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2015,7,20]]},"published-print":{"date-parts":[[2015,6]]}},"alternative-id":["10.1142\/S0218195915500089"],"URL":"https:\/\/doi.org\/10.1142\/s0218195915500089","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,6]]}}}