2026-07-22T18:45:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5948 2024-03-06T10:37:20Z ddc:004 open_access

The Farthest-Point Geodesic Voronoi Diagram of Points on the Boundary of a Simple Polygon Oh, Eunjin Barba, Luis Ahn, Hee-Kap Geodesic distance simple polygons farthest-point Voronoi diagram Given a set of sites (points) in a simple polygon, the farthest-point geodesic Voronoi diagram partitions the polygon into cells, at most one cell per site, such that every point in a cell has the same farthest site with respect to the geodesic metric. We present an O((n+m)loglogn)-time algorithm to compute the farthest-point geodesic Voronoi diagram for m sites lying on the boundary of a simple n-gon. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eunjin Oh and Luis Barba and Hee-Kap Ahn 2016 Is Part Of LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2016.56 urn:nbn:de:0030-drops-59481 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.56 eng https://creativecommons.org/licenses/by/3.0/legalcode