An in-place priority search tree
One of the classic data structures for storing point sets in R2 is the priority search tree, introduced by Mc- Creight in 1985. We show that this data structure can be made in-place, i.e., it can be stored in an array such that each entry only stores one point of the point set. We show that the standard query operations can be an- swered within the same time bounds as for the original priority search tree, while using only O(1) extra space.
|Conference||23rd Annual Canadian Conference on Computational Geometry, CCCG 2011|
De, M. (Minati), Maheshwari, A, Nandy, S.C. (Subhas C.), & Smid, M. (2011). An in-place priority search tree. Presented at the 23rd Annual Canadian Conference on Computational Geometry, CCCG 2011.