TY - JOUR
T1 - On the Complexity of Randomly Weighted Multiplicative Voronoi Diagrams
AU - Har-Peled, Sariel
AU - Raichel, Benjamin
N1 - Funding Information:
The authors would like to thank Pankaj Agarwal, Jeff Erickson, Haim Kaplan, Hsien-Chih Chang, and Micha Sharir for useful discussions. In particular, the work of Agarwal, Kaplan, and Sharir [, ] was the catalyst for this work. In addition, we thank Pankaj Agarwal for pointing out a simple way to slightly improve our bound, specifically the result in Theorem . The authors would also like to thank the reviewers for their insightful comments. This study was partially supported by NSF AF awards CCF-0915984, CCF-1217462, and CCF-1421231. A preliminary version of this paper appeared in SoCG 2014 [].
Publisher Copyright:
© 2015, Springer Science+Business Media New York.
PY - 2015/4/1
Y1 - 2015/4/1
N2 - We provide an $$O(n \,\hbox {polylog}\, n)$$O(npolylogn) bound on the expected complexity of the randomly weighted multiplicative Voronoi diagram of a set of $$n$$n sites in the plane, where the sites can be either points, interior disjoint convex sets, or other more general objects. Here the randomness is on the weight of the sites, not on their location. This compares favorably with the worst-case complexity of these diagrams, which is quadratic. As a consequence we get an alternative proof to that of Agarwal et al. (Discrete Comput Geom 54:551–582, 2014) of the near linear complexity of the union of randomly expanded disjoint segments or convex sets (with an improved bound on the latter). The technique we develop is elegant and should be applicable to other problems.
AB - We provide an $$O(n \,\hbox {polylog}\, n)$$O(npolylogn) bound on the expected complexity of the randomly weighted multiplicative Voronoi diagram of a set of $$n$$n sites in the plane, where the sites can be either points, interior disjoint convex sets, or other more general objects. Here the randomness is on the weight of the sites, not on their location. This compares favorably with the worst-case complexity of these diagrams, which is quadratic. As a consequence we get an alternative proof to that of Agarwal et al. (Discrete Comput Geom 54:551–582, 2014) of the near linear complexity of the union of randomly expanded disjoint segments or convex sets (with an improved bound on the latter). The technique we develop is elegant and should be applicable to other problems.
KW - Arrangements
KW - Randomized incremental construction
KW - Voronoi diagrams
UR - http://www.scopus.com/inward/record.url?scp=84937761085&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84937761085&partnerID=8YFLogxK
U2 - 10.1007/s00454-015-9675-0
DO - 10.1007/s00454-015-9675-0
M3 - Article
AN - SCOPUS:84937761085
SN - 0179-5376
VL - 53
SP - 547
EP - 568
JO - Discrete and Computational Geometry
JF - Discrete and Computational Geometry
IS - 3
ER -