
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

A LinearTime Normalization of OneDimensional Quadtrees
Akira ITO Katsushi INOUE Yue WANG
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E81D
No.3
pp.271277 Publication Date: 1998/03/25
Online ISSN:
DOI:
Print ISSN: 09168532 Type of Manuscript: PAPER Category: Algorithm and Computational Complexity Keyword: quadtree, normalization, binary string, linear time,
Full Text: PDF(548.1KB)>>
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 "onedimensional 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.

