X-rays characterizing some classes of discrete sets

In this paper, we study the problem of determining discrete sets by means o f their X-rays. An X-ray of a discrete set F in a direction u counts the nu mber 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 determi ned 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; Combinato rial Mathematics, The Carus Mathematical Monographs, No. 14, The Mathematic al 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 polyomin oes. If the horizontal and vertical directions belong to U and U's cross ra tio is not in {4/3, 3/2, 2, 3, 4}, we believe that U characterizes the clas s of hv-convex polyominoes. We give experimental evidence to support our co njecture. Moreover, we prove that there is no number 3 such that, if \U\ gr eater than or equal to 8, then U characterizes the hv-convex polyominoes. T his number exists for convex sets and is equal to 7 (see [Trans. Amer, Math . Soc. 349 (1997) 2271]). (C) 2001 Elsevier Science Inc. All rights reserve d.