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 trans- portation 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 $c Ømega(n łog^3 n)$ our algorithm is faster than an algorithm by Aichholzer et al., which takes $O(n n + c^2 c)$ time.
%0 Journal Article
%1 gsw-ccvdf-08
%A Görke, Robert
%A Shin, Chan-Su
%A Wolff, Alexander
%D 2008
%J #IJCGA#
%K wavefrontexpansion transportationnetwork cityVoronoidiagram minimizationquery straightskeleton closestpair
%N 4
%P 275--294
%R 10.1142/S0218195908002623
%T Constructing the City Voronoi Diagram Faster
%U http://dx.doi.org/10.1142/S0218195908002623
%V 18
%X 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 trans- portation 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 $c Ømega(n łog^3 n)$ our algorithm is faster than an algorithm by Aichholzer et al., which takes $O(n n + c^2 c)$ time.
@article{gsw-ccvdf-08,
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 trans- portation 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 $c \in \Omega(\sqrt{n} \log^3 n)$ our algorithm is faster than an algorithm by Aichholzer et al., which takes $O(n \log n + c^2 \log c)$ time.},
added-at = {2010-04-13T09:41:27.000+0200},
author = {G{\"o}rke, Robert and Shin, Chan-Su and Wolff, Alexander},
biburl = {https://www.bibsonomy.org/bibtex/21c397c2ad43437338963f88d397d285f/fink},
doi = {10.1142/S0218195908002623},
interhash = {d76dfcee4f008b1005af7400d7707e8e},
intrahash = {1c397c2ad43437338963f88d397d285f},
journal = {#IJCGA#},
keywords = {wavefrontexpansion transportationnetwork cityVoronoidiagram minimizationquery straightskeleton closestpair},
number = 4,
pages = {275--294},
pdf = {#AWPUBURL#gsw-ccvdf-08.pdf},
succeeds = {gw-ccvdf-05},
timestamp = {2010-04-13T09:41:27.000+0200},
title = {Constructing the City {Voronoi} Diagram Faster},
url = {http://dx.doi.org/10.1142/S0218195908002623},
volume = 18,
year = 2008
}