The geodesic farthest-point Voronoi diagram in a simple polygon

DOI10.1007/S00453-019-00651-ZMaRDI QIDQ2309478zbMATH OpenOpenAlexFDO

Authors Eunjin Oh, Luis Barba, Hee-Kap Ahn

Publication date 1 April 2020

Published in Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

simple polygonfarthest-point Voronoi diagramgeodesic metric

Mathematics Subject Classification ID

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

Abstract: Given a set of point sites in a simple polygon, the geodesic farthest-point 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(nloglogn+mlogm)$- time algorithm to compute the geodesic farthest-point Voronoi diagram of $m$ point sites in a simple $n$-gon. This improves the previously best known algorithm by Aronov et al. [Discrete Comput. Geom. 9(3):217-255, 1993]. In the case that all point sites are on the boundary of the simple polygon, we can compute the geodesic farthest-point Voronoi diagram in $O((n+m)loglogn)$ time.

Recommendations

• The farthest-point geodesic Voronoi diagram of points on the boundary of a simple polygon
• Voronoi diagrams for a moderate-sized point-set in a simple polygon
• The furthest-site geodesic Voronoi diagram
• Voronoi diagrams for a moderate-sized point-set in a simple polygon
• On the geodesic Voronoi diagram of point sites in a simple polygon

Cites work

• scientific article; zbMATH DE number 4051002 (Why is no real title available?)
• scientific article; zbMATH DE number 1555916 (Why is no real title available?)
• scientific article; zbMATH DE number 1424303 (Why is no real title available?)
• A linear-time algorithm for computing the Voronoi diagram of a convex polygon
• A linear-time algorithm for the geodesic center of a simple polygon
• Computing geodesic furthest neighbors in simple polygons
• Computing the geodesic center of a simple polygon
• Concrete and abstract Voronoi diagrams
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Matrix Searching with the Shortest-Path Metric
• Optimal shortest path queries in a simple polygon
• Ray shooting in polygons using geodesic triangulations
• The farthest-point geodesic Voronoi diagram of points on the boundary of a simple polygon
• The furthest-site geodesic Voronoi diagram
• Voronoi diagrams for a moderate-sized point-set in a simple polygon
• k-PAIRS NON-CROSSING SHORTEST PATHS IN A SIMPLE POLYGON

Cited in

(19)

• The furthest-site geodesic Voronoi diagram
• Geodesic Fréchet distance inside a simple polygon
• Optimal algorithm for geodesic nearest-point Voronoi diagrams in simple polygons
• Farthest-polygon Voronoi diagrams
• The farthest-point geodesic Voronoi diagram of points on the boundary of a simple polygon
• On the geodesic Voronoi diagram of point sites in a simple polygon
• An optimal deterministic algorithm for geodesic farthest-point Voronoi diagrams in simple polygons
• Computing geodesic furthest neighbors in simple polygons
• Voronoi diagrams for a moderate-sized point-set in a simple polygon
• Voronoi diagrams for a moderate-sized point-set in a simple polygon
• Euclidean farthest-point Voronoi diagram of a digital edge
• On the Farthest Line-Segment Voronoi Diagram
• The geodesic edge center of a simple polygon
• Farthest-Polygon Voronoi Diagrams
• Farthest-point Voronoi diagrams in the presence of rectangular obstacles
• A coreset for approximate furthest-neighbor queries in a simple polygon
• The geodesic farthest-site Voronoi diagram in a polygonal domain with holes
• Farthest-point Voronoi diagrams in the presence of rectangular obstacles
• An optimal deterministic algorithm for geodesic farthest-point Voronoi diagrams in simple polygons

This page was built for publication: The geodesic farthest-point Voronoi diagram in a simple polygon

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