Scanning integer matrices by means of two rectangular windows

被引：7

作者：

Frosini, Andrea ^{[1
]}

Nivat, Maurice ^{[3
]}

Rinaldi, Simone ^{[2
]}

机构：

[1] Univ Florence, Dipartimento Sistemi & Informat, I-50134 Florence, Italy

[2] Univ Siena, Dipartimento Sci Matemat & Informat Roberto Magar, I-53100 Siena, Italy

[3] Univ Denis Diderot 2, LIAFA, F-75251 Paris 05, France

来源：

THEORETICAL COMPUTER SCIENCE | 2008年 / 406卷 / 1-2期

关键词：

Reconstruction algorithm; Computational complexity; Projection; Rectangular scan;

D O I：

10.1016/j.tcs.2008.07.016

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

This paper deals with the reconstruction of integer matrices from rectangular scans. In particular, since the case of one rectangular scan has already been treated in a previous paper, we consider two rectangular scans, given as two integer matrices, and we investigate the existence and the possibility of reconstruction of a third binary matrix which is compatible with them. Furthermore, our inspection implies interesting side results about the number of these reconstructed matrices for different choices of the dimensions of two windows used in the input scans. (c) 2008 Elsevier B.V. All rights reserved.

引用

页码：90 / 96

页数：7

共 18 条

[1]

[Anonymous], P 6 ANN S COMP GEOM

[2] Reconstructing convex polyominoes from horizontal and vertical projections [J].

Barcucci, E ;

DelLungo, A ;

Nivat, M ;

Pinzani, R .

THEORETICAL COMPUTER SCIENCE, 1996, 155 (02) :321-347

[3]

Barcucci E, 2007, APPL NUMER HARMON AN, P333, DOI 10.1007/978-0-8176-4543-4_15

[4] Reconstruction of lattice sets from their horizontal, vertical and diagonal X-rays [J].

Barcucci, E ;

Brunetti, S ;

Del Lungo, A ;

Nivat, M .

DISCRETE MATHEMATICS, 2001, 241 (1-3) :65-78

[5]

Barcucci E, 2000, LECT NOTES COMPUT SC, V1767, P199

[6] ON TRANSLATING ONE POLYOMINO TO TILE THE PLANE [J].

BEAUQUIER, D ;

NIVAT, M .

DISCRETE & COMPUTATIONAL GEOMETRY, 1991, 6 (06) :575-592

[7] Reconstructing hv-convex polyominoes from orthogonal projections [J].

Chrobak, M ;

Dürr, C .

INFORMATION PROCESSING LETTERS, 1999, 69 (06) :283-289

[8]

Frosini A., 2005, PURE MATH APPL, V16, P251

[9] Binary matrices under the microscope: A tomographical problem [J].

Frosini, Andrea ;

Nivat, Maurice .

THEORETICAL COMPUTER SCIENCE, 2007, 370 (1-3) :201-217

[10] Discrete tomography: Determination of finite sets by X-rays [J].

Gardner, RJ ;

Gritzmann, P .

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1997, 349 (06) :2271-2295

← 1 2 →