Abstract
The problem of reconstructing a discrete set from its horizontal and vertical projections (RSP) is of primary importance in many different problems for example pattern recognition, image processing and data compression.
We give a new algorithm which provides a reconstruction of convex polyominoes from horizontal and vertical projections. It costs atmost O(min(m; n)2 • mnlogmn) for a matrix that has m x n cells. In this paper we provide just a sketch of the algorithm.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Barcucci, E., Del Lungo, A., Nivat, M., Pinzani, R.: Reconstructing convex polyominoes from horizontal and vertical projections. Theor. Comp. Sci. 155 (1996) 321–347
Barcucci, E., DelLungo, A., Nivat, M., Pinzani R.: Reconstructing convex polyominoes from horizontal and vertical projections II. (1996) Preprint
Chang, S.K.: The reconstruction of binary patterns from their projections. Comm. ACM 14 (1971) 21–25
Ryser, H.: Combinatorial Mathematics. The Carus Mathematical Monographs Vol. 14 (The Mathematical Association of America, Rahway, 1963)
Wang, X.G.: Characterisation of binary patterns and their projections. IEEE Trans. Comput. C-24 (1975) 1032–1035.
Woeginger, G.J.: The reconstruction of polyominoes from their orthogonal projections. (1996) Preprint.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
GÇebala, M. (1998). The Reconstruction of Convex Polyominoes from Horizontal and Vertical Projections. In: Rovan, B. (eds) SOFSEM’ 98: Theory and Practice of Informatics. SOFSEM 1998. Lecture Notes in Computer Science, vol 1521. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-49477-4_27
Download citation
DOI: https://doi.org/10.1007/3-540-49477-4_27
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65260-1
Online ISBN: 978-3-540-49477-5
eBook Packages: Springer Book Archive