论文标题
sublrinear显式增量平面Voronoi图
Sublinear Explicit Incremental Planar Voronoi Diagrams
论文作者
论文摘要
提供了一个数据结构，该数据结构明确地维护了平面中$ n $点位点的voronoi图的图，或者在三个维度上的凸壳的凸面壳的偶数图，同时允许插入新站点/点。我们的结构支持在$ \ tilde o（n^{3/4}）$预期摊销时间中插入，其中$ \ tilde o $抑制了polylogarithmic术语。这是实现额定时间插入的第一个结果；以前是Allen等人所显示的。每插入的$θ（\ sqrt {n}）$摊销的组合变化可能会在voronoi图中发生，但是仅针对凸位的特殊情况出现了sublrinear-time算法。
A data structure is presented that explicitly maintains the graph of a Voronoi diagram of $N$ point sites in the plane or the dual graph of a convex hull of points in three dimensions while allowing insertions of new sites/points. Our structure supports insertions in $\tilde O (N^{3/4})$ expected amortized time, where $\tilde O$ suppresses polylogarithmic terms. This is the first result to achieve sublinear time insertions; previously it was shown by Allen et al. that $Θ(\sqrt{N})$ amortized combinatorial changes per insertion could occur in the Voronoi diagram but a sublinear-time algorithm was only presented for the special case of points in convex position.
