A Linear-Time Normalization of One-Dimensional Quadtrees

摘要

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 un- known 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 nor- malization problem, i.e., given a binary string represented by a regional binary tree, the task is to identify the amount of (right- ward) 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.