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

DOI10.1007/s00454-022-00424-6arXiv2103.00076OpenAlexW4294232669WikidataQ114229287 ScholiaQ114229287MaRDI QIDQ6174809

No author found.

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

zbMATH Keywords

simple polygonsshortest pathsVoronoi diagramsgeodesic distancefarthest 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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The geodesic diameter of polygonal domains
• Computing the geodesic center of a simple polygon
• A linear-time algorithm for the geodesic center of a simple polygon
• On the geodesic Voronoi diagram of point sites in a simple polygon
• On the \(\Omega (n\log n)\) lower bound for convex hull and maximal vector determination
• On the complexity of finding the convex hull of a set of points
• A new data structure for shortest path queries in a simple polygon
• The furthest-site geodesic Voronoi diagram
• 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
• Optimal shortest path queries in a simple polygon
• Voronoi diagrams for a moderate-sized point-set in a simple polygon
• A nearly optimal algorithm for the geodesic Voronoi diagram of points in a simple polygon
• The geodesic farthest-point Voronoi diagram in a simple polygon
• A Lower Bound to Finding Convex Hulls
• An Optimal Algorithm for Euclidean Shortest Paths in the Plane
• Matrix Searching with the Shortest-Path Metric
• Optimal Algorithm for Geodesic Nearest-point Voronoi Diagrams in Simple Polygons
• The geodesic farthest-site Voronoi diagram in a polygonal domain with holes

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