A Linear-Time Normalization of One-Dimensional Quadtrees

Akira ITO  Katsushi INOUE  Yue WANG  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E81-D   No.3   pp.271-277
Publication Date: 1998/03/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Algorithm and Computational Complexity
Keyword: 
quadtree,  normalization,  binary string,  linear time,  

Full Text: PDF>>
Buy this Article




Summary: 
Given a binary picture represented by a region quadtree, it is desirable to identify the amount of (rightward and downward) shifts of the foreground components such that it gives the minimum number of nodes of its quadtree. This problem is called "quadtree normalization. " For this problem, it is unknown whether there exists a linear time algorithm with respect to the size of given images (i. e. , the number of pixels). In this study, we investigate the "one-dimensional version" of the quadtree normalization problem, i. e. , given a binary string represented by a regional binary tree, the task is to identify the amount of (rightward) shift of the foreground components such that it gives the minimum number of nodes of its binary tree. We show that there exists a linear time algorithm for this version.