A Helly-Type Theorem for Line Transversals to Disjoint Unit Balls

   Abstract. Let F be a family of disjoint unit balls in R ³ . We prove that there is a Helly-number n ₀ ≤ 46 , such that if every n ₀ members of F ( | F | ≥ n ₀ ) have a line transversal, then F has a line transversal. In order to prove this we prove that if the members of F can be ordered in a way such that every 12 members of F are met by a line consistent with the ordering, then F has a line transversal. The proof also uses the recent result on geometric permutations for disjoint unit balls by Katchalski, Suri, and Zhou.     

Helly-Type Theorems for Line Transversals to Disjoint Unit Balls

We prove Helly-type theorems for line transversals to disjoint unit balls in ℝ ^d . In particular, we show that a family of n≥2d disjoint unit balls in ℝ ^d has a line transversal if, for some ordering ≺ of the balls, any subfamily of 2d balls admits a line transversal consistent with ≺. We also prove that a family of n≥4d−1 disjoint unit balls in ℝ ^d admits a line transversal if any subfamily of size 4d−1 admits a transversal. Andreas Holmsen was supported by the Research Council of Norway, prosjektnummer 166618/V30. Otfried Cheong and Xavier Goaoc acknowledge support from the French-Korean Science and Technology Amicable Relationships program (STAR).     

Line Transversals to Disjoint Balls

We prove that the set of directions of lines intersecting three disjoint balls in ℝ³ in a given order is a strictly convex subset of . We then generalize this result to n disjoint balls in ℝ ^d . As a consequence, we can improve upon several old and new results on line transversals to disjoint balls in arbitrary dimension, such as bounds on the number of connected components and Helly-type theorems.     

A Helly-Type Theorem for Hyperplane Transversals to Well-Separated Convex Sets

Let S be a finite collection of compact convex sets in \R ^d . Let D(S) be the largest diameter of any member of S . We say that the collection S is ɛ-separated if, for every 0 < k < d , any k of the sets can be separated from any other d-k of the sets by a hyperplane more than ɛ D(S)/2 away from all d of the sets. We prove that if S is an ɛ -separated collection of at least N(ɛ) compact convex sets in \R ^d and every 2d+2 members of S are met by a hyperplane, then there is a hyperplane meeting all the members of S . The number N(ɛ) depends both on the dimension d and on the separation parameter ɛ . This is the first Helly-type theorem known for hyperplane transversals to compact convex sets of arbitrary shape in dimension greater than one. Received August 10, 2000, and in revised form January 24, 2001. Online publication April 6, 2001.     

Line Transversals to Unit Disks

Abstract. We show that if every three members of a finite disjoint family of unit disks in the plane have a line transversal, then there is a line transversal to all except at most 12 disks in the family. We derive an analogous result for translates of a general compact convex set, with the constant equal to 47.     

On the Helly Number for Hyperplane Transversals to Unit Balls

We prove two results about the Hadwiger problem of finding the Helly number for line transversals of disjoint unit disks in the plane, and about its higher-dimensional generalization to hyperplane transversals of unit balls in d -dimensional Euclidean space. These consist of (a) a proof of the fact that the Helly number remains 5 even for arbitrarily large sets of disjoint unit disks—thus correcting a 40-year-old error; and (b) a lower bound of d+3 on the Helly number for hyperplane transversals to suitably separated families of unit balls in R ^d . Received January 25, 1999, and in revised form July 7, 1999.     

Line Transversals to Unit Disks

   Abstract. We show that if every three members of a finite disjoint family of unit disks in the plane have a line transversal, then there is a line transversal to all except at most 12 disks in the family. We derive an analogous result for translates of a general compact convex set, with the constant equal to 47.     

A Constant Bound for Geometric Permutations of Disjoint Unit Balls

Abstract. We prove that a set of n disjoint unit balls in R ^d admits at most four distinct geometric permutations, or line transversals, thus settling a long-standing conjecture in combinatorial geometry. The constant bound significantly improves upon the Θ (n ^d-1 ) bound for disjoint balls of unrestricted radii.     

A Constant Bound for Geometric Permutations of Disjoint Unit Balls

   Abstract. We prove that a set of n disjoint unit balls in R ^d admits at most four distinct geometric permutations, or line transversals, thus settling a long-standing conjecture in combinatorial geometry. The constant bound significantly improves upon the Θ (n ^d-1 ) bound for disjoint balls of unrestricted radii.     

Line Transversals to Translates of Unit Discs

Let be a family of convex figures in the plane. We say that has property T if there exists a line intersecting every member of . Also, the family has property T(k) if every k-membered subfamily of has property T. Let B be the unit disc centered at the origin. In this paper we prove that if a finite family of translates of B has property T(4) then the family , where , has property T. We also give some results concerning families of translates of the unit disc which has either property T(3) or property T(5).     

A Helly-Type Theorem for Unions of Convex Sets

We prove that for any d, k ≥ 1 there are numbers q = q(d,k) and h = h(d,k) such that the following holds: Let be a family of subsets of the d-dimensional Euclidean space, such that the intersection of any subfamily of consisting of at most q sets can be expressed as a union of at most k convex sets. Then the Helly number of is at most h. We also obtain topological generalizations of some cases of this result. The main result was independently obtained by Alon and Kalai, by a different method. Received April 14, 1995, and in revised form August 1, 1995.     

