2026-08-07T04:46:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10416 2024-03-06T10:45:56Z ddc:004 open_access

Optimal Algorithm for Geodesic Farthest-Point Voronoi Diagrams Barba, Luis Geodesic distance simple polygons farthest-point Voronoi diagram Let P be a simple polygon with n vertices. For any two points in P, the geodesic distance between them is the length of the shortest path that connects them among all paths contained in P. Given a set S of m sites being a subset of the vertices of P, we present the first randomized algorithm to compute the geodesic farthest-point Voronoi diagram of S in P running in expected O(n + m) time. That is, a partition of P 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 distance. This algorithm can be extended to run in expected O(n + m log m) time when S is an arbitrary set of m sites contained in P. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Luis Barba 2019 Is Part Of LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2019.12 urn:nbn:de:0030-drops-104161 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.12 eng https://creativecommons.org/licenses/by/3.0/legalcode