A clustering-based approach to kinetic closest pair

Timothy M. Chan, Zahed Rahmati

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Given a set P of n moving points in fixed dimension d, where the trajectory of each point is a polynomial of degree bounded by some constant, we present a kinetic data structure (KDS) for maintenance of the closest pair on P. Assuming the closest pair distance is between 1 and Δ over time, our KDS uses O(n log Δ) space and processes O(n2β log Δ log n + n2β log Δ log log Δ)) events, each in worst-case time O(log2 n + log2 log Δ). Here, β is an extremely slow-growing function. The locality of the KDS is O(log n + log log Δ). Our closest pair KDS supports insertions and deletions of points. An insertion or deletion takes worst-case time O(log Δ log2 n+log Δ log2 log Δ). Also, we use a similar approach to provide a KDS for the all ε-nearest neighbors in ℝd. The complexities of the previous KDSs, for both closest pair and all ε-nearest neighbors, have polylogarithmic factor, where the number of logs depends on dimension d. Assuming Δ is polynomial in n, our KDSs obtain improvements on the previous KDSs. Our solutions are based on a kinetic clustering on P. Though we use ideas from the previous clustering KDS by Hershberger, we simplify and improve his work.

Original languageEnglish (US)
Title of host publication15th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2016
EditorsRasmus Pagh
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages28.1-28.13
ISBN (Electronic)9783959770118
DOIs
StatePublished - Jun 1 2016
Externally publishedYes
Event15th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2016 - Reykjavik, Iceland
Duration: Jun 22 2016Jun 24 2016

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume53
ISSN (Print)1868-8969

Other

Other15th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2016
CountryIceland
CityReykjavik
Period6/22/166/24/16

Keywords

  • All nearest neighbors
  • Closest pair
  • Clustering
  • Kinetic data structure

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'A clustering-based approach to kinetic closest pair'. Together they form a unique fingerprint.

Cite this