Premium
Linkless Octree Using Multi‐Level Perfect Hashing
Author(s) -
Choi Myung Geol,
Ju Eunjung,
Chang JungWoo,
Lee Jehee,
Kim Young J.
Publication year - 2009
Publication title -
computer graphics forum
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.578
H-Index - 120
eISSN - 1467-8659
pISSN - 0167-7055
DOI - 10.1111/j.1467-8659.2009.01554.x
Subject(s) - quadtree , computer science , octree , hash function , pointer (user interface) , data structure , hash table , dynamic perfect hashing , perfect hash function , tree (set theory) , theoretical computer science , overhead (engineering) , tree traversal , parallel computing , algorithm , artificial intelligence , mathematics , double hashing , mathematical analysis , computer security , programming language , operating system
The standard C/C++ implementation of a spatial partitioning data structure, such as octree and quadtree, is often inefficient in terms of storage requirements particularly when the memory overhead for maintaining parent‐to‐child pointers is significant with respect to the amount of actual data in each tree node. In this work, we present a novel data structure that implements uniform spatial partitioning without storing explicit parent‐to‐child pointer links. Our linkless tree encodes the storage locations of subdivided nodes using perfect hashing while retaining important properties of uniform spatial partitioning trees, such as coarse‐to‐fine hierarchical representation, efficient storage usage, and efficient random accessibility. We demonstrate the performance of our linkless trees using image compression and path planning examples.