文章基本信息

标题：Linear Expected Complexity for Directional and Multiplicative Voronoi Diagrams
本地全文：下载
作者：Chenglin Fan ; Benjamin Raichel
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：173
页码：45:1-45:18
DOI：10.4230/LIPIcs.ESA.2020.45
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Voronoi Diagrams; Expected Complexity; Computational Geometry