2026-08-10T22:48:42Z https://drops.dagstuhl.de/oai

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

Near-Optimal epsilon-Kernel Construction and Related Problems Arya, Sunil da Fonseca, Guilherme D. Mount, David M. Approximation diameter kernel coreset nearest neighbor polytope membership bichromatic closest pair Macbeath regions The computation of (i) eps-kernels, (ii) approximate diameter, and (iii) approximate bichromatic closest pair are fundamental problems in geometric approximation. In each case the input is a set of points in d-dimensional space for a constant d and an approximation parameter eps > 0. In this paper, we describe new algorithms for these problems, achieving significant improvements to the exponent of the eps-dependency in their running times, from roughly d to d/2 for the first two problems and from roughly d/3 to d/4 for problem (iii). These results are all based on an efficient decomposition of a convex body using a hierarchy of Macbeath regions, and contrast to previous solutions that decomposed the space using quadtrees and grids. By further application of these techniques, we also show that it is possible to obtain near-optimal preprocessing time for the most efficient data structures for (iv) approximate nearest neighbor searching, (v) directional width queries, and (vi) polytope membership queries. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sunil Arya and Guilherme D. da Fonseca and David M. Mount 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.10 urn:nbn:de:0030-drops-72257 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.10 eng https://creativecommons.org/licenses/by/3.0/legalcode