2020/04/20 by Chenglin Fan, Fan, Chenglin, Benjamin Raichel +1
Computer Science · #Computational Geometry (cs.CG) #FOS: Computer and information sciences #cs.CG
paper · pdf · doi:10.48550/arxiv.2004.09385
arxiv created 2020/04/20 · arxiv updated 2020/04/21
While the standard unweighted Voronoi diagram in the plane has linear worst-case complexity, many of its natural generalizations do not. This paper considers two such previously studied generalizations, namely multiplicative and semi Voronoi diagrams. These diagrams both have quadratic worst-case complexity, though here we show that their expected complexity is linear for certain natural randomized inputs. Specifically, we argue that the expected complexity is linear for: (1) semi Voronoi diagrams when the visible direction is randomly sampled, and (2) for multiplicative diagrams when either weights are sampled from a constant-sized set, or the more challenging case when weights are arbitrary but locations are sampled from a square.