Reconstructing convex polyominoes from horizontal and vertical projections

DOI10.1016/0304-3975(94)00293-2zbMath0872.68134MaRDI QIDQ672143

Elena Barcucci, Renzo Pinzani, Maurice Nivat, Alberto del Lungo

Publication date: 27 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(94)00293-2

zbMATH Keywords

pattern recognition; image processing; data compression; numerical matching with target sums problem; Reconstructing discrete bidimensional sets

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R05: Combinatorics in computer science

68T10: Pattern recognition, speech recognition

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

05B50: Polyominoes

Related Items

Discrete tomography: Determination of finite sets by X-rays, DISCRETE TOMOGRAPHIC RECONSTRUCTION OF BINARY IMAGES WITH DISJOINT COMPONENTS USING SHAPE INFORMATION, Approximating hv-Convex Binary Matrices and Images from Discrete Projections, Reconstruction of domino tiling from its two orthogonal projections, X-rays characterizing some classes of discrete sets, Comparison of algorithms for reconstructing \(hv\)-convex discrete sets, Reconstruction of 4- and 8-connected convex discrete sets from row and column projections, On the computational complexity of reconstructing three-dimensional lattice sets from their two-dimensional \(X\)-rays, An algorithm for discrete tomography, Two-view ``cylindrical decomposition of binary images, Reconstructing convex matrices by integer programming approaches, Complexity results for reconstructing binary images with disjoint components from horizontal and vertical projections, Minimal non-convex words, Polyominoes simulating arbitrary-neighborhood zippers and tilings, Binary matrices under the microscope: A tomographical problem, A framework for generating some discrete sets with disjoint components by using uniform distributions, Reconstruction of binary matrices under fixed size neighborhood constraints, Reconstruction of convex lattice sets from tomographic projections in quartic time, Scanning integer matrices by means of two rectangular windows, A benchmark set for the reconstruction of \(hv\)-convex discrete sets, Complexity results for the horizontal bar packing problem, Solving nonograms by combining relaxations, Numerical characterization of \(n\)-cube subset partitioning, On the computational complexity of reconstructing lattice sets from their \(X\)-rays, Polyominoes defined by their vertical and horizontal projections, Reconstructing \((h,v)\)-convex \(2\)-dimensional patterns of objects from approximate horizontal and vertical projections., An algorithm reconstructing convex lattice sets., The reconstruction of polyominoes from their orthogonal projections, Reconstruction of convex 2D discrete sets in polynomial time, Basic analytic combinatorics of directed lattice paths, A short scientific biography of Maurice Nivat, Reconstructing \(hv\)-convex polyominoes from orthogonal projections, Determination of Q-convex sets by X-rays, Reconstruction of 8-connected but not 4-connected \(hv\)-convex discrete sets, Algorithms for polyominoes based on the discrete Green theorem, Detection of the discrete convexity of polyominoes, Reconstruction of hv-convex sets by their coordinate X-ray functions, A network flow algorithm for reconstructing binary images from discrete X-rays, A reconstruction algorithm for L-convex polyominoes., An evolutionary algorithm for discrete tomography, Optimization and reconstruction of \(hv\)-convex (0,1)-matrices, An introduction to periodical discrete sets from a tomographical perspective, Random generation of \(Q\)-convex sets, In memoriam: Alberto Del Lungo (1965--2003), The discrete Green theorem and some applications in discrete geometry, Reconstruction of convex polyominoes from orthogonal projections of their contours, A simulated annealing for reconstructing hv-convex binary matrices, Discrete Q-Convex Sets Reconstruction from Discrete Point X-Rays, Optimization and reconstruction of hv-convex (0,1)-matrices, An experimental study of the stability problem in discrete tomography, Reconstruction of L-convex Polyominoes, Reconstructing a binary matrix under timetabling constraints, Reconstruction of Discrete Sets from Four Projections: Strong Decomposability, Recognizable Picture Languages and Polyominoes, RECONSTRUCTION OF TWO SUBCLASSES OF 2L-CONVEX POLYOMINOES

Cites Work