Algorithms for Pixelwise Shape Deformations Preserving Digital Convexity
2022, Tarsisi, Lama, Kenmochi, Y, Djerroumi, H, Coeurjolly, D., Romon, P., Borel, JP
In this article, we propose algorithms for pixelwise deformations of digital convex sets preserving their convexity using the combinatorics on words to identify digital convex sets via their boundary words, namely Lyndon and Christoffel words. The notion of removable and insertable points are used with a geometric strategy for choosing one of those pixels for each deformation step. The worst-case time complexity of each deflation and inflation step, which is the atomic deformation, is also analysed.
Further steps on the reconstruction of convex polyominoes from orthogonal projections
2022, Tarsisi, Lama, Dulio, Pablo, Frosini, Andrea, Rinaldi, Simone, Vuillon, Laurent
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.
Structure and Complexity of 2-Intersection Graphs of 3-Hypergraphs
2023, Tarsissi, Lama, Kocay, William Lawrence, Di Marco, Niccoló, Frosini, Andrea, Pergola, Elisa
Given a 3-uniform hypergraph H having a set V of vertices, and a set of hyperedges T ⊂ P(V), whose elements have cardinality three each, a null labelling is an assignment of ±1 to the hyperedges such that each vertex belongs to the same number of hyperedges labelled +1 and −1. A sufficient condition for the existence of a null labelling of H (proved in Di Marco et al. Lect Notes Comput Sci 12757:282-294, 2021) is a Hamiltonian cycle in its 2-intersection graph. The notion of 2-intersection graph generalizes that of intersection graph of an (hyper)graph and extends its effectiveness. The present study first shows that this sufficient condition for the existence of a null labelling in H can not be weakened by requiring only the connectedness of the 2-intersection graph. Then some interesting properties related to their clique configurations are proved. Finally, the main result is proved, the NP-completeness of this characterization and, as a consequence, of the construction of the related 3hypergraphs.