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.
| Identifer | oai:union.ndltd.org:WATERLOO/oai:uwspace.uwaterloo.ca:10012/4599 |
| Date | January 2009 |
| Creators | Bains, Adam |
| Source Sets | University of Waterloo Electronic Theses Repository |
| Language | English |
| Detected Language | English |
| Type | Thesis or Dissertation |
Page generated in 0.0014 seconds