Linkless Octree Using Multi-Level Perfect Hashing

Simple item page
dc.contributor.authorChoi, Myung Geolen_US
dc.contributor.authorJu, Eunjungen_US
dc.contributor.authorChang, Jung-Wooen_US
dc.contributor.authorLee, Jeheeen_US
dc.contributor.authorKim, Young J.en_US
dc.date.accessioned2015-02-23T16:07:51Z
dc.date.available2015-02-23T16:07:51Z
dc.date.issued2009en_US
dc.description.abstractThe 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.en_US
dc.description.number7en_US
dc.description.seriesinformationComputer Graphics Forumen_US
dc.description.volume28en_US
dc.identifier.doi10.1111/j.1467-8659.2009.01554.xen_US
dc.identifier.issn1467-8659en_US
dc.identifier.pages1773-1780en_US
dc.identifier.urihttps://doi.org/10.1111/j.1467-8659.2009.01554.xen_US
dc.publisherThe Eurographics Association and Blackwell Publishing Ltden_US
dc.titleLinkless Octree Using Multi-Level Perfect Hashingen_US
Files
Collections
28-Issue 7