@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.}",
note = "Publisher Copyright: {\textcopyright} Timothy M. Chan.; 33rd International Symposium on Computational Geometry, SoCG 2017 ; Conference date: 04-07-2017 Through 07-07-2017",
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",
}