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:LACETR/oai:collectionscanada.gc.ca:OWTU.10012/4599 |
| Date | January 2009 |
| Creators | Bains, Adam |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | English |
| Type | Thesis or Dissertation |
Page generated in 0.0068 seconds