Reconstructing hv-convex polyominoes from orthogonal projections

被引：69
作者：
Chrobak, M [1 ]
Dürr, C
机构：
[1] Univ Calif Riverside, Dept Comp Sci, Riverside, CA 92521 USA
[2] Int Comp Sci Inst, Berkeley, CA 94704 USA
来源：
INFORMATION PROCESSING LETTERS | 1999年 / 69卷 / 06期
基金：
美国国家科学基金会;
关键词：
combinatorial problems; discrete tomography; polyominoes;
D O I：
10.1016/S0020-0190(99)00025-3
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
We address the problem of reconstructing a discrete 2D object, represented by a set of grid cells, from its orthogonal projections. We focus on objects called hv-convex polyominoes, which are connected objects with the property that the cells in each row and column are consecutive. The main result of this paper is a simple, O(mn min(m(2), n(2)))-time algorithm for reconstructing hv-convex polyominoes. (C) 1999 Elsevier Science B.V. kll rights reserved.
引用
收藏
页码：283 / 289
页数：7
相关论文
共 38 条
1234