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.
@InProceedings{arya_et_al:LIPIcs.SoCG.2017.10, author = {Arya, Sunil and da Fonseca, Guilherme D. and Mount, David M.}, title = {{Near-Optimal epsilon-Kernel Construction and Related Problems}}, booktitle = {33rd International Symposium on Computational Geometry (SoCG 2017)}, pages = {10:1--10:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-038-5}, ISSN = {1868-8969}, year = {2017}, volume = {77}, editor = {Aronov, Boris and Katz, Matthew J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.10}, URN = {urn:nbn:de:0030-drops-72257}, doi = {10.4230/LIPIcs.SoCG.2017.10}, annote = {Keywords: Approximation, diameter, kernel, coreset, nearest neighbor, polytope membership, bichromatic closest pair, Macbeath regions} }
Feedback for Dagstuhl Publishing