The geodesic farthest-point Voronoi diagram in a simple polygon

DOI10.1007/S00453-019-00651-ZzbMATH Open1433.68499arXiv1802.06223OpenAlexW2983120862MaRDI QIDQ2309478FDOQ2309478

Authors: Eunjin Oh, Luis Barba, Hee-Kap Ahn 

Publication date: 1 April 2020

Published in: Algorithmica (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

Cited In (16)

• The furthest-site geodesic Voronoi diagram
• Optimal algorithm for geodesic nearest-point Voronoi diagrams in simple polygons
• Geodesic Fréchet distance inside a simple polygon
• 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
• 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
• Farthest-Polygon Voronoi Diagrams
• Farthest-point Voronoi diagrams in the presence of rectangular obstacles
• 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)