Name
Abstract | ||
|---|---|---|
In this paper, we consider the problem of reconstructing polyominoes from information about the thickness in vertical and horizontal directions. We focus on the case where there are multiple disjoint polyominoes (of different colours) that are hv-convex, i.e., any intersection with a horizontal or vertical line is contiguous. We show that reconstruction of such polyominoes is polynomial if the number of colours is constant, but NP-hard for an unbounded number of colours. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1016/j.tcs.2010.04.041 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
Theory of computation,Combinatorial problems,Algorithms,multiple disjoint polyominoes,Computational geometry,Discrete tomography,different colour,hv-convex multi-coloured polyominoes,vertical line,unbounded number,horizontal direction | Journal | 411 |
Issue | ISSN | Citations |
34-36 | Theoretical Computer Science | 0 |
PageRank | References | Authors |
0.34 | 4 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Adam Bains | 1 | 0 | 0.34 |
| Therese Biedl | 2 | 902 | 106.36 |