CONSTRUCTING THE CITY VORONOI DIAGRAM FASTER
- 1 August 2008
- journal article
- research article
- Published by World Scientific Pub Co Pte Ltd in International Journal of Computational Geometry & Applications
- Vol. 18 (04) , 275-294
Abstract
Given a set P of n point sites in the plane, the city Voronoi diagram subdivides the plane into the Voronoi regions of the sites, with respect to the city metric. This metric is induced by quickest paths according to the Manhattan metric and an accelerating transportation network that consists of c non-intersecting axis-parallel line segments. We describe an algorithm that constructs the city Voronoi diagram (including quickest path information) using O((c+n) polylog (c+n)) time and storage by means of a wavefront expansion. For [Formula: see text] our algorithm is faster than an algorithm by Aichholzer et al., which takes O(n log n + c2 log c) time.Keywords
This publication has 11 references indexed in Scilit:
- Computational Geometry2008
- Shortest Paths and Voronoi Diagrams with Transportation Networks Under General Distances2005
- Quickest Paths, Straight Skeletons, and the City Voronoi DiagramDiscrete & Computational Geometry, 2003
- Voronoi Diagram for services neighboring a highwayInformation Processing Letters, 2003
- Deformable Free-Space Tilings for Kinetic Collision Detection†The International Journal of Robotics Research, 2002
- Raising Roofs, Crashing Cycles, and Playing Pool: Applications of a Data Structure for Finding Pairwise InteractionsDiscrete & Computational Geometry, 1999
- Ray Shooting, Depth Orders and Hidden Surface Removal1993
- The weighted region problemJournal of the ACM, 1991
- Path Planning in 0/1/∞ Weighted Regions with ApplicationsINFORMS Journal on Computing, 1990
- The Discrete Geodesic ProblemSIAM Journal on Computing, 1987