Back to search

University of Waterloo

Reconstructing hv-convex polyominoes with multiple colours

Abstract

dc:description.abstract

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.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2009

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Bains, Adam

Subjects

dc:subject × 2

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/4599

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Bains, Adam. Reconstructing hv-convex polyominoes with multiple colours. University of Waterloo, 2009. http://hdl.handle.net/10012/4599