A linear-time normalization of one-dimensional quadtrees

作     者：Ito, A Inoue, K Wang, Y 

作者机构：Yamaguchi Univ Fac Engn Ube Yamaguchi 7558611 Japan 

出 版 物：《IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS》 (电子信息通信学会汇刊：信息与系统)

年 卷 期：1998年第E81D卷第3期

页      面：271-277页

核心收录：

学科分类：0810[工学-信息与通信工程] 08[工学] 0835[工学-软件工程] 081001[工学-通信与信息系统] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：quadtree normalization binary string linear time 

摘      要：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.