Reconstruction of 8-connected but not 4-connected \(hv\)-convex discrete sets
type: Item
instance of: scholarly article
title: Reconstruction of 8-connected but not 4-connected \(hv\)-convex discrete sets
zbMATH Open document ID: 1071.65047
author: Péter Balázs
author: Emese Balogh
author: Attila Kuba
published in: Discrete Applied Mathematics
publication date: 2005-05-04T00:00:00Z
review text: The authors consider the reconstruction of 8-connected but not 4-connected \(hv\)-convex discrete sets from projections, which is a very important problem in discrete tomography. A new algorithm is presented with worst case complexity of \(O(mn\min\{m,n\})\) to reconstruct all sets from horizontal and vertical projections. By using in addition the diagonal projections the complexity of the algorithm can be reduced to \(O(mn)\) in which case there is a unique solution. Possible generalizations are also briefly discussed to more general classes. Numerical examples illustrate the algorithms.
reviewed by: F. Szidarovszky
Mathematics Subject Classification ID: 65F30
Mathematics Subject Classification ID: 92C55
zbMATH DE Number: 2164852
zbMATH Keywords: Discrete tomography
zbMATH Keywords: Reconstruction
zbMATH Keywords: Connected discrete set
zbMATH Keywords: algorith
zbMATH Keywords: numerical examples
MaRDI profile type: Publication
full work available at URL: j.dam.2004.09.009
OpenAlex ID: W2023898014
cites work: Discrete Geometry for Computer Imagery
cites work: Comparison of algorithms for reconstructing \(hv\)-convex discrete sets
cites work: Reconstructing convex polyominoes from horizontal and vertical projections
cites work: Matrices of zeros and ones with fixed row and column sum vectors
cites work: Reconstruction of 4- and 8-connected convex discrete sets from row and column projections
cites work: Reconstructing \(hv\)-convex polyominoes from orthogonal projections
cites work: Polyominoes defined by two vectors
cites work: The number of convex polyominoes reconstructible from their orthogonal projections
cites work: Q4524010
cites work: Discrete tomography. Foundations, algorithms, and applications
cites work: Reconstruction of convex 2D discrete sets in polynomial time
cites work: Combinatorial Properties of Matrices of Zeros and Ones
cites work: Switching components and the ambiguity problem in the reconstruction of pictures from their projections
cites work: The reconstruction of polyominoes from their orthogonal projections
DOI: 10.1016/J.DAM.2004.09.009
description: scientific article; zbMATH DE number 2164852