This paper applies the randomized incremental construction (RIC) framework to computing the Hausdorff Voronoi diagram of a family of k clusters of points in the plane. The total number of points is n. The diagram is a generalization of Voronoi diagrams based on the Hausdorff distance function. The combinatorial complexity of the Hausdorff Voronoi diagram is O(n+m), where m is the total number of crossings between pairs of clusters. For non-crossing clusters (m=0), our algorithm works in expected O(n log n + k log n log k) time and deterministic O(n) space. For arbitrary clusters (m=O(n^2)), the algorithm runs in expected O((m+n log k) log n) time and O(m +n log k) space. When clusters cross, bisectors are disconnected curves resulting in disconnected Voronoi regions that challenge the incremental construction. This paper applies the RIC paradigm to a Voronoi diagram with disconnected regions and disconnected bisectors, for the first time.
翻译:本文应用随机递增构造框架( RIC ) 来计算由 k 组组组成的陆基图。 总点数为 n。 该图是根据Hausdorf 距离函数对Voronio 图表的概括化。 Hausdorf Voranoi 图表的组合复杂度为 O( n+m), 其中 m 是两组间交叉的总数。 对于非交叉组( m=0 ), 我们的算法在预期的 O(n log n + klog nlog k) 时间和确定性 O( n) 空间中的计算。 对于任意组( m=O (n) ), 算法在预期的 O( m +n log n) 时间和 O(m + n log k) log k 空间中运行。 当组交叉时, 两部分是断开的曲线, 导致对递增构造产生挑战的离线的Voronoi 区域。 本文首次将 RIC 模式应用于带有断开的区域和断开的Vornoi 的Vornoi 图表。