Abstract
We propose a simple variant of kd-trees, called rank-based kd-trees, for sets of points in Rd. We show that a rank-based kd-tree, like an ordinary kd-tree, supports range search queries in O(n1-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(n2) 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.
| Original language | English |
|---|---|
| Pages | 126-129 |
| Number of pages | 4 |
| Publication status | Published - 2007 |
| Event | 23rd European Workshop on Computational Geometry (EuroCG 2007) - Graz, Switzerland Duration: 19 Mar 2007 → 21 Mar 2007 Conference number: 23 |
Workshop
| Workshop | 23rd European Workshop on Computational Geometry (EuroCG 2007) |
|---|---|
| Abbreviated title | EuroCG |
| Country/Territory | Switzerland |
| City | Graz |
| Period | 19/03/07 → 21/03/07 |