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.     

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).     

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).     

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.     

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.     

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.     

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 ℝ³.     

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.     

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.     

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     

关于平行三角形集簇直线横截的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.     

Kinetic Connectivity for Unit Disks

We describe a kinetic data structure (KDS) that maintains the connected components of the union of a set of unit-radius disks moving in the plane. We assume that the motion of each disk can be specified by a low-degree algebraic trajectory; this trajectory, however, can be modified in an on-line fashion. While the disks move continuously, their connectivity changes at discrete times. Our main result is an O(n) space data structure that takes O(log n\slash \kern -1pt log log n) time per connectivity query of the form ``are disks A and B in the same connected component?' A straightforward approach based on dynamically maintaining the overlap graph requires Ω (n ² ) space. Our data structure requires only linear space and must deal with O(n ^{2 + ε} ) updates in the worst case, each requiring O(log ² n) amortized time, for any ε>0 . This number of updates is close to optimal, since a set of n moving unit disks can undergo Ω (n ² ) connectivity changes. Received September 20, 2000, and in revised form January 19, 2001. Online publication April 6, 2001.     

Allowable Interval Sequences and Line Transversals in the Plane

Given a family F of n pairwise disjoint compact convex sets in the plane with non-empty interiors, let T(k) denote the property that every subfamily of F of size k has a line transversal, and T the property that the entire family has a line transversal. We illustrate the applicability of allowable interval sequences to problems involving line transversals in the plane by proving two new results and generalizing three old ones. Two of the old results are Klee??s assertion that if F is totally separated then T(3) implies T, and the following variation of Hadwiger??s Transversal Theorem proved by Wenger and (independently) Tverberg: If F is ordered and each four sets of F have some transversal which respects the order on F, then there is a transversal for all of F which respects this order. The third old result (a consequence of an observation made by Kramer) and the first of the new results (which partially settles a 2008 conjecture of Eckhoff) deal with fractional transversals and share the following general form: If F has property T(k) and meets certain other conditions, then there exists a transversal of some m sets in F, with k<m<n. The second new result establishes a link between transversal properties and separation properties of certain families of convex sets.     

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.     

有向拟阵和横截

讨论有向拟阵的横截理论，给出了Rado-Hall定理、Edmonds-Fulkerson定理的有向情形，从而部分地回答了[1]中的两个问题。     

Transversals in Trees

The total embedding polynomial of a graph G is the bivariate polynomial where is the number of embeddings, for into the orientable surface , and is the number of embeddings, for into the nonorientable surface . The sequence is called the total embedding distribution of the graph G; it is known for relatively few classes of graphs, compared to the genus distribution . The circular ladder graph is the Cartesian product of the complete graph on two vertices and the cycle graph on n vertices. In this article, we derive a closed formula for the total embedding distribution of circular ladders.     

On Adequate Transversals

We consider adequate transversals of abundant semigroups and prove that, in a particular case, there is a natural embedding of an inverse transversal within a certain regular subsemigroup. We also introduce the concepts of simplistic, perfect, and quasi-adequate transversal and provide a number of interesting connections between these.     

Transversals of d-Intervals

We present a method which reduces a family of problems in combinatorial geometry (concerning multiple intervals) to purely combinatorial questions about hypergraphs. The main tool is the Borsuk—Ulam theorem together with one of its extensions. For a positive integer d, a homogeneous d-interval is a union of at most d closed intervals on a fixed line ℓ. Let be a system of homogeneous d-intervals such that no k + 1 of its members are pairwise disjoint. It has been known that its transversal number can then be bounded in terms of k and d. Tardos [9] proved that for d = 2, one has . In particular, the bound is linear in k. We show that the latter holds for any d, and prove the tight bound for d = 2. We obtain similar results in the case of nonhomogeneous d-intervals whose definition appears below. Received June 10, 1995, and in revised form June 13, 1996.     

On Generalized Adequate Transversals

The aim of this article is to study abundant semigroups with generalized adequate transversals. We obtain some properties of such semigroups and give, in particular, a construction of the class of abundant semigroups with quasi-ideal generalized adequate transversals. Finally, we apply this construction to some special cases.