Article: Linkless octree using multi-level perfect hashing

File Download Links for fulltext
(May Require Subscription)
Supplementary
  • Basic View
  • Metadata View
  • XML View
TitleLinkless octree using multi-level perfect hashing
AuthorsChoi, MG3
Ju, EJ
Chang, JW2
Lee, JH
Kim, YJ1
KeywordsComputer Graphics [I.3.6]: Graphics data structures and data types—
Issue Date2009
PublisherWiley-Blackwell Publishing Ltd.. The Journal's web site is located at http://www.wiley.com/bw/journal.asp?ref=0167-7055
CitationComputer Graphics Forum: the international journal of the Eurographics Association, 2009, v. 28 n. 7, p. 1773-1780 [How to Cite?]
DOI: http://dx.doi.org/10.1111/j.1467-8659.2009.01554.x
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.
ISSN0167-7055
2011 Impact Factor: 1.634
2011 SCImago Journal Rankings: 0.051
DOIhttp://dx.doi.org/10.1111/j.1467-8659.2009.01554.x
DC Field
Value
dc.contributor.authorChoi, MG
dc.contributor.authorJu, EJ
dc.contributor.authorChang, JW
dc.contributor.authorLee, JH
dc.contributor.authorKim, YJ
dc.date.accessioned2011-06-28T04:52:23Z
dc.date.available2011-06-28T04:52:23Z
dc.date.issued2009
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.
dc.description.naturepostprint
dc.identifier.citationComputer Graphics Forum: the international journal of the Eurographics Association, 2009, v. 28 n. 7, p. 1773-1780 [How to Cite?]
DOI: http://dx.doi.org/10.1111/j.1467-8659.2009.01554.x
dc.identifier.citeulike6331010
dc.identifier.doihttp://dx.doi.org/10.1111/j.1467-8659.2009.01554.x
dc.identifier.epage1780
dc.identifier.hkuros182651
dc.identifier.issn0167-7055
2011 Impact Factor: 1.634
2011 SCImago Journal Rankings: 0.051
dc.identifier.issue7
dc.identifier.openurl
dc.identifier.scopuseid_2-s2.0-71949116983
dc.identifier.spage1773
dc.identifier.urihttp://hdl.handle.net/10722/134617
dc.identifier.volume28
dc.languageeng
dc.publisherWiley-Blackwell Publishing Ltd.. The Journal's web site is located at http://www.wiley.com/bw/journal.asp?ref=0167-7055
dc.relation.ispartofComputer Graphics Forum: the international journal of the Eurographics Association
dc.rightsThe definitive version is available at www3.interscience.wiley.com
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License
dc.subjectComputer Graphics [I.3.6]: Graphics data structures and data types—
dc.titleLinkless octree using multi-level perfect hashing
dc.typeArticle
Author Affiliations
  1. Ewha Womens University
  2. The University of Hong Kong
  3. Seoul National University