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.

Additional Metadata
Conference 23rd Annual Canadian Conference on Computational Geometry, CCCG 2011
Citation
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.