Reconstructing hv-convex polyominoes with multiple colours

polyominoes;hv-convex;Computer Science

Bains, Adam

University of Waterloo

关键词: polyominoes;    hv-convex;    Computer Science;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/4599/1/Bains_Adam.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

This thesis examines the problem of reconstructing multiple discrete 2D objects, represented by a set of cells arranged in an m × n grid, from their projections. The objects being constructed are disjoint, hv-convex polyominoes, each of which has a separate colour. The main results presented here are two algorithms for unordered C-colour reconstruction that have time complexities of O(C^2n^{2C +1}m^{2C +1}) and O(C^2 min(n^{2C}, m^{2C})nm), an ordered C-colour reconstruction algorithm that is O(Cmin(n^{2C}, m^{2C})nm), and an NP-completeness proof when the number of colours is unbounded.