### Applications of Chebyshev polynomials to low-dimensional computational geometry

#### Abstract

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:

PDFDOI: http://dx.doi.org/10.20382/jocg.v9i2a2

ISSN: 1920-180X