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.     

Lines Pinning Lines

A line ℓ is a transversal to a family F of convex polytopes in ℝ³ if it intersects every member of F. If, in addition, ℓ is an isolated point of the space of line transversals to F, we say that F is a pinning of ℓ. We show that any minimal pinning of a line by polytopes in ℝ³ such that no face of a polytope is coplanar with the line has size at most eight. If in addition the polytopes are pairwise disjoint, then it has size at most six.     

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.     

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.     

Pinning a Line by Balls or Ovaloids in ℝ<Superscript>3</Superscript>

We show that if a line ℓ is an isolated line transversal to a finite family F\mathcal{F} of (possibly intersecting) balls in ℝ³ and no two balls are externally tangent on ℓ, then there is a subfamily G í F\mathcal{G}\subseteq\mathcal{F} of size at most 12 such that ℓ is an isolated line transversal to G\mathcal{G}. We generalize this result to families of semialgebraic ovaloids.     

The Maximal Number of Geometric Permutations for n Disjoint Translates of a Convex Set in ℝ Is Ω(n)

A geometric permutation induced by a transversal line of a finite family of disjoint convex sets in ℝ^d is the order in which the transversal meets the members of the family. It is known that the maximal number of geometric permutations in families of n disjoint translates of a convex set in ℝ³ is 3. We prove that for d ≥ 3 the maximal number of geometric permutations for such families in ℝ^d is Ω(n).     

Topological transversals to a family of convex sets

Let F\mathcal{F} be a family of compact convex sets in ℝ ^d . We say that F\mathcal{F} has a topological ρ-transversal of index (m,k) (ρ<m, 0<k≤d−m) if there are, homologically, as many transversal m-planes to F\mathcal{F} as m-planes containing a fixed ρ-plane in ℝ ^m+k .     

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.     

On the connected components of the space of line transversals to a family of convex sets

Let ℒ be the space of line transversals to a finite family of pairwise disjoint compact convex sets in ℝ³. We prove that each connected component of ℒ can itself be represented as the space of transversals to some finite family of pairwise disjoint compact convex sets. The research of J. E. Goodman was supported in part by NSF Grant DMS91-22065 and by NSA Grant MDA904-92-H-3069. R. Pollack's research was supported in part by NSF Grant CCR91-22103 and by NSA Grant MDA904-92-H-3075. The research of R. Wenger was supported in part by NSA Grant MDA904-93-H-3026 and by the NSF Regional Geometry Institute (Smith College, July 1993) Grant DMS90-13220.     

The Existence and Uniqueness of the Solution for Neutral Stochastic Functional Differential Equations with Infinite Delay in Abstract Space

The main aim of this paper is to prove the existence and uniqueness of the solution for neutral stochastic functional differential equations with infinite delay, which the initial data belong to the phase space ℬ((−∞,0];ℝ ^d ). The vital work of this paper is to extend the initial function space of the paper (Wei and Wang, J. Math. Anal. Appl. 331:516–531, 2007) and give some examples to show that the phase space ℬ((−∞,0];ℝ ^d ) exists. In addition, this paper builds a Banach space ℳ²((−∞,T],ℝ ^d ) with a new norm in order to discuss the existence and uniqueness of the solution for such equations with infinite delay.     

Sharp Bounds on Geometric Permutations of Pairwise Disjoint Balls in R d

We prove that the maximum number of geometric permutations, induced by line transversals to a collection of n pairwise disjoint balls in \R ^d , is Θ (n ^d-1 ) . This improves substantially the upper bound of O(n ^2d-2 ) known for general convex sets [9]. We show that the maximum number of geometric permutations of a sufficiently large collection of pairwise disjoint unit disks in the plane is two, improving the previous upper bound of three given in [5]. Received September 21, 1998, and in revised form March 14, 1999.     

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.     

Analogues of Horn’s theorem for finite unions of starshaped sets in ℝ<Superscript><Emphasis Type="Italic">d</Emphasis></Superscript>

Fix k, d, 1 ≤ k ≤ d + 1. Let $ \mathcal{F} $ \mathcal{F} be a nonempty, finite family of closed sets in ℝ ^d , and let L be a (d − k + 1)-dimensional flat in ℝ ^d . The following results hold for the set T ≡ ∪{F: F in $ \mathcal{F} $ \mathcal{F} }. Assume that, for every k (not necessarily distinct) members F ₁, …, F _k of $ \mathcal{F} $ \mathcal{F} ,∪{F _i : 1 ≤ i ≤ k} is starshaped and the corresponding kernel contains a translate of L. Then T is starshaped, and its kernel also contains a translate of L.     

On classification of orthogonal multiplications à la do carmo-wallach

The space of range-equivalence classes of full orthogonal multiplications F: ℝ ⁿ ×ℝ ⁿ →ℝ ^p , n≤p ≤n ², is shown to be a compact convex body lying in so(n)⊗so(n). Furthermore, the dimension of the space of equivalence classes is determined to be (n ²(n−1)²)/4−n(n−1).     

A local criterion for Tverberg graphs

The topological Tverberg theorem states that for any prime power q and continuous map from a (d+1)(q−1)-simplex to ℝ ^d , there are q disjoint faces F _i of the simplex whose images intersect. It is possible to put conditions on which pairs of vertices of the simplex that are allowed to be in the same face F _i . A graph with the same vertex set as the simplex, and with two vertices adjacent if they should not be in the same F _i , is called a Tverberg graph if the topological Tverberg theorem still work.     

Lower bounds for weak epsilon-nets and stair-convexity

A set N ⊂ ℝ ^d is called a weak ɛ-net (with respect to convex sets) for a finite X ⊂ ℝ ^d if N intersects every convex set C with |X ∩ C| ≥ ɛ|X|. For every fixed d ≥ 2 and every r ≥ 1 we construct sets X ⊂ ℝ ^d for which every weak 1/r -net has at least Ω(r log ^d−1 r) points; this is the first superlinear lower bound for weak ɛ-nets in a fixed dimension.     

Gradient algorithms for quadratic optimization with fast convergence rates

We propose a family of gradient algorithms for minimizing a quadratic function f(x)=(Ax,x)/2−(x,y) in ℝ ^d or a Hilbert space, with simple rules for choosing the step-size at each iteration. We show that when the step-sizes are generated by a dynamical system with ergodic distribution having the arcsine density on a subinterval of the spectrum of A, the asymptotic rate of convergence of the algorithm can approach the (tight) bound on the rate of convergence of a conjugate gradient algorithm stopped before d iterations, with d≤∞ the space dimension.