License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.08081.2
URN: urn:nbn:de:0030-drops-15307
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2008/1530/
Go to the corresponding Portal |
Abam, Mohammad ;
de Berg, Mark ;
Speckmann, Bettina
Kinetic kd-Trees and Longest-Side kd-Trees
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:DagSemProc.08081.2,
author = {Abam, Mohammad and de Berg, Mark and Speckmann, Bettina},
title = {{Kinetic kd-Trees and Longest-Side kd-Trees}},
booktitle = {Data Structures},
pages = {1--12},
series = {Dagstuhl Seminar Proceedings (DagSemProc)},
ISSN = {1862-4405},
year = {2008},
volume = {8081},
editor = {Lars Arge and Robert Sedgewick and Raimund Seidel},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2008/1530},
URN = {urn:nbn:de:0030-drops-15307},
doi = {10.4230/DagSemProc.08081.2},
annote = {Keywords: Kinetic data structures, kd-tree, longest-side kd-tree}
}
Keywords: |
|
Kinetic data structures, kd-tree, longest-side kd-tree |
Collection: |
|
08081 - Data Structures |
Issue Date: |
|
2008 |
Date of publication: |
|
16.06.2008 |