The geodesic farthest-point Voronoi diagram in a simple polygon

DOI10.1007/s00453-019-00651-zzbMath1433.68499arXiv1802.06223OpenAlexW2983120862MaRDI QIDQ2309478

Eunjin Oh, Hee-Kap Ahn, Luis Barba

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)

Related Items (2)

An optimal deterministic algorithm for geodesic farthest-point Voronoi diagrams in simple polygons ⋮ Farthest-point Voronoi diagrams in the presence of rectangular obstacles

Cites Work

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

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