On the geodesic Voronoi diagram of point sites in a simple polygon
type: Item
instance of: scholarly article
title: On the geodesic Voronoi diagram of point sites in a simple polygon
zbMATH Open document ID: 0664.68043
DOI: 10.1007/BF01553882
author: Boris Aronov
published in: Algorithmica
publication date: 1989-01-01T00:00:00Z
review text: Given a simple polygon with n sides in the plane and a set of k point ``sites'' in its interior or on the boundary, compute the Voronoi diagram of the set of sites using the internal ``geodesic'' distance inside the polygon as the metric. We describe an \(O((n+k)\log (n+k)\log n)-time\) algorithm for solving this problem and sketch a faster \(O((n+k)\log (n+k))\) algorithm for the case when the set of sites includes all reflex vertices of the polygon in question.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 52A10
Mathematics Subject Classification ID: 52A30
Mathematics Subject Classification ID: 68U99
zbMATH DE Number: 4087016
zbMATH Keywords: computational geometry
zbMATH Keywords: geodesic metric
zbMATH Keywords: shortest paths
zbMATH Keywords: simple polygon
zbMATH Keywords: Voronoi diagram
MaRDI profile type: Publication
cites work: Power Diagrams: Properties, Algorithms and Applications
cites work: Q3787490
cites work: An optimal algorithm for constructing the weighted Voronoi diagram in the plane
cites work: The furthest-site geodesic Voronoi diagram
cites work: On the shortest paths between two convex polyhedra
cites work: Constrained Delaunay triangulations
cites work: Voronoi diagrams and arrangements
cites work: A sweepline algorithm for Voronoi diagrams
cites work: Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
cites work: Triangulating a simple polygon
cites work: Voronoi Diagram in the Laguerre Geometry and Its Applications
cites work: Two-Dimensional Voronoi Diagrams in the L p -Metric
cites work: Computing the link center of a simple polygon
cites work: Generalized Delaunay triangulation for planar graphs
cites work: Euclidean shortest paths in the presence of rectilinear barriers
cites work: Q3479543
cites work: Voronoui Diagrams in $L_1 (L_\infty )$ Metrics with 2-Dimensional Storage Applications
cites work: Generalized voronoi diagrams for moving a ladder. I: Topological analysis
cites work: Generalized Voronoi diagrams for a ladder. II: Efficient construction of the diagram
cites work: Q3992847
cites work: Computing the geodesic center of a simple polygon
cites work: An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon
cites work: An O(n log n) algorithm for the Voronoi diagram of a set of simple curve segments
full work available at URL: https://doi.org/10.1007/bf01553882
OpenAlex ID: W2009218627
description: scientific article; zbMATH DE number 4087016