@inproceedings{d35eb84a97d44c07b3cea0a9bac84489,

title = "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 ϵ-kernels (coresets for approximate width and approximate convex hull) in close to optimal time O(n + (1/ϵ)(d-1)/2), up to a small near-(1/ϵ)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/ϵ)d/4n) preprocessing time and O((1/ϵ)d/4 log n) query time. We obtain improved approximation algorithms for discrete Voronoi diagrams, diameter, and bichromatic closest pair in the Ls-metric for any even integer constant s ≥ 2. The techniques are general and may have further applications.",

keywords = "Approximate nearest neighbor search, Coresets, Diameter, Streaming, The polynomial method",

author = "Chan, {Timothy M.}",

year = "2017",

month = jun,

day = "1",

doi = "10.4230/LIPIcs.SoCG.2017.26",

language = "English (US)",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

pages = "261--2615",

editor = "Katz, {Matthew J.} and Boris Aronov",

booktitle = "33rd International Symposium on Computational Geometry, SoCG 2017",

note = "33rd International Symposium on Computational Geometry, SoCG 2017 ; Conference date: 04-07-2017 Through 07-07-2017",

}