Higher Order City Voronoi Diagrams

Details Higher Order City Voronoi Diagrams Higher Order City Voronoi Diagrams

2012-04-19

arxiv.org/abs/1204.4374v1

Computer Science

Computational Geometry

15 pages, extended version of paper to appear in Proc. 13th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT'12)

Scientific paper

We investigate higher-order Voronoi diagrams in the city metric. This metric is induced by quickest paths in the L1 metric in the presence of an accelerating transportation network of axis-parallel line segments. For the structural complexity of kth-order city Voronoi diagrams of n point sites, we show an upper bound of O(k(n - k) + kc) and a lower bound of {\Omega}(n + kc), where c is the complexity of the transportation network. This is quite different from the bound O(k(n - k)) in the Euclidean metric. For the special case where k = n - 1 the complexity in the Euclidean metric is O(n), while that in the city metric is {\Theta}(nc). Furthermore, we develop an O(k^2(n + c) log n)-time iterative algorithm to compute the kth-order city Voronoi diagram and an O(nc log^2(n + c) log n)-time divide-and-conquer algorithm to compute the farthest-site city Voronoi diagram.

Affiliated with

Also associated with

No associations

Rating

Higher Order City Voronoi Diagrams does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Higher Order City Voronoi Diagrams, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Higher Order City Voronoi Diagrams will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-35161