X-rays characterizing some classes of discrete sets

• Published in: Linear algebra and its applications 2001-12, Vol.339 (1), p.3-21
• Main Authors: Barcucci, Elena, Del Lungo, Alberto, Nivat, Maurice, Pinzani, Renzo
• Format: Article
• Language: English
• Subjects: Biological and medical sciences; Computational geometry; Convex polyominoes; Convex sets and geometric inequalities; Discrete tomography; Exact sciences and technology; Geometry, differential geometry, and topology; Investigative techniques, diagnostic techniques (general aspects); Logic, set theory, and algebra; Mathematical methods in physics; Medical sciences; Miscellaneous. Technology; Pathology. Cytology. Biochemistry. Spectrometry. Miscellaneous investigative techniques; Physics; Set theory; X-ray imaging
• ISSN: 0024-3795; 1873-1856
• DOI: 10.1016/S0024-3795(01)00431-1

In this paper, we study the problem of determining discrete sets by means of their X-rays. An X-ray of a discrete set F in a direction u counts the number of points in F on each line parallel to u. A class F of discrete sets is characterized by the set U of directions if each element in F is determined by its X-rays in the directions of U. By using the concept of switching component introduced by Chang and Ryser [Comm. ACM 14 (1971) 21; Combinatorial Mathematics, The Carus Mathematical Monographs, No. 14, The Mathematical Association of America, Rahway, 1963] and extended in [Discrete Comput. Geom. 5 (1990) 223], we prove that there are some classes of discrete sets that satisfy some connectivity and convexity conditions and that cannot be characterized by any set of directions. Gardner and Gritzmann [Trans. Amer. Math. Soc. 349 (1997) 2271] show that any set U of four directions having cross ratio that does not belong to {4/3,3/2,2,3,4}, characterizes the class of convex sets. We prove the converse, that is, if U's cross ratio is in {4/3,3/2,2,3,4}, then the hv-convex sets cannot be characterized by U. We show that if the horizontal and vertical directions do not belong to U, Gardner and Gritzmann's result cannot be extended to hv-convex polyominoes. If the horizontal and vertical directions belong to U and U's cross ratio is not in {4/3,3/2,2,3,4}, we believe that U characterizes the class of hv-convex polyominoes. We give experimental evidence to support our conjecture. Moreover, we prove that there is no number δ such that, if | U|⩾ δ, then U characterizes the hv-convex polyominoes. This number exists for convex sets and is equal to 7 (see [Trans. Amer. Math. Soc. 349 (1997) 2271]).