Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419131 | Discrete Applied Mathematics | 2013 | 12 Pages |
Abstract
The problem of reconstructing a special class of binary images from their horizontal and vertical projections is considered. We present a general framework for analyzing the worst case complexity of this task if the image consists of more than one pairwise disjoint component. Applying the presented technique we analyze the complexity of reconstructing canonical hv-convex binary images. We also present parameterized complexity results on general and so-called glued hv-convex images. Moreover, we study how our results are related to the reconstruction of permutation matrices from four projections.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Péter Balázs,