Geometric partitioning made easier, even in parallel
Geometric partitioning made easier, even in parallel
复制标题
几何分区变得更容易，即使是并行的
DOI：
10.1145/160985.161002
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
M. Goodrich
中科院分区：
文献类型：
--
作者：
M. Goodrich
我们提出了一种简单的方法，该方法以一种易于应用于新问题的方式构建几何分区。我们避免使用VC-dimension参数，而是将我们的参数基于我们称为脚手架维度的概念，该脚手尺寸为VC-dimension，并且更简单地应用。我们展示了如何轻松构造具有有界支架尺寸的范围空间的（1/r）-Net和（1/r） - Approximations，这立即暗示了用于构造（1/r）切割的简单算法（通过直接向前的递归细分方法）。但是，更重要的是，对于以前的方法的一种概念性简化，我们的方法在许多计算几何问题上导致渐近渐近，更高效的EREW PRAM并行算法，包括开发第一个最佳作品NC NC NC NC算法的NC算法。众所周知的3维凸壳问题，它解决了Amato和Preparata的开放问题。有趣的是，我们的方法还通过参数搜索范式产生了距离选择问题的更快的顺序算法，该范围解决了Agarwal，Aronov，Sharir和Suri提出的开放问题，并由Dickerson和Drysdale重申。
We present a simple approach for constructing geometric partitions in a way that is easy to apply to new problems. We avoid the use of VC-dimension arguments, and, instead, base our arguments on a notion we call the scaffold dimension, which subsumes the VC-dimension and is simpler to apply. We show how to easily construct (1/r)-nets and (1/r)-approximations for range spaces with bounded scaffold dimension, which immediately implies simple algorithms for constructing (1/r)-cuttings (by straight-forward recursive subdivision methods). More significant than simply being a conceptual simplification of previous approaches, however, is that our methods lead to asymptotically faster and more-efficient EREW PRAM parallel algorithms for a number of computational geometry problems, including the development of the first optimal-work NC algorithm for the well-known 3-dimensional convex hull problem, which solves an open problem of Amato and Preparata. Interestingly, our approach also yields a faster sequential algorithm for the distance selection problem, by the parametric searching paradigm, which solves an open problem posed by Agarwal, Aronov, Sharir, and Suri, and reiterated by Dickerson and Drysdale.