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-IJCGA08
%A Görke, Robert
%A Shin, Chan-Su
%A Wolff, Alexander
%D 2008
%J International Journal of Computational Geometry and Applications
%K city_Voronoi_diagram closest_pair minimization_query myown straight_skeleton transportation_network wavefront_expansion
%N 4
%P 275--294
%R 10.1142/S0218195908002623
%T Constructing the City Voronoi Diagram Faster
%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-IJCGA08,
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 = {2024-02-18T09:53:56.000+0100},
author = {G{\"o}rke, Robert and Shin, Chan-Su and Wolff, Alexander},
biburl = {https://www.bibsonomy.org/bibtex/260b4d246d7cb7644986b87f6cbb43c13/awolff},
doi = {10.1142/S0218195908002623},
interhash = {d76dfcee4f008b1005af7400d7707e8e},
intrahash = {60b4d246d7cb7644986b87f6cbb43c13},
journal = {International Journal of Computational Geometry and Applications},
keywords = {city_Voronoi_diagram closest_pair minimization_query myown straight_skeleton transportation_network wavefront_expansion},
number = 4,
pages = {275--294},
pdf = {http://www1.pub.informatik.uni-wuerzburg.de/pub/wolff/pub/gsw-ccvdf-08.pdf},
succeeds = {gw-ccvdf-05},
timestamp = {2024-02-18T12:36:59.000+0100},
title = {Constructing the City {Voronoi} Diagram Faster},
volume = 18,
year = 2008
}