2026-08-10T09:51:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7227 2024-03-06T10:39:59Z ddc:004 open_access

Applications of Chebyshev Polynomials to Low-Dimensional Computational Geometry Chan, Timothy M. diameter coresets approximate nearest neighbor search the polynomial method streaming 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Timothy M. Chan 2017 Is Part Of LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2017.26 urn:nbn:de:0030-drops-72279 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.26 eng https://creativecommons.org/licenses/by/3.0/legalcode