Voronoi diagrams for a moderate-sized point-set in a simple polygon

DOI10.1007/s00454-019-00063-4zbMath1432.68525OpenAlexW2966785732WikidataQ128303361 ScholiaQ128303361MaRDI QIDQ2291454

Hee-Kap Ahn, Eunjin Oh

Publication date: 31 January 2020

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

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/7218/

zbMATH Keywords

simple polygonsVoronoi diagramsgeodesic distance

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Tilings in (2) dimensions (aspects of discrete geometry) (52C20)

Related Items (6)

Kinetic Geodesic Voronoi Diagrams in a Simple Polygon ⋮ Dynamic data structures for \(k\)-nearest neighbor queries ⋮ An optimal deterministic algorithm for geodesic farthest-point Voronoi diagrams in simple polygons ⋮ Farthest-point Voronoi diagrams in the presence of rectangular obstacles ⋮ Approximating the smallest \(k\)-enclosing geodesic disc in a simple polygon ⋮ Piercing pairwise intersecting geodesic disks

Cites Work

• 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 sweepline algorithm for Voronoi diagrams
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• On the geodesic Voronoi diagram of point sites in a simple polygon
• 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
• Optimal shortest path queries in a simple polygon
• The farthest-point geodesic Voronoi diagram of points on the boundary of a simple polygon
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• Decomposable searching problems I. Static-to-dynamic transformation
• Higher-Order Geodesic Voronoi Diagrams in a Polygonal Domain with Holes

This page was built for publication: Voronoi diagrams for a moderate-sized point-set in a simple polygon