Time-windowed closest pair

Timothy M. Chan, Simon Pratt

Research output: Contribution to conferencePaper

Abstract

Given a set of points in any constant dimension, each of which is associated with a time during which that point is active, we design a data structure with O(n log n) space that can find the closest pair of active points within a query interval of time in O(log log n) time using a quadtree-based approach in the word-RAM model.

Original languageEnglish (US)
Pages141-144
Number of pages4
StatePublished - Jan 1 2015
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 'Time-windowed closest pair'. Together they form a unique fingerprint.

  • Cite this

    Chan, T. M., & Pratt, S. (2015). Time-windowed closest pair. 141-144. Paper presented at 27th Canadian Conference on Computational Geometry, CCCG 2015, Kingston, Canada.