共查询到20条相似文献,搜索用时 15 毫秒
1.
Nir Halman 《Discrete and Computational Geometry》2008,39(4):690-719
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. 相似文献
2.
Julien Demouth Olivier Devillers Marc Glisse Xavier Goaoc 《Discrete and Computational Geometry》2009,42(3):379-398
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. 相似文献
3.
Otfried Cheong Xavier Goaoc Andreas Holmsen Sylvain Petitjean 《Discrete and Computational Geometry》2008,39(1-3):194-212
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). 相似文献
4.
In this paper we ``measure' the size of the set of n -transversals of a family F of convex sets in R
n+k
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. 相似文献
5.
Helly-type results are established relating to the existence of a line supporting a family of nonoverlapping convex bodies in the plane. 相似文献
6.
J. Matoušek 《Discrete and Computational Geometry》1997,18(1):1-12
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. 相似文献
7.
B. Aronov J. E. Goodman R. Pollack R. Wenger 《Discrete and Computational Geometry》2001,25(4):507-517
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. 相似文献
8.
Abstract. Let F be a family of disjoint unit balls in R
3
. We prove that there is a Helly-number n
0
≤ 46 , such that if every n
0
members of F ( | F | ≥ n
0
) 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. 相似文献
9.
Saugata Basu Andrei Gabrielov Nicolai Vorobjov 《Discrete and Computational Geometry》2013,50(4):857-864
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. 相似文献
10.
Marilyn Breen 《Geometriae Dedicata》1998,71(2):111-117
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. 相似文献
11.
Abstract. Let F be a family of disjoint unit balls in R
3
. We prove that there is a Helly-number n
0
≤ 46 , such that if every n
0
members of F ( | F | ≥ n
0
) 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. 相似文献
12.
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. 相似文献
13.
引入了一类新的有限连续空间(简称, $FC$-空间),并在$FC$-空间中证明了一些新的涉及容许类集值映射和具有紧局部交性质的KKM型定理和重合点定理.作为应用,在$FC$-空间中得到了一些新的不动点定理.这些结果统一和推广了近期文献在抽象凸空间中的一些重要结果. 相似文献
14.
何蓉华 《应用泛函分析学报》2011,13(2):161-167
给出了-些从仿紧拓扑空间到FC-空间的新的连续选择;也给出了-些从仿紧拓扑空间到局部FC-一致空间的新的邻近选择.这些结果改进且推广了-些近来的结论. 相似文献
15.
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. 相似文献
16.
Yongjie Piao & Zhe Yin 《数学研究通讯:英文版》2009,25(2):115-122
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. 相似文献
17.
本文的目的是在H-空间上得出几个截口定理、相交定理和重合定理.作为这些结果的应用,我们研究了H-空间中的极大极小不等式和变分不等式解的存在性问题.本文结果改进和发展了引文[1,3,5,6,8,9,12,14,15,17]中的相应结果. 相似文献
18.
Ravi P. Agarwal Mircea Balaj Donal O’Regan 《Journal of Optimization Theory and Applications》2017,173(2):443-458
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. 相似文献
19.
20.
在G-凸空间中证明了一些新的KKM型定理.作为应用,在G-凸空间中得到了一些新的匹配定理和截口定理,所得结果改进和推广了[2,3,7]中的相关结果. 相似文献