Delaunay Triangulations in O(sort(n)) Time and More
Delaunay Triangulations in O(sort(n)) Time and More
复制标题
DOI：
10.1145/1944345.1944347
复制
发表时间：
2009-10
期刊：
影响因子：
--
通讯作者：
K. Buchin;Wolfgang Mulzer
中科院分区：
文献类型：
--
作者：
K. Buchin;Wolfgang Mulzer
本文给出了在透二分法和遗传环境下Delaunay三角剖分和凸包的几个结果：（i）平面点集的Delaunay三角剖分可以在期望时间O（sort（n））内在字RAM上计算，其中sort（n）是排序n个数的时间。我们假设字RAM支持在恒定时间内的混洗操作;（ii）如果我们知道平面点集在x方向和y方向上的排序，则可以通过具有预期线性深度的随机代数计算树找到其DT;（iii）给定平面中的点的全域U，我们为Delaunay查询构建数据结构D：对于U的任何子集P，D可以在时间O中找到P的DT（|P|重对数|U|);（iv）给定三维空间中的点在一般凸位置的论域U，存在用于凸船体查询的数据结构D：对于U的任何子集P，D可以在时间O找到P的凸船体（|P|（日志日志|U|）^2）;（v）给定一个3-空间中的凸多面体，其n个顶点被k <$2种颜色着色，我们可以在O（n（log log n）^2）的时间内将其分解为各个颜色类的凸壳，结果（i）-（iii）推广到高维.我们需要广泛的技术。最突出的是，我们描述了一个减少从DT最近邻图，依赖于一个新的变体的随机增量结构，使用相关采样。
We present several results about Delaunay triangulations (DTs) and convex hulls in transdichotomous and hereditary settings: (i) the DT of a planar point set can be computed in expected time O(sort(n)) on a word RAM, where sort(n)is the time to sort n numbers. We assume that the word RAM supports the shuffle-operation in constant time; (ii) if we know the ordering of a planar point set in x- and in y-direction, its DT can be found by a randomized algebraic computation tree of expected linear depth;(iii) given a universe U of points in the plane, we construct a data structure D for Delaunay queries: for any subset P of U, D can find the DT of P in time O(|P| loglog |U|); (iv) given a universe U of points in 3-space in general convex position, there is a data structure D for convex hull queries: for any subset P of U, D can find the convex hull of P in time O(|P| (log log |U|)^2);(v) given a convex polytope in 3-space with n vertices which are colored with k ≫ 2 colors, we can split it into the convex hulls of the individual color classes in time O(n (log log n)^2).The results (i)--(iii) generalize to higher dimensions. We need a wide range of techniques. Most prominently, we describe a reduction from DTs to nearest-neighbor graphs that relies on a new variant of randomized incremental constructions using dependent sampling.