2026-07-23T21:43:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13858 2024-03-06T10:52:54Z ddc:004 open_access

An Optimal Deterministic Algorithm for Geodesic Farthest-Point Voronoi Diagrams in Simple Polygons Wang, Haitao farthest-sites Voronoi diagrams triple-point geodesic center simple polygons 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+mlog m) time lower bound. Previously, a randomized algorithm was proposed [Barba, SoCG 2019] that can solve the problem in O(n+mlog m) expected time. The previous best deterministic algorithms solve the problem in O(nlog log n+ mlog m) time [Oh, Barba, and Ahn, SoCG 2016] or in O(n+mlog m+mlog² n) time [Oh and Ahn, SoCG 2017]. In this paper, we present a deterministic algorithm of O(n+mlog m) time, which is optimal. This answers an open question posed by Mitchell in the Handbook of Computational Geometry two decades ago. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Haitao Wang 2021 Is Part Of LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2021.59 urn:nbn:de:0030-drops-138585 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.59 eng https://creativecommons.org/licenses/by/4.0/legalcode