Kinetic kd-trees and longest-side kd-trees

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Citations (Scopus)

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. 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 R2. RBLS kd-trees can be kinetized efficiently as well and like longest-side kd-trees, RBLS kdtrees support nearest-neighbor, farthest-neighbor, and approximate range search queries in O((1/e) log2 n) time. The KDS processes O(n3 log n) events in the worst case, assuming that the points follow constant-degree algebraic trajectories; each event can be handled in O(log2 n) time, and each point is involved in O(log n) certificates.
Original languageEnglish
Title of host publicationProceedings of the 23rd Annual ACM Symposium on Computational Geometry (SoCG 2007) 6-8 June 2007, Geongju, South Korea
Place of PublicationNew York
PublisherAssociation for Computing Machinery, Inc
Pages364-372
ISBN (Print)978-1-59593-705-6
Publication statusPublished - 2007
Event23rd International Symposium on Computational Geometry (SoCG 2007) - Gyeongju, Korea, Republic of
Duration: 6 Jun 20078 Jun 2007
Conference number: 23

Conference

Conference23rd International Symposium on Computational Geometry (SoCG 2007)
Abbreviated titleSoCG 2007
CountryKorea, Republic of
CityGyeongju
Period6/06/078/06/07

Fingerprint

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

Cite this