Applications of Chebyshev Polynomials to Low-Dimensional Computational Geometry
Applications of Chebyshev Polynomials to Low-Dimensional Computational Geometry
复制标题
切比雪夫多项式在低维计算几何中的应用
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Timothy M. Chan
中科院分区：
文献类型：
--
作者：
Timothy M. Chan
我们应用多项式的方法-特别是切比雪夫多项式-获得一些新的结果几何逼近算法在低常维。例如，我们给出了一个算法来构造ε-核（近似宽度和近似凸船体的核集），其时间接近于最优时间O（n +（1/n）^{（d-1）/2}），直到一个小的近似（1/n）^{3/2}因子，对于任何d维n点集。我们获得了一种改进的欧几里得 * 近似最近邻搜索 * 数据结构，预处理时间接近O（n log n +（1/epsilon）^{d/4} n），查询时间接近O（（1/epsilon）^{d/4} log n）。对于任意偶数常数s >= 2，我们得到了离散Voronoi图、直径和双色最近对在L_s度量中的改进近似算法。这些技术是通用的，并且可以具有进一步的应用。
We apply the polynomial method - specifically, Chebyshev polynomials - to obtain a number of new results on geometric approximation algorithms in low constant dimensions. For example, we give an algorithm for constructing epsilon-kernels (coresets for approximate width and approximate convex hull) in close to optimal time O(n + (1/epsilon)^{(d-1)/2}), up to a small near-(1/epsilon)^{3/2} factor, for any d-dimensional n-point set. We obtain an improved data structure for Euclidean *approximate nearest neighbor search* with close to O(n log n + (1/epsilon)^{d/4} n) preprocessing time and O((1/epsilon)^{d/4} log n) query time. We obtain improved approximation algorithms for discrete Voronoi diagrams, diameter, and bichromatic closest pair in the L_s-metric for any even integer constant s >= 2. The techniques are general and may have further applications.