FIXED-SIZE GEOMETRIC COVERING TO MINIMIZE THE NUMBER OF DISCONNECTED COMPONENTS
Andrew Joseph Tomascak · Montana State University ScholarWorks (Montana State University) · 2003
Decomposing an image into fixed-sized sub-images has many applications in image storage and analysis, especially in the area of three dimensional imaging.The Connected Component Problem deals with the task of covering a binary image with tiles such that the sum of the number of connected components of each tile is minimized.This problem is relevant for storing and processing three dimensional images, in particular those using voxels.Interest in this study was originally spawned through the study of biological voxel images, and in particular, neural morphology.In this thesis, the Connected Component Problem is studied in both of its basic forms, allowing overlapping and the more restricted version where overlap is not allowed.The names of the two variations of the problem are the Connected Component Covering and the Connected Component Tiling.In the non-overlapping version, the Connected Component Tiling, a variation of this problem is proven to be NP-complete.An approximation factor is proven for both instances.Approximation algorithms are given for both cases iii