Kinetic kd-trees

M.A. Abam; M. Berg, de; B. Speckmann

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 language	English
Pages	126-129
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

Access to Document

Metis210769Final published version, 286 KB

Cite this

@conference{b453ce2c177248868ce15607ecb54e23,

title = "Kinetic kd-trees",

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.",

author = "M.A. Abam and {Berg, de}, M. and B. Speckmann",

year = "2007",

language = "English",

pages = "126--129",

note = "23rd European Workshop on Computational Geometry (EuroCG 2007), EuroCG ; Conference date: 19-03-2007 Through 21-03-2007",

}

TY - CONF

T1 - Kinetic kd-trees

AU - Abam, M.A.

AU - Berg, de, M.

AU - Speckmann, B.

N1 - Conference code: 23

PY - 2007

Y1 - 2007

N2 - 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.

AB - 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.

M3 - Abstract

SP - 126

EP - 129

T2 - 23rd European Workshop on Computational Geometry (EuroCG 2007)

Y2 - 19 March 2007 through 21 March 2007

ER -

Kinetic kd-trees

Abstract

Workshop

Access to Document

Fingerprint

Cite this