Reconstruction of lattice sets from their horizontal, vertical and diagonal X-rays

作     者：Barcucci, E Brunetti, S Del Lungo, A Nivat, M 

作者机构：Univ Siena Dipartimento Matemat I-53100 Siena Italy Univ Florence DSI I-50134 Florence Italy Univ Denis Diderot 2 LIAFA F-75251 Paris 05 France 

出 版 物：《DISCRETE MATHEMATICS》 (离散数学)

年 卷 期：2001年第241卷第1-3期

页      面：65-78页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：MURST 

主　　题：tomography discrete tomography combinatorial problems computational complexity polynomial-time algorithm lattice sets polyominoes 

摘      要：In this paper, we study the problem of reconstructing a lattice set from its X-rays in a finite number of prescribed directions. The problem is NIP-complete when the number of prescribed directions is greater than two. We provide a polynomial-time algorithm for reconstructing an interesting subclass of lattice sets (having some connectivity properties) from its X-rays in directions (1, 0), (0, 1) and (1, 1). This algorithm can be easily extended to contexts having more than three X-rays. (C) 2001 Elsevier Science B.V. All rights reserved.