License
When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-15307
URL: http://drops.dagstuhl.de/opus/volltexte/2008/1530/
Go to the corresponding Portal

Abam, Mohammad ; de Berg, Mark ; Speckmann, Bettina

Kinetic kd-Trees and Longest-Side kd-Trees

pdf-format:
Document 1.pdf (241 KB)

Abstract

We propose a simple variant of kd-trees, called rank-based kd-trees, for sets of points in~$Reals^d$. We show that a rank-based kd-tree, like an ordinary kd-tree, supports range search que-ries in~$O(n^{1-1/d}+k)$ time, where~$k$ is the output size. The main advantage of rank-based kd-trees is that they can be efficiently kinetized: the KDS processes~$O(n^2)$ events in the worst case, assuming that the points follow constant-degree algebraic trajectories, each event can be handled in~$O(log n)$ time, and each point is involved in~$O(1)$ certificates. We also propose a variant of longest-side kd-trees, called rank-based longest-side kd-trees (RBLS kd-trees, for short), for sets of points in~$Reals^2$. RBLS kd-trees can be kinetized efficiently as well and like longest-side kd-trees, RBLS kd-trees support nearest-neighbor, farthest-neighbor, and approximate range search queries in~$O((1/epsilon)log^2 n)$ time. The KDS processes~$O(n^3log n)$ events in the worst case, assuming that the points follow constant-degree algebraic trajectories; each event can be handled in~$O(log^2 n)$ time, and each point is involved in~$O(log n)$ certificates.

BibTeX - Entry

@InProceedings{abam_et_al:DSP:2008:1530,
  author =	{Mohammad Abam and Mark de Berg and Bettina Speckmann},
  title =	{Kinetic kd-Trees and Longest-Side kd-Trees},
  booktitle =	{Data Structures},
  year =	{2008},
  editor =	{Lars Arge and Robert Sedgewick and Raimund Seidel},
  number =	{08081},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2008/1530},
  annote =	{Keywords: Kinetic data structures, kd-tree, longest-side kd-tree}
}

Keywords: Kinetic data structures, kd-tree, longest-side kd-tree
Seminar: 08081 - Data Structures
Issue Date: 2008
Date of publication: 16.06.2008

DROPS-Home | Fulltext Search | Imprint Published by LZI