1 Search Results for "Rahmati, Zahed"

Document

DOI: 10.4230/LIPIcs.SWAT.2016.28

A Clustering-Based Approach to Kinetic Closest Pair

Authors: Timothy M. Chan and Zahed Rahmati

Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)

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 Delta over time, our KDS uses O(n log Delta) space and processes O(n^2 beta log Delta log n + n^2 beta log Delta log log Delta)) events, each in worst-case time O(log^2 n + log^2 log Delta). Here, beta is an extremely slow-growing function. The locality of the KDS is O(log n + log log Delta). Our closest pair KDS supports insertions and deletions of points. An insertion or deletion takes worst-case time O(log Delta log^2 n + log Delta log^2 log Delta). Also, we use a similar approach to provide a KDS for the all epsilon-nearest neighbors in R^d. The complexities of the previous KDSs, for both closest pair and all epsilon-nearest neighbors, have polylogarithmic factor, where the number of logs depends on dimension d. Assuming Delta 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.

Cite as

Timothy M. Chan and Zahed Rahmati. A Clustering-Based Approach to Kinetic Closest Pair. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 28:1-28:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{chan_et_al:LIPIcs.SWAT.2016.28,
  author =	{Chan, Timothy M. and Rahmati, Zahed},
  title =	{{A Clustering-Based Approach to Kinetic Closest Pair}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{28:1--28:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Pagh, Rasmus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.28},
  URN =		{urn:nbn:de:0030-drops-60508},
  doi =		{10.4230/LIPIcs.SWAT.2016.28},
  annote =	{Keywords: Kinetic Data Structure, Clustering, Closest Pair, All Nearest Neighbors}
}

Refine by Author
1 Chan, Timothy M.
1 Rahmati, Zahed

Refine by Classification

Refine by Keyword
1 All Nearest Neighbors
1 Closest Pair
1 Clustering
1 Kinetic Data Structure

Refine by Type
1 document

Refine by Publication Year
1 2016

1 Search Results for "Rahmati, Zahed"

A Clustering-Based Approach to Kinetic Closest Pair

Abstract

Cite as

Thanks for your feedback!

Could not send message