Y.Y. Li, K.S. Leung, et al.
J Combin Optim
We introduce a new method for computing the geodesic Voronoi diagram of point sites in a simple polygon and other restricted polygonal domains. Our method combines a sweep of the polygonal domain with the merging step of a usual divide-and-conquer algorithm. The time complexity is O((n+k) log(n+K)) where n is the number of vertices and k is the number of points, improving upon previously known bounds. Space is O(n+K). Other polygonal domains where our method is applicable include (among others) a polygonal domain of parallel disjoint line segments and a polygonal domain of rectangles in the L1 metric. © 1998 Springer-Verlag New York Inc.
Y.Y. Li, K.S. Leung, et al.
J Combin Optim
Minghong Fang, Zifan Zhang, et al.
CCS 2024
Charles Micchelli
Journal of Approximation Theory
Jonathan Ashley, Brian Marcus, et al.
Ergodic Theory and Dynamical Systems