1,721,064 research outputs found
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
The NP-Completeness of a Tomographical problem on bicolorede domino tilings
No full textIn this paper we study the problem of reconstructing a bicolored domino tiling of a rectangular
surface from its horizontal and vertical projections. We use a reduction from the NP-complete
problem NUMERICAL MATCHING WITH TARGET SUMS in order to prove that, unless P = NP,
this task cannot be performed in polynomial time. The reconstruction of monochromatic domino
tilings is still open
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
Square involutions
No full textA square involution is a square permutation which is also an involution. In this paper we give the enumeration of square involutions, using purely combinatorial methods, by establishing a bijective correspondence with a class of lattice paths. As a corollary to our result, we enumerate various subclasses of square involutions, including the classes of triangular, decomposable, and fat involutions
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
Enumeration of L-convex polyominoes by rows and columns
Full text linkIn this paper, we consider the class of L-convex polyominoes, i.e. the convex polyominoes in which
any two cells can be connected by a path of cells in the polyomino that switches direction between
the vertical and the horizontal at most once.
Using the ECO method, we prove that the number fn of L-convex polyominoes with perimeter
2(n+2) satisfies the rational recurrence relation fn =4fn-1 -2fn-2, with f0 =1, f1 =2, f2 =7.
Moreover, we give a combinatorial interpretation of this statement. In the last section, we present
some open problem
A reconstruction algorithm for a subclass of instances of the 2-color problem
No full textIn the field of Discrete Tomography, the 2-color problem consists in reconstructing a matrix whose elements are of two different types, starting from its horizontal and vertical projections. It is known that the 1-color problem admits a polynomial time reconstruction algorithm, while the c-color problem, with c ≥ 2, is NP-hard. Thus, the 2-color problem constitutes an interesting example of a problem just in the frontier between hard and easy problems.
In this paper we define a linear time algorithm (in the size of the output matrix) to solve a subclass of its instances, where some values of the horizontal and vertical projections are constant, while the others are upper bounded by a positive number proportional to the dimension of the problem. Our algorithm relies on classical studies for the solution of the 1-color problem
A decomposition theorem for homogeneous sets with respect to diamond probes
No full textAn unknown planar discrete set of points A can be inspected by means of a probe P of generic shape that moves around it, and reveals, for each position, the number of its elements as a magnifying glass. All the data collected during this process can be naturally arranged in an integer matrix that we call the scan of the starting set A w.r.t. the probe P. In [10], Nivat conjectured that a discrete set whose scan w.r.t. an exact probe is k-homogeneous, shows a strong periodical behavior, and it can be decomposed into smaller 1-homogeneous subsets. In this paper, we prove this conjecture to be true when the probe is a diamond, and then we extend this result to exact polyominoes that can regarded as balls in a generalized L-1 norm of Z(2). Then we provide experimental evidence that the conjecture holds for each exact polyomino of small dimension, using the mathematical software Sage [13]. Finally, we give some hints to solve the related reconstruction problem
- …
