Kinetic kd-trees

Onderzoeksoutput: Bijdrage aan congresAbstractAcademic

40 Downloads (Pure)

Samenvatting

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.
Originele taal-2Engels
Pagina's126-129
StatusGepubliceerd - 2007
Evenement23rd European Workshop on Computational Geometry (EuroCG 2007) - Graz, Zwitserland
Duur: 19 mrt 200721 mrt 2007
Congresnummer: 23

Workshop

Workshop23rd European Workshop on Computational Geometry (EuroCG 2007)
Verkorte titelEuroCG
LandZwitserland
StadGraz
Periode19/03/0721/03/07

Vingerafdruk Duik in de onderzoeksthema's van 'Kinetic kd-trees'. Samen vormen ze een unieke vingerafdruk.

Citeer dit