A Clustering-Based Approach to Kinetic Closest Pair

Zahed Rahmati, Timothy M. Chan

Research output: Contribution to journalArticlepeer-review

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(nlog Δ) space and processes O(n2βlog Δlog n+ n2βlog Δlog log Δ) events, each in worst-case time O(log 2n+ log 2log Δ). 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 Δlog 2n+ log Δlog 2log Δ). Also, we use a similar approach to provide a KDS for the all ε-nearest neighbors in Rd. The complexities of the previous KDSs, for both closest pair and all ε-nearest neighbors, have polylogarithmic factors, 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)
Pages (from-to)2742-2756
Number of pages15
JournalAlgorithmica
Volume80
Issue number10
DOIs
StatePublished - Oct 1 2018

Keywords

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

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Fingerprint Dive into the research topics of 'A Clustering-Based Approach to Kinetic Closest Pair'. Together they form a unique fingerprint.

Cite this