Discrete and Lexicographic Helly-Type Theorems

Helly’s theorem says that if every d+1 elements of a given finite set of convex objects in ℝ ^d have a common point, then there is a point common to all of the objects in the set. We define three new types of Helly theorems: discrete Helly theorems—where the common point should belong to an a-priori given set, lexicographic Helly theorems—where the common point should not be lexicographically greater than a given point, and lexicographic-discrete Helly theorems. We study the relations between the different types of the Helly theorems. We obtain several new discrete and lexicographic Helly numbers. An extended abstract containing parts of this work appeared in the proceedings of the Forty-Fifth Annual Symposium on Foundations of Computer Science (FOCS) 2004. This work is part of the author’s Ph.D. thesis, prepared in the school of mathematical sciences at Tel Aviv University, under the supervision of Professor Arie Tamir.     

Helly-Type Theorems for Approximate Covering

Let ℱ∪{U} be a collection of convex sets in ℝ ^d such that ℱ covers U. We prove that if the elements of ℱ and U have comparable size, then a small subset of ℱ suffices to cover most of the volume of U; we analyze how small this subset can be depending on the geometry of the elements of ℱ and show that smooth convex sets and axis parallel squares behave differently. We obtain similar results for surface-to-surface visibility amongst balls in three dimensions for a notion of volume related to form factor. For each of these situations, we give an algorithm that takes ℱ and U as input and computes in time O(|ℱ|*|ℋ _ε |) either a point in U not covered by ℱ or a subset ℋ _ε covering U up to a measure ε, with |ℋ _ε | meeting our combinatorial bounds. The authors acknowledge support from the French–Korean Science and Technology amicable relationship program (STAR) 11844QJ.     

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

Helly-Type Theorems on the Homology of the Space of Transversals

In this paper we ``measure' the size of the set of n -transversals of a family F of convex sets in R <sup>n+k</sup> according to its homological complexity inside the corresponding Grassmannian manifold. Our main result states that the ``measure' μ of the set of n -transversals of F is greater than or equal to k if and only if every k+1 members of F have a common point and also if and only if for some integer m , 1≤ m≤ n , and every subfamily F ^\prime of F with k+2 members, the ``measure' μ of the set of m -transversals of F ^\prime is greater than or equal to k . Received October 25, 2000, and in revised form September 27, 2001, and October 17, 2001. Online publication March 1, 2002.     

Helly-Type Theorems on Common Supporting Lines for Nonoverlapping Families of Convex Bodies in the Plane

Helly-type results are established relating to the existence of a line supporting a family of nonoverlapping convex bodies in the plane.     

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.     

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.     

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

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.     

Bernstein-Type Theorems and Uniqueness Theorems

Let be an entire function of finite type with respect to finite order and let be a subset of an open cone in a certain n-dimensional subspace (the smaller , the sparser ). We assume that this cone contains a ray 0} \right\}$$ " align="middle" border="0"> . It is shown that the radial indicator of at any point may be evaluated in terms of function values at points of the discrete subset . Moreover, if tends to zero fast enough as over , then this function vanishes identically. To prove these results, a special approximation technique is developed. In the last part of the paper, it is proved that, under certain conditions on and , which are close to exact conditions, the function bounded on is bounded on the ray.     

拓扑空间中的KKM型定理和重合点定理

引入了一类新的有限连续空间(简称, $FC$-空间),并在$FC$-空间中证明了一些新的涉及容许类集值映射和具有紧局部交性质的KKM型定理和重合点定理.作为应用,在$FC$-空间中得到了一些新的不动点定理.这些结果统一和推广了近期文献在抽象凸空间中的一些重要结果.     

FC-空间上的连续选择和邻近选择定理

给出了-些从仿紧拓扑空间到FC-空间的新的连续选择;也给出了-些从仿紧拓扑空间到局部FC-一致空间的新的邻近选择.这些结果改进且推广了-些近来的结论.     

Coincidence Point Theorems,Intersection Theorems and Saddle Point Theorems on FC-spaces

In this paper, we first give the definitions of finitely continuous topological space and FC-subspace generated by some set, and obtain coincidence point theorem, whole intersection theorems and Ky Fan type matching theorems, and finally discuss the existence of saddle point as an application of coincidence point theorem.     

Coincidence Point Theorems,Intersection Theorems and Saddle Point Theorems on FC-Spaces

In this paper, we first give the definitions of finitely continuous topological space and FC-subspace generated by some set, and obtain coincidence point theorem, whole intersection theorems and Ky Fan type matching theorems, and finally discuss the existence of saddle point as an application of coincidence point theorem.     

H-空间的截口定理重合定理相交定理及其应用*

本文的目的是在H-空间上得出几个截口定理、相交定理和重合定理.作为这些结果的应用,我们研究了H-空间中的极大极小不等式和变分不等式解的存在性问题.本文结果改进和发展了引文[1,3,5,6,8,9,12,14,15,17]中的相应结果.     

Common Fixed Point Theorems in Topological Vector Spaces via Intersection Theorems

Our purpose in this paper is to present two methods for obtaining common fixed point theorems in topological vector spaces. Both methods combine an intersection theorem and a fixed point theorem, but the order in which they are applied differs.     

G-凸空间中的KKM定理，匹配定理和截口定理

在G-凸空间中证明了一些新的KKM型定理．作为应用,在G-凸空间中得到了一些新的匹配定理和截口定理,所得结果改进和推广了[2,3,7]中的相关结果．