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 条
  • [1] Reconstructing hv-convex multi-coloured polyominoes
    Bains, Adam
    Biedl, Therese
    THEORETICAL COMPUTER SCIENCE, 2010, 411 (34-36) : 3123 - 3128
  • [2] Ambiguity Results in the Characterization of hv-convex Polyominoes from Projections
    Barcucci, Elena
    Dulio, Paolo
    Frosini, Andrea
    Rinaldi, Simone
    DISCRETE GEOMETRY FOR COMPUTER IMAGERY, DGCI 2017, 2017, 10502 : 147 - 158
  • [3] Ambiguous reconstructions of hv-convex polyominoes
    Dulio, Paolo
    Frosini, Andrea
    Pagani, Silvia M. C.
    Rinaldi, Simone
    DISCRETE MATHEMATICS, 2020, 343 (10)
  • [4] An Empirical Study of Reconstructing hv-Convex Binary Matrices from Horizontal and Vertical Projections
    Ozsvar, Zoltan
    Balazs, Peter
    ACTA CYBERNETICA, 2013, 21 (01): : 149 - 163
  • [5] A Fast Algorithm for Reconstructing hv-Convex Binary Images from Their Horizontal Projection
    Hantos, Norbert
    Balazs, Peter
    ADVANCES IN VISUAL COMPUTING (ISVC 2014), PT II, 2014, 8888 : 789 - 798
  • [6] Reconstruction of convex polyominoes from orthogonal projections of their contours
    Picouleau, C
    THEORETICAL COMPUTER SCIENCE, 2005, 346 (2-3) : 439 - 454
  • [7] Reconstruction of hv-convex binary matrices from their absorbed projections
    Kuba, A
    Nagy, A
    Balogh, E
    DISCRETE APPLIED MATHEMATICS, 2004, 139 (1-3) : 137 - 148
  • [8] Reconstruction of Canonical hv-Convex Discrete Sets from Horizontal and Vertical Projections
    Balazs, Peter
    COMBINATORIAL IMAGE ANALYSIS, PROCEEDINGS, 2009, 5852 : 280 - 288
  • [9] Comparison of algorithms for reconstructing hv-convex discrete sets
    Balogh, E
    Kuba, A
    Dévényi, C
    Del Lungo, A
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2001, 339 : 23 - 35
  • [10] On the Ambiguity of Reconstructing hv-Convex Binary Matrices with Decomposable Configurations
    Balazs, Peter
    ACTA CYBERNETICA, 2008, 18 (03): : 367 - 377
1234