An optimal deterministic algorithm for geodesic farthest-point Voronoi diagrams in simple polygons

DOI10.1007/S00454-022-00424-6arXiv2103.00076OpenAlexW4294232669WikidataQ114229287 ScholiaQ114229287MaRDI QIDQ6174809FDOQ6174809

Authors:

Publication date: 17 August 2023

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Abstract: 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 $Omega(n+mlogm)$ time lower bound. Previously, a randomized algorithm was proposed [Barba, SoCG 2019] that can solve the problem in $O(n+mlogm)$ expected time. The previous best deterministic algorithms solve the problem in $O(nloglogn+mlogm)$ time [Oh, Barba, and Ahn, SoCG 2016] or in $O(n+mlogm+mlo{g}^{2}n)$ time [Oh and Ahn, SoCG 2017]. In this paper, we present a deterministic algorithm of $O(n+mlogm)$ time, which is optimal. This answers an open question posed by Mitchell in the Handbook of Computational Geometry two decades ago.

Full work available at URL: https://arxiv.org/abs/2103.00076

zbMATH Keywords

shortest pathsVoronoi diagramsgeodesic distancesimple polygonsfarthest sites

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• An Optimal Algorithm for Euclidean Shortest Paths in the Plane
• The furthest-site geodesic Voronoi diagram
• Optimal shortest path queries in a simple polygon
• The geodesic diameter of polygonal domains
• Title not available (Why is that?)
• Matrix Searching with the Shortest-Path Metric
• The geodesic farthest-site Voronoi diagram in a polygonal domain with holes
• Computing the geodesic center of a simple polygon
• On the geodesic Voronoi diagram of point sites in a simple polygon
• Ray shooting in polygons using geodesic triangulations
• A new approach for the geodesic Voronoi diagram of points in a simple polygon and other restricted polygonal domains
• Computing the geodesic centers of a polygonal domain
• Computing geodesic furthest neighbors in simple polygons
• A Lower Bound to Finding Convex Hulls
• A linear-time algorithm for the geodesic center of a simple polygon
• The geodesic farthest-point Voronoi diagram in a simple polygon
• A nearly optimal algorithm for the geodesic Voronoi diagram of points in a simple polygon
• Optimal algorithm for geodesic nearest-point Voronoi diagrams in simple polygons
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the \(\Omega (n\log n)\) lower bound for convex hull and maximal vector determination
• A new data structure for shortest path queries in a simple polygon
• On the complexity of finding the convex hull of a set of points
• Title not available (Why is that?)
• Voronoi diagrams for a moderate-sized point-set in a simple polygon

Cited In (4)

• Maximizing Voronoi regions of a set of points enclosed in a circle with applications to facility location
• Title not available (Why is that?)
• The optimal algorithm for dynamic support of the Voronoi Diagram for a set of points
• Title not available (Why is that?)

This page was built for publication: An optimal deterministic algorithm for geodesic farthest-point Voronoi diagrams in simple polygons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6174809)