Applications of Chebyshev polynomials to low-dimensional computational geometry

Timothy M. Chan


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 $\varepsilon$-kernels (coresets for approximate width and approximate convex hull) for any $d$-dimensional $n$-point set in near-optimal time, close to $O(n+(1/\varepsilon)^{(d-1)/2})$, ignoring a small $(1/\varepsilon)^{3/2+o(1)}$ factor. We obtain an improved data structure for Euclidean approximate nearest neighbor search with close to $O(n\log n + (1/\varepsilon)^{d/4}n)$ preprocessing time and $O((1/\varepsilon)^{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\ge 2$. The techniques are general and may have further applications.

Full Text:



ISSN: 1920-180X