Approximating center points with iterative Radon points
Approximating center points with iterative Radon points
复制标题
用迭代氡点近似中心点
DOI：
--
复制
发表时间：
1996
影响因子：
--
通讯作者：
S. Teng
中科院分区：
文献类型：
--
作者：
K. Clarkson;D. Eppstein;G. Miller;Carl Sturtivant;S. Teng
给出了一种实用且可证明效果良好的逼近中心点的蒙特卡罗算法。设P是Rd中n个点的集合，如果每个包含c的闭半空间至少包含P的βn个点，则点c∈Rd是P的β中心点，每个点集都有一个1/(d+1)中心点；我们的算法以高概率找到一个Ω（1/d2）中心点。我们的算法具有很小的常数因子，是第一个复杂度为次指数d的近似中心点算法，并且可以优化并行化到O（log2d log log n）时间。该算法已用于网格划分方法，可用于统计学中多元数据集的高击穿估计的构建。在实际应用中，该方法有可能改善弱<s:1>网络的构造结果。我们推导了我们算法的一个变体，其时间限制在d上是完全多项式的，在n上是线性的，并展示了如何将我们的方法与以前的技术结合起来，更快地计算高质量的中心点。
We give a practical and provably good Monte Carlo algorithm for approximating center points. Let P be a set of n points in Rd. A point c∈Rd is a β-center point of P if every closed halfspace containing c contains at least βn points of P. Every point set has a 1/(d+1)-center point; our algorithm finds an Ω(1/d2)-center point with high probability. Our algorithm has a small constant factor and is the first approximate center point algorithm whose complexity is subexponential in d. Moreover, it can be optimally parallelized to require O(log2d log log n) time. Our algorithm has been used in mesh partitioning methods and can be used in the construction of high breakdown estimators for multivariate datasets in statistics. It has the potential to improve results in practice for constructing weak ∊-nets. We derive a variant of our algorithm whose time bound is fully polynomial in d and linear in n, and show how to combine our approach with previous techniques to compute high quality center points more quickly.