Kinetic kd-trees

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

Kinetic kd-trees

Onderzoeksoutput: Bijdrage aan congres › Paper › Academic

202 Downloads (Pure)

Samenvatting

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.

Originele taal-2	Engels
Pagina's	126-129
Aantal pagina's	4
Status	Gepubliceerd - 2007
Evenement	23rd European Workshop on Computational Geometry (EuroCG 2007) - Graz, Zwitserland Duur: 19 mrt. 2007 → 21 mrt. 2007 Congresnummer: 23

Workshop

Workshop	23rd European Workshop on Computational Geometry (EuroCG 2007)
Verkorte titel	EuroCG
Land/Regio	Zwitserland
Stad	Graz
Periode	19/03/07 → 21/03/07

Toegang tot document

Metis210769Definitieve gepubliceerde versie, 286 KB

Citeer dit

@conference{b453ce2c177248868ce15607ecb54e23,

title = "Kinetic kd-trees",

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

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

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

M3 - Paper

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

Samenvatting

Workshop

Toegang tot document

Vingerafdruk

Citeer dit