Line Transversals of Balls and Smallest Enclosing Cylinders in Three Dimensions

We establish a near-cubic upper bound on the complexity of the space of line transversals of a collection of n balls in three dimensions, and show that the bound is almost tight, in the worst case. We apply this bound to obtain a near-cubic algorithm for computing a smallest infinite cylinder enclosing a given set of points or balls in 3-space. We also present an approximation algorithm for computing a smallest enclosing cylinder. Received May 23, 1997, and in revised form October 20, 1997.     

A Helly-Type Theorem for Semi-monotone Sets and Monotone Maps

We consider sets and maps defined over an o-minimal structure over the reals, such as real semi-algebraic or globally subanalytic sets. A monotone map is a multi-dimensional generalization of a usual univariate monotone continuous function on an open interval, while the closure of the graph of a monotone map is a generalization of a compact convex set. In a particular case of an identically constant function, such a graph is called a semi-monotone set. Graphs of monotone maps are, generally, non-convex, and their intersections, unlike intersections of convex sets, can be topologically complicated. In particular, such an intersection is not necessarily the graph of a monotone map. Nevertheless, we prove a Helly-type theorem, which says that for a finite family of subsets of $\mathbb{R }^n$ , if all intersections of subfamilies, with cardinalities at most $n+1$ , are non-empty and graphs of monotone maps, then the intersection of the whole family is non-empty and the graph of a monotone map.     

A Helly-Type Theorem for Intersections of Compact Connected Sets in the Plane

For a family C of nonempty compact sets in the plane, the following conditions are equivalent:(1) Every two (not necessarily distinct) members of C have a connected union and every three (not necessarily distinct) members of C have a simply connected union.(2) C is a family of simply connected sets such that every two (not necessarily distinct) members of C have a connected intersection and every three (not necessarily distinct) members of C have a nonempty intersection.If either set of conditions is satisfied, then { C : C in C } is nonempty, simply connected, and connected. Furthermore, if the collection C is finite, then it is also true that { C : C in C } is simply connected.     

Transversals to Line Segments in Three-Dimensional Space

We completely describe the structure of the connected components of transversals to a collection of n line segments in ℝ³. Generically, the set of transversals to four segments consists of zero or two lines. We catalog the non-generic cases and show that n≥ 3 arbitrary line segments in ℝ³ admit at most n connected components of line transversals, and that this bound can be achieved in certain configurations when the segments are coplanar, or they all lie on a hyperboloid of one sheet. This implies a tight upper bound of n on the number of geometric permutations of line segments in ℝ³.     

关于平行三角形集簇直线横截的Helly数

We prove two results about the problem of finding the Helly number for line transversals to a family of parallel triangles in the plane: (1) If each three triangles of a family of parallel right triangles are intersected by an ascending (or a descending) line, then there is an ascending (or a descending) line that intersects all the triangles of the family; (2) If each three triangles of a family of parallel obtuse triangles are intersected by an ascending (or a descending) line, then there is an ascending (or a descending) line that intersects all the triangles of the family. We also obtain that the Helly number of a family of parallel right or obtuse triangles is 3.     

On the Helly Number for Line Transversals to Parallel Triangles

We prove two results about the problem of finding the Helly number for line transversals to a family of parallel triangles in the plane: (1) If each three triangles of a family of parallel right triangles are intersected by an ascending (or a descending) line, then there is an ascending (or a descending) line that intersects all     

A Generalization of the Erdos - Szekeres Theorem to Disjoint Convex Sets

Let F denote a family of pairwise disjoint convex sets in the plane. F is said to be in convex position if none of its members is contained in the convex hull of the union of the others. For any fixed k≥ 3 , we estimate P _k (n) , the maximum size of a family F with the property that any k members of F are in convex position, but no n are. In particular, for k=3 , we improve the triply exponential upper bound of T. Bisztriczky and G. Fejes Tóth by showing that P ₃ (n) < 16 ⁿ . <lsiheader> <onlinepub>26 June, 1998 <editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; <pdfname>19n3p437.pdf <pdfexist>yes <htmlexist>no <htmlfexist>no <texexist>yes <sectionname> </lsiheader> Received March 27, 1997, and in revised form July 10, 1997.     

Line Transversals to Translates of a Convex Body

Let K be a convex body in the plane. Define λ(K,t) as the smallest number satisfying the following: if F\mathcal{F} is any family of translates of K such that every t members of F\mathcal{F} have a common transversal, then all the members of l(K,t)F\lambda(K,t)\mathcal{F} have a common transversal. We give bounds for λ(K,3) and λ(K,4) for a general convex figure K. In particular, we obtain that λ(K,3)≤1.79 when K is the Euclidean disc.     

Separoids,Their Categories and a Hadwiger-Type Theorem for Transversals

In this paper we study the topology of transversals to a family of convex sets as a subset of a Grassmanian manifold. This topology seems to be ruled by a combinatorial structure which we call a separoid. With these combinatorial objects and the topological notion of virtual transversal we prove a Borsuk—Ulam-type theorem which has as a corollary a generalization of Hadwiger's theorem. Received October 25, 2000, and in revised form September 27, 2001, October 6, 2001, and October 11, 2001. Online publication March 1, 2002.