Physical Sciences and Mathematics Commons^™

An Optimal Deterministic Algorithm For Geodesic Farthest-Point Voronoi Diagrams In Simple Polygons, Haitao Wang

Computer Science Faculty and Staff Publications

Given a set S of m point sites in a simple polygon P of n vertices, we consider the problem of computing the geodesic farthest-point Voronoi diagram for S in P. It is known that the problem has an Ω(n + m log m) time lower bound. Previously, a randomized algorithm was proposed [Barba, SoCG 2019] that can solve the problem in O(n + m log m) expected time. The previous best deterministic algorithms solve the problem in O(n log log n + m log m) time [Oh, Barba, and Ahn, …