{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T11:37:13Z","timestamp":1774352233319,"version":"3.50.1"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,5,12]],"date-time":"2021-05-12T00:00:00Z","timestamp":1620777600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,5,12]],"date-time":"2021-05-12T00:00:00Z","timestamp":1620777600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A remarkable family of discrete sets which has recently attracted the attention of the discrete geometry community is the family of convex polyominoes, that are the discrete counterpart of Euclidean convex sets, and combine the constraints of convexity and connectedness. In this paper we study the problem of their reconstruction from orthogonal projections, relying on the approach defined by Barcucci et al. (Theor Comput Sci 155(2):321\u2013347, 1996). In particular, during the reconstruction process it may be necessary to expand a convex subset of the interior part of the polyomino, say the polyomino kernel, by adding points at specific positions of its contour, without losing its convexity. To reach this goal we consider convexity in terms of certain combinatorial properties of the boundary word encoding the polyomino. So, we first show some conditions that allow us to extend the kernel maintaining the convexity. Then, we provide examples where the addition of one or two points causes a loss of convexity, which can be restored by adding other points, whose number and positions cannot be determined a priori.<\/jats:p>","DOI":"10.1007\/s10878-021-00751-z","type":"journal-article","created":{"date-parts":[[2021,5,12]],"date-time":"2021-05-12T05:02:30Z","timestamp":1620795750000},"page":"2423-2442","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Further steps on the reconstruction of convex polyominoes from orthogonal projections"],"prefix":"10.1007","volume":"44","author":[{"given":"Paolo","family":"Dulio","sequence":"first","affiliation":[]},{"given":"Andrea","family":"Frosini","sequence":"additional","affiliation":[]},{"given":"Simone","family":"Rinaldi","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1932-4676","authenticated-orcid":false,"given":"Lama","family":"Tarsissi","sequence":"additional","affiliation":[]},{"given":"Laurent","family":"Vuillon","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,5,12]]},"reference":[{"key":"751_CR1","first-page":"433","volume":"2008","author":"P Balazs","year":"2008","unstructured":"Balazs P, Gara M (2008) Decision trees in binary tomography for supporting the reconstruction of hv-convex connected images. ACIVS 2008:433\u2013443","journal-title":"ACIVS"},{"issue":"2","key":"751_CR2","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1016\/0304-3975(94)00293-2","volume":"155","author":"E Barcucci","year":"1996","unstructured":"Barcucci E, Del Lungo A, Nivat M, Pinzani R (1996) Reconstructing convex polyominoes from horizontal and vertical projections. Theor Comput Sci 155(2):321\u2013347","journal-title":"Theor Comput Sci"},{"key":"751_CR3","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0024-3795(01)00431-1","volume":"339","author":"E Barcucci","year":"2001","unstructured":"Barcucci E, Del Lungo A, Nivat M, Pinzani R (2001) X-rays characterizing some classes of discrete sets. Linear Algebra Appl. 339:3\u201321","journal-title":"Linear Algebra Appl."},{"issue":"1\u20132","key":"751_CR4","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/S0304-3975(96)00101-6","volume":"178","author":"J Berstel","year":"1997","unstructured":"Berstel J, de Luca A (1997) Sturmian words, Lyndon words and trees. Theor Comput Sci 178(1\u20132):171\u2013203","journal-title":"Theor Comput Sci"},{"key":"751_CR5","doi-asserted-by":"crossref","unstructured":"Berstel J, Lauve A, Reutenauer C, Saliola F (2008) Combinatorics on words: Christoffel words and repetitions in words. Universit\u00e9 de Montr\u00e9al et American Mathematical Society 27, CRM monograph series","DOI":"10.1090\/crmm\/027"},{"key":"751_CR6","doi-asserted-by":"crossref","unstructured":"Bodini O, Jacquot A, Duchon P, Mutafchiev LR, (2013) Asymptotic analysis and random sampling of digitally convex polyominoes. In: Gonzalez-Diaz R, Jimenez MJ, Medrano B (eds) Discrete geometry for computer imagery. DGCI, Lecture notes in computer science, 7749. Springer, Berlin","DOI":"10.1007\/978-3-642-37067-0_9"},{"issue":"1","key":"751_CR7","doi-asserted-by":"publisher","first-page":"23","DOI":"10.5802\/jtnb.77","volume":"5","author":"JP Borel","year":"1993","unstructured":"Borel JP, Laubie F (1993) Quelques mots sur la droite projective re\u00e9lle. J. Th\u00e9or. Nombres Bordeaux 5(1):23\u201351","journal-title":"J. Th\u00e9or. Nombres Bordeaux"},{"key":"751_CR8","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/978-3-319-32360-2_7","volume":"9647","author":"S Brlek","year":"2016","unstructured":"Brlek S, Frosini A (2016) A tomographical interpretation of a sufficient condition for h-graphical sequences. Lect Notes Comput Sci 9647:95\u2013104","journal-title":"Lect Notes Comput Sci"},{"key":"751_CR9","doi-asserted-by":"publisher","first-page":"2239","DOI":"10.1016\/j.patcog.2008.11.010","volume":"42\u201310","author":"S Brlek","year":"2009","unstructured":"Brlek S, Lachaud J-O, Proven\u00e7al X, Reutenauer C (2009) Lyndon + Christoffel=digitally convex. Pattern Recognit 42\u201310:2239\u20132246","journal-title":"Pattern Recognit"},{"key":"751_CR10","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/0024-3795(80)90105-6","volume":"33","author":"RA Brualdi","year":"1980","unstructured":"Brualdi RA (1980) Matrices of zeros and ones with fixed row and column sum vectors. Linear Algebra Appl 33:159\u2013231","journal-title":"Linear Algebra Appl"},{"key":"751_CR11","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/S0024-3795(01)00435-9","volume":"339","author":"S Brunetti","year":"2001","unstructured":"Brunetti S, Del Lungo A, Del Ristoro F, Kuba A, Nivat M (2001) Reconstruction of 4- and 8-connected convex discrete sets from row and column projections. Linear Algebra Appl 339:37\u201357","journal-title":"Linear Algebra Appl"},{"key":"751_CR12","doi-asserted-by":"crossref","unstructured":"Brunetti S, Daurat A, Kuba A (2006) Fast filling operations used in the reconstruction of convex lattice sets. In: Proceedings of the DGCI 2006, lecture notes in Comp. Sci. 4245, pp 98\u2013109","DOI":"10.1007\/11907350_9"},{"key":"751_CR13","first-page":"145","volume":"6","author":"EB Christoffel","year":"1875","unstructured":"Christoffel EB (1875) Observatio arithmetica. Ann Mat Pura Appl 6:145\u2013152","journal-title":"Ann Mat Pura Appl"},{"issue":"1\u20133","key":"751_CR14","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/S0012-365X(96)00355-X","volume":"177","author":"WF Chuan","year":"1997","unstructured":"Chuan WF (1997) $$\\alpha $$-words and factors of characteristic sequences. Discr Math 177(1\u20133):33\u201350","journal-title":"Discr Math"},{"issue":"1","key":"751_CR15","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/S0304-3975(96)00310-6","volume":"183","author":"A de Luca","year":"1997","unstructured":"de Luca A (1997) Sturmian words: structure, combinatorics, and their arithmetics. Theor Comput Sci 183(1):45\u201382","journal-title":"Theor Comput Sci"},{"issue":"2","key":"751_CR16","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1016\/0304-3975(94)00035-H","volume":"136","author":"A de Luca","year":"1994","unstructured":"de Luca A, Mignosi F (1994) Some combinatorial properties of Sturmian words. Theor Comput Sci 136(2):361\u2013385","journal-title":"Theor Comput Sci"},{"key":"751_CR17","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/S0012-365X(96)83007-X","volume":"157","author":"A Del Lungo","year":"1996","unstructured":"Del Lungo A, Nivat M, Pinzani R (1996) The number of convex polyominoes reconstructible from their orthogonal projections. Discr Math 157:65\u201378","journal-title":"Discr Math"},{"issue":"12","key":"751_CR18","doi-asserted-by":"publisher","first-page":"125011","DOI":"10.1088\/0266-5611\/31\/12\/125011","volume":"31","author":"P Dulio","year":"2015","unstructured":"Dulio P, Frosini A, Pagani SM (2015) A geometrical characterization of regions of uniqueness and applications to discrete tomography. Inverse Probl 31(12):125011","journal-title":"Inverse Probl"},{"key":"751_CR19","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/978-3-319-32360-2_8","volume":"9647","author":"P Dulio","year":"2016","unstructured":"Dulio P, Frosini A, Pagani SM (2016) Geometrical characterization of the uniqueness regions under special sets of three directions in discrete tomography. Lect Notes Comput Sci 9647:105\u2013116","journal-title":"Lect Notes Comput Sci"},{"key":"751_CR20","doi-asserted-by":"crossref","unstructured":"Dulio P, Frosini A, Rinaldi S, Tarsissi L, Vuillon L (2017a) First steps in the algorithmic reconstruction of digital convex sets. Lect Notes Comput Sci 10432:164\u2013176","DOI":"10.1007\/978-3-319-66396-8_16"},{"key":"751_CR21","doi-asserted-by":"crossref","unstructured":"Dulio P, Frosini A, Pagani SM (2017b) Regions of uniqueness quickly reconstructed by three directions in discrete tomography. Fundam Inform 155:407\u2013423","DOI":"10.3233\/FI-2017-1592"},{"key":"751_CR22","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1016\/0196-6774(83)90017-2","volume":"4","author":"JP Duval","year":"1983","unstructured":"Duval JP (1983) Factorizing words over an ordered alphabet. J. Algorithms 4:363\u2013381","journal-title":"J. Algorithms"},{"key":"751_CR23","doi-asserted-by":"crossref","unstructured":"Eckhardt U (2001) Digital lines and digital convexity. Digital and Image Geometry, Advanced Lectures, Lecture Notes in Computer Science 2243:209\u2013228","DOI":"10.1007\/3-540-45576-0_13"},{"key":"751_CR24","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1090\/S0002-9939-1965-0174934-9","volume":"16","author":"NJ Fine","year":"1965","unstructured":"Fine NJ, Wilf HS (1965) Uniqueness theorems for periodic functions. Proc AMS 16:109\u2013114","journal-title":"Proc AMS"},{"key":"751_CR25","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1109\/TEC.1961.5219197","volume":"2","author":"H Freeman","year":"1961","unstructured":"Freeman H (1961) On the encoding of arbitrary geometric configurations. IRE Trans Electron Comput 2:260\u2013268","journal-title":"IRE Trans Electron Comput"},{"key":"751_CR26","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1007\/978-3-642-37067-0_26","volume":"7749","author":"A Frosini","year":"2013","unstructured":"Frosini A, Picouleau C, Rinaldi S (2013) On the degree sequences of uniform hypergraphs. Lect Notes Comput Sci 7749:300\u2013311","journal-title":"Lect Notes Comput Sci"},{"key":"751_CR27","doi-asserted-by":"publisher","first-page":"1073","DOI":"10.2140\/pjm.1957.7.1073","volume":"7","author":"D Gale","year":"1957","unstructured":"Gale D (1957) A theorem on flows in networks. Pacif J Math. 7:1073\u20131082","journal-title":"Pacif J Math."},{"key":"751_CR28","doi-asserted-by":"publisher","first-page":"2271","DOI":"10.1090\/S0002-9947-97-01741-8","volume":"349","author":"RJ Gardner","year":"1997","unstructured":"Gardner RJ, Gritzmann P (1997) Discrete tomography: determination of finite sets by x-rays. Tran Am Math Soc 349:2271\u20132295","journal-title":"Tran Am Math Soc"},{"issue":"1\u20133","key":"751_CR29","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/S0012-365X(98)00347-1","volume":"202","author":"RJ Gardner","year":"1999","unstructured":"Gardner RJ, Gritzmann P, Prangenberg D (1999) On the computational complexity of reconstructing lattice sets from their X-rays. Discr Math 202(1\u20133):45\u201371","journal-title":"Discr Math"},{"key":"751_CR30","doi-asserted-by":"crossref","unstructured":"G\u0229bala M (1998) The reconstruction of convex polyominoes from horizontal and vertical projections. In: Proceedings of the SOFSEM 98. Lecture Notes in Comp. Sci., vol 1521, pp 350\u2013359","DOI":"10.1007\/3-540-49477-4_27"},{"key":"751_CR31","unstructured":"G\u00e9rard Y (2017) About the complexity of reconstructing convex lattice sets from horizontal and vertical X-rays. In: Communication at the $$11^{st}$$ edition of the meeting. Tomography and applications\u2014discrete tomography and image reconstruction, Milan, May 15\u201317"},{"issue":"4","key":"751_CR32","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1016\/0020-0190(72)90045-2","volume":"1","author":"RL Graham","year":"1972","unstructured":"Graham RL (1972) An efficient algorithm for determining the convex hull of a finite planar set. Inf Process Lett 1(4):132\u2013133","journal-title":"Inf Process Lett"},{"key":"751_CR33","doi-asserted-by":"crossref","unstructured":"Guttmann AJ (2009) Polygons, polyominoes and polycubes. Springer. Lecture Notes in Physics 775","DOI":"10.1007\/978-1-4020-9927-4"},{"issue":"3","key":"751_CR34","doi-asserted-by":"publisher","first-page":"1189","DOI":"10.1016\/j.disc.2015.10.043","volume":"339","author":"L Hegedus","year":"2016","unstructured":"Hegedus L, Nagy B (2016) On periodic properties of circular words. Discr Math 339(3):1189\u20131197","journal-title":"Discr Math"},{"key":"751_CR35","volume-title":"Discrete tomography: foundations algorithms and applications","year":"1999","unstructured":"Herman GT, Kuba A (eds) (1999) Discrete tomography: foundations algorithms and applications. Birkhauser, Boston"},{"key":"751_CR36","volume-title":"Advances in discrete tomography and its applications (applied and numerical harmonic analysis)","year":"2007","unstructured":"Herman GT, Kuba A (eds) (2007) Advances in discrete tomography and its applications (applied and numerical harmonic analysis). Birkhauser, Boston"},{"key":"751_CR37","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1137\/S0097539790191010","volume":"23","author":"RW Irving","year":"1994","unstructured":"Irving RW, Jerrum MR (1994) Three-dimensional statistical data security problems. SIAM J Comput 23:170\u2013184","journal-title":"SIAM J Comput"},{"key":"751_CR38","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511566097","volume-title":"Combinatorics on words. Cambridge mathematical library","author":"M Lothaire","year":"1997","unstructured":"Lothaire M (1997) Combinatorics on words. Cambridge mathematical library. Cambridge University Press, Cambridge"},{"key":"751_CR39","doi-asserted-by":"publisher","first-page":"532","DOI":"10.1109\/42.511756","volume":"15","author":"GPM Prause","year":"1996","unstructured":"Prause GPM, Onnasch DGW (1996) Binary reconstruction of the heart chambers from biplane angiographic image sequence. IEEE Trans Med Imaging 15:532\u2013559","journal-title":"IEEE Trans Med Imaging"},{"key":"751_CR40","doi-asserted-by":"crossref","unstructured":"Ryser H (1963) Combinatorial mathematics, The Carus Mathematical Monographs 14, Math. Assoc. America","DOI":"10.5948\/UPO9781614440147"},{"key":"751_CR41","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/0031-3203(78)90004-3","volume":"10","author":"AR Shliferstein","year":"1978","unstructured":"Shliferstein AR, Chien YT (1978) Switching components and the ambiguity problem in the reconstruction of pictures from their projections. Pattern Recognit 10:327\u2013340","journal-title":"Pattern Recognit"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00751-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-021-00751-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00751-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,14]],"date-time":"2022-10-14T20:18:24Z","timestamp":1665778704000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-021-00751-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,12]]},"references-count":41,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["751"],"URL":"https:\/\/doi.org\/10.1007\/s10878-021-00751-z","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,5,12]]},"assertion":[{"value":"24 April 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 May 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}