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.2019.61
URN: urn:nbn:de:0030-drops-104659
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10465/
Go to the corresponding LIPIcs Volume Portal

Xue, Jie ; Li, Yuan ; Rahul, Saladi ; Janardan, Ravi

Searching for the Closest-Pair in a Query Translate

pdf-format:
LIPIcs-SoCG-2019-61.pdf (0.6 MB)

Abstract

We consider a range-search variant of the closest-pair problem. Let Gamma be a fixed shape in the plane. We are interested in storing a given set of n points in the plane in some data structure such that for any specified translate of Gamma, the closest pair of points contained in the translate can be reported efficiently. We present results on this problem for two important settings: when Gamma is a polygon (possibly with holes) and when Gamma is a general convex body whose boundary is smooth. When Gamma is a polygon, we present a data structure using O(n) space and O(log n) query time, which is asymptotically optimal. When Gamma is a general convex body with a smooth boundary, we give a near-optimal data structure using O(n log n) space and O(log^2 n) query time. Our results settle some open questions posed by Xue et al. at SoCG 2018.

BibTeX - Entry

@InProceedings{xue_et_al:LIPIcs:2019:10465,
  author =	{Jie Xue and Yuan Li and Saladi Rahul and Ravi Janardan},
  title =	{{Searching for the Closest-Pair in a Query Translate}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{61:1--61:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Gill Barequet and Yusu Wang},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10465},
  URN =		{urn:nbn:de:0030-drops-104659},
  doi =		{10.4230/LIPIcs.SoCG.2019.61},
  annote =	{Keywords: Closest pair, Range search, Geometric data structures, Translation query}
}

Keywords: Closest pair, Range search, Geometric data structures, Translation query
Collection: 35th International Symposium on Computational Geometry (SoCG 2019)
Issue Date: 2019
Date of publication: 11.06.2019

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