On the geodesic Voronoi diagram of point sites in a simple polygon

DOI10.1007/BF01553882zbMath0664.68043OpenAlexW2009218627MaRDI QIDQ1115602

Boris Aronov

Publication date: 1989

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01553882

zbMATH Keywords

Voronoi diagramshortest pathscomputational geometrysimple polygongeodesic metric

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computing methodologies and applications (68U99) Convex sets in (2) dimensions (including convex curves) (52A10) Variants of convex sets (star-shaped, ((m, n))-convex, etc.) (52A30)

Related Items (25)

A new algorithm for shortest paths among obstacles in the plane ⋮ Boat-sail Voronoi diagram on a curved surface ⋮ Efficient piecewise-linear function approximation using the uniform metric ⋮ Stable marker-particle method for the Voronoi diagram in a flow field ⋮ A note on visibility-constrained Voronoi diagrams ⋮ Kinetic Geodesic Voronoi Diagrams in a Simple Polygon ⋮ Efficient computation of the geodesic Voronoi diagram of points in a simple polygon ⋮ 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 ⋮ SEPARATING POINT SETS IN POLYGONAL ENVIRONMENTS ⋮ Proximity problems for points on a rectilinear plane with rectangular obstacles ⋮ GEODESIC DISKS AND CLUSTERING IN A SIMPLE POLYGON ⋮ Computing the \(L_1\) geodesic diameter and center of a polygonal domain ⋮ The furthest-site geodesic Voronoi diagram ⋮ Unnamed Item ⋮ A linear-time algorithm for the geodesic center of a simple polygon ⋮ Voronoi diagrams for a moderate-sized point-set in a simple polygon ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A nearly optimal algorithm for the geodesic Voronoi diagram of points in a simple polygon ⋮ On determining optimal strategies in pursuit games in the plane ⋮ BOAT-SAIL VORONOI DIAGRAM AND ITS APPLICATION ⋮ Boat-sail Voronoi diagram and its computation based on a cone-approximation scheme ⋮ Polygon Area Decomposition for Multiple-Robot Workspace Division

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing the geodesic center of a simple polygon
• An optimal algorithm for constructing the weighted Voronoi diagram in the plane
• Generalized Delaunay triangulation for planar graphs
• Voronoi diagrams and arrangements
• An O(n log n) algorithm for the Voronoi diagram of a set of simple curve segments
• Generalized Voronoi diagrams for a ladder. II: Efficient construction of the diagram
• A sweepline algorithm for Voronoi diagrams
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Computing the link center of a simple polygon
• Constrained Delaunay triangulations
• The furthest-site geodesic Voronoi diagram
• Triangulating a simple polygon
• Voronoi Diagram in the Laguerre Geometry and Its Applications
• Euclidean shortest paths in the presence of rectilinear barriers
• Generalized voronoi diagrams for moving a ladder. I: Topological analysis
• An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon
• On the shortest paths between two convex polyhedra
• Two-Dimensional Voronoi Diagrams in the L _p -Metric
• Voronoui Diagrams in $L_1 (L_\infty )$ Metrics with 2-Dimensional Storage Applications
• Power Diagrams: Properties, Algorithms and Applications

This page was built for publication: On the geodesic Voronoi diagram of point sites in a simple polygon