TY - GEN

T1 - A clustering-based approach to kinetic closest pair

AU - Chan, Timothy M.

AU - Rahmati, Zahed

N1 - Publisher Copyright:
© Timothy M. Chan and Zahed Rahmati.
Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.

PY - 2016/6/1

Y1 - 2016/6/1

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

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

KW - All nearest neighbors

KW - Closest pair

KW - Clustering

KW - Kinetic data structure

UR - http://www.scopus.com/inward/record.url?scp=85012008392&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85012008392&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.SWAT.2016.28

DO - 10.4230/LIPIcs.SWAT.2016.28

M3 - Conference contribution

AN - SCOPUS:85012008392

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 28.1-28.13

BT - 15th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2016

A2 - Pagh, Rasmus

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 15th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2016

Y2 - 22 June 2016 through 24 June 2016

ER -