License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2017.10
URN: urn:nbn:de:0030-drops-72257
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7225/
Go to the corresponding LIPIcs Volume Portal

Arya, Sunil ; da Fonseca, Guilherme D. ; Mount, David M.

Near-Optimal epsilon-Kernel Construction and Related Problems

pdf-format:
LIPIcs-SoCG-2017-10.pdf (0.6 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{arya_et_al:LIPIcs:2017:7225,
  author =	{Sunil Arya and Guilherme D. da Fonseca and David M. Mount},
  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 =	{Boris Aronov and Matthew J. Katz},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7225},
  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}
}

Keywords: Approximation, diameter, kernel, coreset, nearest neighbor, polytope membership, bichromatic closest pair, Macbeath regions
Collection: 33rd International Symposium on Computational Geometry (SoCG 2017)
Issue Date: 2017
Date of publication: 20.06.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI