[{"acknowledgement":"The second author gratefully acknowledges discussions on the presented topic with David Kirkpatrick and Raimund Seidel.","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","oa_version":"None","quality_controlled":"1","_id":"4125","publication_identifier":{"issn":["0031-3203"],"eissn":["1873-5142"]},"extern":"1","publist_id":"1997","date_updated":"2022-01-27T14:06:27Z","volume":17,"article_processing_charge":"No","author":[{"last_name":"Aurenhammer","full_name":"Aurenhammer, Franz","first_name":"Franz"},{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert","last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833","first_name":"Herbert"}],"abstract":[{"lang":"eng","text":"Let S denote a set of n points in the plane such that each point p has assigned a positive weight w(p) which expresses its capability to influence its neighbourhood. In this sense, the weighted distance of an arbitrary point x from p is given by de(x,p)/w(p) where de denotes the Euclidean distance function. The weighted Voronoi diagram for S is a subdivision of the plane such that each point p in S is associated with a region consisting of all points x in the plane for which p is a weighted nearest point of S.\r\n\r\nAn algorithm which constructs the weighted Voronoi diagram for S in O(n2) time is outlined in this paper. The method is optimal as the diagram can consist of Θ(n2) faces, edges and vertices.\r\n"}],"publication_status":"published","citation":{"mla":"Aurenhammer, Franz, and Herbert Edelsbrunner. “An Optimal Algorithm for Constructing the Weighted Voronoi Diagram in the Plane.” <i>Pattern Recognition</i>, vol. 17, no. 2, Elsevier, 1983, pp. 251–57, doi:<a href=\"https://doi.org/10.1016/0031-3203(84)90064-5\">10.1016/0031-3203(84)90064-5</a>.","ama":"Aurenhammer F, Edelsbrunner H. An optimal algorithm for constructing the weighted Voronoi diagram in the plane. <i>Pattern Recognition</i>. 1983;17(2):251-257. doi:<a href=\"https://doi.org/10.1016/0031-3203(84)90064-5\">10.1016/0031-3203(84)90064-5</a>","short":"F. Aurenhammer, H. Edelsbrunner, Pattern Recognition 17 (1983) 251–257.","ista":"Aurenhammer F, Edelsbrunner H. 1983. An optimal algorithm for constructing the weighted Voronoi diagram in the plane. Pattern Recognition. 17(2), 251–257.","ieee":"F. Aurenhammer and H. Edelsbrunner, “An optimal algorithm for constructing the weighted Voronoi diagram in the plane,” <i>Pattern Recognition</i>, vol. 17, no. 2. Elsevier, pp. 251–257, 1983.","apa":"Aurenhammer, F., &#38; Edelsbrunner, H. (1983). An optimal algorithm for constructing the weighted Voronoi diagram in the plane. <i>Pattern Recognition</i>. Elsevier. <a href=\"https://doi.org/10.1016/0031-3203(84)90064-5\">https://doi.org/10.1016/0031-3203(84)90064-5</a>","chicago":"Aurenhammer, Franz, and Herbert Edelsbrunner. “An Optimal Algorithm for Constructing the Weighted Voronoi Diagram in the Plane.” <i>Pattern Recognition</i>. Elsevier, 1983. <a href=\"https://doi.org/10.1016/0031-3203(84)90064-5\">https://doi.org/10.1016/0031-3203(84)90064-5</a>."},"main_file_link":[{"url":"https://www.sciencedirect.com/science/article/pii/0031320384900645?via%3Dihub"}],"title":"An optimal algorithm for constructing the weighted Voronoi diagram in the plane","year":"1983","doi":"10.1016/0031-3203(84)90064-5","page":"251 - 257","issue":"2","publication":"Pattern Recognition","status":"public","intvolume":"        17","type":"journal_article","day":"01","date_created":"2018-12-11T12:07:05Z","language":[{"iso":"eng"}],"publisher":"Elsevier","scopus_import":"1","article_type":"original","date_published":"1983-07-01T00:00:00Z","month":"07"}]