Abstract Voronoi Diagrams from Closed Bisecting Curves

Bohler CKlein RCHIH-HUNG LIU2022-11-112022-11-11201702181959https://www.scopus.com/inward/record.uri?eid=2-s2.0-85041167749&doi=10.1142%2fS0218195917500054&partnerID=40&md5=28724545dc3f4dfc0e4ba1b73087a1abhttps://scholars.lib.ntu.edu.tw/handle/123456789/624643We present the first algorithm for constructing abstract Voronoi diagrams from bisectors that are unbounded or closed Jordan curves. It runs in expected O(s2nlog(max{s,n}) σni=2nm i/i) many steps and O(σni=3nm i) space, where n is the number of sites, mi denotes the average number of faces (connected components) per Voronoi region in any diagram of a subset of i sites, and s is the maximum number of intersection points between any two related bisectors. © 2017 World Scientific Publishing Company.Abstract Voronoi diagrams; closed bisecting curves; computational geometry; distance problems; Voronoi diagramsAbstract Voronoi Diagrams from Closed Bisecting Curvesjournal article10.1142/S02181959175000542-s2.0-85041167749