Further steps on the reconstruction of convex polyominoes from orthogonal projections
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 p...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | , , , |
| Published: |
2021
|
| Subjects: | |
| Online Access: | https://dspaceusad7.4science.cloud/handle/123456789/1233 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1857415064349310976 |
|---|---|
| author | Tarsissi, Lama |
| author2 | Dulio, Pablo Frosini, Andrea Rinaldi, Simone Vuillon, Laurent |
| author2_role | author author author author |
| author_facet | Tarsissi, Lama Dulio, Pablo Frosini, Andrea Rinaldi, Simone Vuillon, Laurent |
| author_role | author |
| dc.creator.none.fl_str_mv | Tarsissi, Lama Dulio, Pablo Frosini, Andrea Rinaldi, Simone Vuillon, Laurent |
| dc.date.none.fl_str_mv | 2021-12-19T11:57:31Z 2021-12-19T11:57:31Z 2022 |
| dc.format.none.fl_str_mv | application/pdf |
| dc.identifier.none.fl_str_mv | 10.1007/s10878-021-00751-z https://dspaceusad7.4science.cloud/handle/123456789/1233 10.1007/s10878-021-00751-z |
| dc.language.none.fl_str_mv | en |
| dc.relation.none.fl_str_mv | Journal of Combinatorial Optimization 1382-6905 |
| dc.subject.none.fl_str_mv | Digital convexity Discrete geometry Discrete tomography Reconstruction problem |
| dc.title.none.fl_str_mv | Further steps on the reconstruction of convex polyominoes from orthogonal projections |
| dc.type.none.fl_str_mv | Controlled Vocabulary for Resource Type Genres::text::periodical::journal::contribution to journal::journal article |
| description | 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–347, 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> |
| id | sorbonner_136322d78d745c8e8b293f9d3bbcd047 |
| identifier_str_mv | 10.1007/s10878-021-00751-z |
| language_invalid_str_mv | en |
| network_acronym_str | sorbonner |
| network_name_str | Sorbonne University Abu Dhabi repository |
| oai_identifier_str | oai:depot.sorbonne.ae:20.500.12458/1233 |
| publishDate | 2021 |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | Further steps on the reconstruction of convex polyominoes from orthogonal projectionsTarsissi, LamaDulio, PabloFrosini, AndreaRinaldi, SimoneVuillon, LaurentDigital convexityDiscrete geometryDiscrete tomographyReconstruction problemA 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–347, 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>2021-12-19T11:57:31Z2021-12-19T11:57:31Z2022Controlled Vocabulary for Resource Type Genres::text::periodical::journal::contribution to journal::journal articleapplication/pdf10.1007/s10878-021-00751-zhttps://dspaceusad7.4science.cloud/handle/123456789/123310.1007/s10878-021-00751-zenJournal of Combinatorial Optimization1382-6905oai:depot.sorbonne.ae:20.500.12458/12332024-09-11T11:01:09Z |
| spellingShingle | Further steps on the reconstruction of convex polyominoes from orthogonal projections Tarsissi, Lama Digital convexity Discrete geometry Discrete tomography Reconstruction problem |
| title | Further steps on the reconstruction of convex polyominoes from orthogonal projections |
| title_full | Further steps on the reconstruction of convex polyominoes from orthogonal projections |
| title_fullStr | Further steps on the reconstruction of convex polyominoes from orthogonal projections |
| title_full_unstemmed | Further steps on the reconstruction of convex polyominoes from orthogonal projections |
| title_short | Further steps on the reconstruction of convex polyominoes from orthogonal projections |
| title_sort | Further steps on the reconstruction of convex polyominoes from orthogonal projections |
| topic | Digital convexity Discrete geometry Discrete tomography Reconstruction problem |
| url | https://dspaceusad7.4science.cloud/handle/123456789/1233 |