[{"publication":"IEEE Transactions on Computers","language":[{"iso":"eng"}],"intvolume":"        36","scopus_import":"1","issue":"11","article_processing_charge":"No","date_updated":"2022-02-04T10:32:27Z","title":"An improved algorithm for constructing kth-order Voronoi diagrams","status":"public","type":"journal_article","month":"11","publication_identifier":{"issn":["0018-9340"],"eissn":["1557-9956"]},"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","main_file_link":[{"url":"https://ieeexplore.ieee.org/document/5009474"}],"day":"01","oa_version":"None","author":[{"first_name":"Bernard","full_name":"Chazelle, Bernard","last_name":"Chazelle"},{"orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","first_name":"Herbert","full_name":"Edelsbrunner, Herbert"}],"doi":"10.1109/TC.1987.5009474","article_type":"original","_id":"4095","year":"1987","acknowledgement":"We would like to thank two anonymous referees for their constructive criticism. ","citation":{"apa":"Chazelle, B., &#38; Edelsbrunner, H. (1987). An improved algorithm for constructing kth-order Voronoi diagrams. <i>IEEE Transactions on Computers</i>. IEEE. <a href=\"https://doi.org/10.1109/TC.1987.5009474\">https://doi.org/10.1109/TC.1987.5009474</a>","ista":"Chazelle B, Edelsbrunner H. 1987. An improved algorithm for constructing kth-order Voronoi diagrams. IEEE Transactions on Computers. 36(11), 1349–1354.","chicago":"Chazelle, Bernard, and Herbert Edelsbrunner. “An Improved Algorithm for Constructing Kth-Order Voronoi Diagrams.” <i>IEEE Transactions on Computers</i>. IEEE, 1987. <a href=\"https://doi.org/10.1109/TC.1987.5009474\">https://doi.org/10.1109/TC.1987.5009474</a>.","mla":"Chazelle, Bernard, and Herbert Edelsbrunner. “An Improved Algorithm for Constructing Kth-Order Voronoi Diagrams.” <i>IEEE Transactions on Computers</i>, vol. 36, no. 11, IEEE, 1987, pp. 1349–54, doi:<a href=\"https://doi.org/10.1109/TC.1987.5009474\">10.1109/TC.1987.5009474</a>.","ama":"Chazelle B, Edelsbrunner H. An improved algorithm for constructing kth-order Voronoi diagrams. <i>IEEE Transactions on Computers</i>. 1987;36(11):1349-1354. doi:<a href=\"https://doi.org/10.1109/TC.1987.5009474\">10.1109/TC.1987.5009474</a>","ieee":"B. Chazelle and H. Edelsbrunner, “An improved algorithm for constructing kth-order Voronoi diagrams,” <i>IEEE Transactions on Computers</i>, vol. 36, no. 11. IEEE, pp. 1349–1354, 1987.","short":"B. Chazelle, H. Edelsbrunner, IEEE Transactions on Computers 36 (1987) 1349–1354."},"date_created":"2018-12-11T12:06:54Z","publist_id":"2026","date_published":"1987-11-01T00:00:00Z","publisher":"IEEE","volume":36,"quality_controlled":"1","page":"1349 - 1354","extern":"1","abstract":[{"text":"he kth-order Voronoi diagram of a finite set of sites in the Euclidean plane E2 subdivides E2 into maximal regions such that all points within a given region have the same k nearest sites. Two versions of an algorithm are developed for constructing the kth-order Voronoi diagram of a set of n sites in O(n2 log n + k(n - k) log2 n) time, O(k(n - k)) storage, and in O(n2 + k(n - k) log2 n) time, O(n2) storage, respectively.","lang":"eng"}],"publication_status":"published"}]