Approximating the minimum closest pair distance and nearest neighbor distances of linearly moving points

Timothy M. Chan, Zahed Rahmati

Research output: Contribution to conferencePaper

Abstract

Given a set of n moving points in Rd, where each point moves along a linear trajectory at arbitrary but constant velocity, we present an O (n5/3)-time algorithm1 to compute a (1 +-)-factor approximation to the minimum closest pair distance over time, for any constant- > 0 and any constant dimension d. This addresses an open problem posed by Gupta, Janardan, and Smid [12]. More generally, we consider a data structure version of the problem: for any linearly moving query point q, we want a (1 +-)-factor approximation to the minimum nearest neighbor distance to q over time. We present a data structure that requires O(n5/3) space and ?O (n2/3) query time, O(n5) space and polylogarithmic query time, or O(n) space and O(n4/5) query time, for any constant- > 0 and any constant dimension d.

Original languageEnglish (US)
Pages136-140
Number of pages5
StatePublished - Jan 1 2015
Externally publishedYes
Event27th Canadian Conference on Computational Geometry, CCCG 2015 - Kingston, Canada
Duration: Aug 10 2015Aug 12 2015

Other

Other27th Canadian Conference on Computational Geometry, CCCG 2015
CountryCanada
CityKingston
Period8/10/158/12/15

ASJC Scopus subject areas

  • Geometry and Topology
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Approximating the minimum closest pair distance and nearest neighbor distances of linearly moving points'. Together they form a unique fingerprint.

  • Cite this

    Chan, T. M., & Rahmati, Z. (2015). Approximating the minimum closest pair distance and nearest neighbor distances of linearly moving points. 136-140. Paper presented at 27th Canadian Conference on Computational Geometry, CCCG 2015, Kingston, Canada.