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

DOI10.1007/S00454-022-00424-6MaRDI QIDQ6174809zbMATH OpenOpenAlexWikidataFDO

Authors

Publication date 17 August 2023

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

Full work available at URL https://arxiv.org/abs/2103.00076, https://digitalcommons.usu.edu/computer_science_facpubs/21

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)

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.

Cites work

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

Cited in

(6)

• Maximizing Voronoi regions of a set of points enclosed in a circle with applications to facility location
• scientific article; zbMATH DE number 140459 (Why is no real title available?)
• The optimal algorithm for dynamic support of the Voronoi Diagram for a set of points
• The geodesic edge center of a simple polygon
• scientific article; zbMATH DE number 3889235 (Why is no real title available?)
• A coreset for approximate furthest-neighbor queries in a simple polygon

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)