1,720,978 research outputs found
Integer orbits in rectangular lattice billiards
Full text linkIn this paper we consider rectangular billiard tables having vertices with integer coordinates, and side lengths equal to integer multiples of the norms of the side directions. We also assume that all the bouncing points of a billiard ball are constrained to belong to the integer lattice Z2. We address several questions concerning combinatorial and geometric properties of the allowed orbits, that, due to the integer constraint, are called integer orbits. We give a complete classification of integer orbits, and the parameters contributing to their structure are precisely determined. This leads to understand how the orbit fills the lattice billiard before it really propagates. In particular, one can characterize the trajectories that reach a billiard pocket, as well as all the closed orbits, by the simple knowledge of the size of the billiard table, and of the starting moving direction. The characterization bases on the explicit determination of the numerical sequences corresponding to clockwise, and counterclockwise, bouncing. We also investigate the geometrical structure of an allowed orbit in terms of special sub-patterns, called Z-paths, pointing out the allowed lengths of different Z-paths in a same orbit. This is of independent interest, and is related to the configurations known as switching components, that play a crucial role in discrete tomography, and in problems concerning image reconstruction
Characterization of hv-Convex Sequences
Full text linkReconstructing a discrete object by means of X-rays along a finite set U of (discrete) directions represents one of the main task in discrete tomography. Indeed, it is an ill-posed inverse problem, since different structures exist having the same projections along all lines whose directions range in U. Characteristic of ambiguous reconstructions are special configurations, called switching components, whose understanding represents a main issue in discrete tomography, and an independent interesting geometric problem as well. The investigation of switching component usually bases on some kind of prior knowledge that is incorporated in the tomographic problem. In this paper, we focus on switching components under the constraint of convexity along the horizontal and the vertical directions imposed to the unknown object. Moving from their geometric characterization in windows and curls, we provide a numerical description, by encoding them as special sequences of integers. A detailed study of these sequences leads to the complete understanding of their combinatorial structure, and to a polynomial-time algorithm that explicitly reconstructs any of them from a pair of integers arbitrarily given
Generalization of Heron’s and Brahmagupta’s equalities to any cyclic polygon
Full text linkIt is well known that Heron’s equality provides an explicit formula for the area of a triangle, as a symmetric function of the lengths of its edges. It has been extended by Brahmagupta to quadrilaterals inscribed in a circle (cyclic quadrilaterals). A natural problem is trying to further generalize the result to cyclic polygons with a larger number of edges. Surprisingly, this has proved to be far from simple, and no explicit solutions exist for cyclic polygons having n> 4 edges. In this paper we investigate such a problem by following a new and elementary approach, based on the idea that the simple geometry underlying Heron’s and Brahmagupta’s equalities hides the real players of the game. In details, we propose to focus on the dissection of the edges determined by the incircles of a suitable triangulation of the cyclic polygon, showing that this approach leads to an explicit formula for the area as a symmetric function of the lengths of these segments. We also show that such a symmetry can be rediscovered in Heron’s and Brahmagupta’s results, which consequently represent special cases of the provided general equality
On Some Geometric Aspects of the Class of hv-Convex Switching Components
No full textIn the usual aim of discrete tomography, the reconstruction of an unknown discrete set is considered, by means of projection data collected along a set U of discrete directions. Possible ambiguous reconstructions can arise if and only if switching components occur, namely, if and only if non-empty images exist having null projections along all the directions in U. In order to lower the number of allowed reconstructions, one tries to incorporate possible extra geometric constraints in the tomographic problem, such as the request for connectedness, or some reconstruction satisfying special convexity constraints. In particular, the class P of horizontally and vertically convex connected sets (briefly, hv-convex polyominoes) has been largely considered. In this paper we introduce the class of hv-convex switching components, and prove some preliminary results on their geometric structure. The class includes all switching components arising when the tomographic problem is considered in P, which highly motivates the investigation of such configurations, also in view of possible uniqueness results for hv-convex polyominoes. It turns out that the considered class can be partitioned into two disjointed subclasses of closed patterns, called windows and curls, respectively, according to whether the pattern can be travelled by turning always clockwise (or always counterclockwise), or whether points with different turning directions exist. It follows that all windows have a unique representation, while curls consist of interlaced sequences of sub-patterns, called Z-paths, which leads to the problem of understanding the combinatorial structure of such sequences. We provide explicit constructions of families of curls associated to some special sequences, and also give additional details on further allowed or forbidden configurations by means of a number of illustrative examples
Erratum to “A rounding theorem for unique binary tomographic reconstruction” [Discrete Appl. Math. 268 (2019) 54–69, (S0166218X19302562), (10.1016/j.dam.2019.05.005)]
No full textWe correct an error occurred in Lemma 10, and a couple of typos in the following paper P. Dulio, S.M.C. Pagani A rounding theorem for unique binary tomographic reconstruction, Discrete Appl. Math. 268 (2019) 54–69. The corrections do not alter anyone of the obtained results
A Graphlet-Based Topological Characterization of the Resting-State Network in Healthy People
Full text linkIn this paper, we propose a graphlet-based topological algorithm for the investigation of the brain network at resting state (RS). To this aim, we model the brain as a graph, where (labeled) nodes correspond to specific cerebral areas and links are weighted connections determined by the intensity of the functional magnetic resonance imaging (fMRI). Then, we select a number of working graphlets, namely, connected and non-isomorphic induced subgraphs. We compute, for each labeled node, its Graphlet Degree Vector (GDV), which allows us to associate a GDV matrix to each one of the 133 subjects of the considered sample, reporting how many times each node of the atlas "touches" the independent orbits defined by the graphlet set. We focus on the 56 independent columns (i.e., non-redundant orbits) of the GDV matrices. By aggregating their count all over the 133 subjects and then by sorting each column independently, we obtain a sorted node table, whose top-level entries highlight the nodes (i.e., brain regions) most frequently touching each of the 56 independent graphlet orbits. Then, by pairwise comparing the columns of the sorted node table in the top-k entries for various values of k, we identify sets of nodes that are consistently involved with high frequency in the 56 independent graphlet orbits all over the 133 subjects. It turns out that these sets consist of labeled nodes directly belonging to the default mode network (DMN) or strongly interacting with it at the RS, indicating that graphlet analysis provides a viable tool for the topological characterization of such brain regions. We finally provide a validation of the graphlet approach by testing its power in catching network differences. To this aim, we encode in a Graphlet Correlation Matrix (GCM) the network information associated with each subject then construct a subject-to-subject Graphlet Correlation Distance (GCD) matrix based on the Euclidean distances between all possible pairs of GCM. The analysis of the clusters induced by the GCD matrix shows a clear separation of the subjects in two groups, whose relationship with the subject characteristics is investigated
Uniqueness and reconstruction of finite lattice sets from their line sums
No full textIf an unknown finite set C⊂Z2 is cut by lines parallel to given directions, then one may count the number of points of C that are intercepted by each line, that is, the projections of C in the given directions. The inverse problem consists in reconstructing the set C, interpreted as a binary image, from the knowledge of its projections. In general, this challenging combinatorial problem, also related to the tomographic reconstruction of an unknown homogeneous object by means of X-rays, is ill-posed, meaning that different binary images exist that match the available projections. Therefore, as a preliminary step, one can try to find conditions to be imposed on the considered directions in order to limit the number of allowed solutions. In this paper we address the above problems for sets C contained in a finite assigned lattice grid, and generalize some results known in literature. First, we describe special sets of lattice directions, called simple cycles, and focus on some of their properties. Then we prove that uniqueness of reconstruction for binary images is guaranteed if and only if the line sums are computed along suitable simple cycles having even cardinality. As a second item, we prove that the unique binary solution can be explicitly reconstructed from a real-valued solution having minimal Euclidean norm. This leads to an explicit reconstruction algorithm, tested on four different phantoms and compared with previous results, which points out a significant improvement of the corresponding performance
Further steps on the reconstruction of convex polyominoes from orthogonal projections
Full text linkA 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
Ambiguous reconstructions of hv-convex polyominoes
No full textThe core problem of discrete tomography, i.e., the faithful reconstruction of an unknown discrete object from projections along a given set of directions, is ill-posed in general. When further constraints are imposed on the object or on the employed directions, uniqueness of the reconstruction can be obtained. It is the case, for example, of convex lattice sets in Z2, for which a theorem by Gardner and Gritzmann assures the faithful reconstruction when suitable sets of directions are considered. It was conjectured that a similar result holds for the class of hv-convex polyominoes. In this paper we are concerned with this conjecture, providing new 4-tuples of discrete directions that do not lead to a unique reconstruction of hv-convex polyominoes, underlining the relevant structural difference with the class of convex sets. Our result is based on the recursive definition of new hv-convex switching components on discrete sets along four directions
- …
