Time-windowed closest pair

Timothy M. Chan; Simon Pratt

Time-windowed closest pair

Timothy M. Chan
, Simon Pratt

Siebel School of Computing and Data Science

Research output: Contribution to conference › Paper › peer-review

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 language	English (US)
Pages	141-144
Number of pages	4
State	Published - 2015
Event	27th Canadian Conference on Computational Geometry, CCCG 2015 - Kingston, Canada Duration: Aug 10 2015 → Aug 12 2015

Other

Other	27th Canadian Conference on Computational Geometry, CCCG 2015
Country/Territory	Canada
City	Kingston
Period	8/10/15 → 8/12/15

ASJC Scopus subject areas

Geometry and Topology
Computational Mathematics

Library availability

Discover UIUC Full Text

Cite this

@conference{9d79e47c9b0247e4a3b0c28ce5778ace,

title = "Time-windowed closest pair",

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.",

author = "Chan, \{Timothy M.\} and Simon Pratt",

note = "∗Research supported by The Natural Sciences and Engineering Research Council of Canada and the Ontario Graduate Scholarship.; 27th Canadian Conference on Computational Geometry, CCCG 2015 ; Conference date: 10-08-2015 Through 12-08-2015",

year = "2015",

language = "English (US)",

pages = "141--144",

}

TY - CONF

T1 - Time-windowed closest pair

AU - Chan, Timothy M.

AU - Pratt, Simon

N1 - ∗Research supported by The Natural Sciences and Engineering Research Council of Canada and the Ontario Graduate Scholarship.

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/84976866071

UR - https://www.scopus.com/pages/publications/84976866071#tab=citedBy

M3 - Paper

AN - SCOPUS:84976866071

SP - 141

EP - 144

T2 - 27th Canadian Conference on Computational Geometry, CCCG 2015

Y2 - 10 August 2015 through 12 August 2015

ER -

Time-windowed closest pair

Abstract

Other

ASJC Scopus subject areas

Library availability

Related links

Fingerprint

Cite this