Kinetic kd-trees

Research output: Contribution to conferenceAbstractAcademic

36 Downloads (Pure)

Abstract

We propose a simple variant of kd-trees, called rankbased 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 constantdegree algebraic trajectories, each event can be handled in O(log n) time, and each point is involved in O(1) certificates.
Original languageEnglish
Pages126-129
Publication statusPublished - 2007
Event23rd European Workshop on Computational Geometry (EuroCG 2007) - Graz, Switzerland
Duration: 19 Mar 200721 Mar 2007
Conference number: 23

Workshop

Workshop23rd European Workshop on Computational Geometry (EuroCG 2007)
Abbreviated titleEuroCG
CountrySwitzerland
CityGraz
Period19/03/0721/03/07

Fingerprint Dive into the research topics of 'Kinetic kd-trees'. Together they form a unique fingerprint.

  • Cite this

    Abam, M. A., Berg, de, M., & Speckmann, B. (2007). Kinetic kd-trees. 126-129. Abstract from 23rd European Workshop on Computational Geometry (EuroCG 2007), Graz, Switzerland.