共查询到20条相似文献,搜索用时 15 毫秒
1.
Ciprian Borcea Xavier Goaoc Sylvain Petitjean 《Discrete and Computational Geometry》2008,39(1-3):158-173
We prove that the set of directions of lines intersecting three disjoint balls in ℝ3 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. 相似文献
2.
Pankaj K. Agarwal Boris Aronov Vladlen Koltun Micha Sharir 《Discrete and Computational Geometry》2005,34(2):231-250
Let B be a set of n unit balls
in ℝ3. We show that the combinatorial complexity of the
space of lines in ℝ3 that avoid all the balls of B is O(n3+ε), for any ε > 0. This result has connections to
problems in visibility, ray shooting, motion planning, and
geometric optimization. 相似文献
3.
On the Helly Number for Hyperplane Transversals to Unit Balls 总被引:5,自引:0,他引:5
B. Aronov J. E. Goodman R. Pollack R. Wenger 《Discrete and Computational Geometry》2000,24(2-3):171-176
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. 相似文献
4.
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.
We prove that for each natural k, each family of k permutations is realizable
(as a family of geometric permutations of some ℱ)
in ℝd for d ≥ 2k – 1, but there is a family of k permutations
which is non-realizable in ℝd for d ≤ 2k – 2. 相似文献
5.
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. 相似文献
6.
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. 相似文献
7.
We consider a periodically heterogeneous and perforated medium
filling an open domain Ω of ℝN. Assuming that the size of the periodicity of the structure and of the holes is O(ε),
we study the asymptotic behavior, as ε → 0, of the
solution of an elliptic boundary value problem with strongly oscillating coefficients posed in Ωε
(Ωε being Ω minus the holes) with a Neumann condition on the boundary of the holes. We use Bloch wave
decomposition to introduce an approximation of the solution in the
energy norm which can be computed from the homogenized solution
and the first Bloch eigenfunction. We first consider the case
where Ωis ℝN and then localize the problem for a
bounded domain Ω, considering a homogeneous Dirichlet
condition on the boundary of Ω. 相似文献
8.
Let ℒ be the space of line transversals to a finite family of pairwise disjoint compact convex sets in ℝ3. 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. 相似文献
9.
If u ≥ 0 is subharmonic on a domain Ω in n and 0 < p < 1, then it is well-known that there is a constant C(n,p) ≥ 1 such u(x)p ≤ C)n,p) MV )up,B(x,r)) for each ball B(x,r)) Ω. We show more generally that a similar result holds for functions ψ : + → + may be any surjective, concave function whose inverse ψ−1 satisfies the Δ2-condition. 相似文献
10.
A line ℓ is a transversal to a family F of convex objects in ℝ d if it intersects every member of F. In this paper we show that for every integer d ⩾ 3 there exists a family of 2d−1 pairwise disjoint unit balls in ℝ d with the property that every subfamily of size 2d − 2 admits a transversal, yet any line misses at least one member of the family. This answers a question of Danzer from 1957. Crucial to the proof is the notion of a pinned transversal, which means an isolated point in the space of transversals. Here we investigate minimal pinning configurations and construct a family F of 2d−1 disjoint unit balls in ℝ d with the following properties: (i) The space of transversals to F is a single point and (ii) the space of transversals to any proper subfamily of F is a connected set with non-empty interior. 相似文献
11.
A Gaussian t-design is defined as a finite set X in the Euclidean space ℝn satisfying the condition:
for any polynomial f(x) in n variables of degree at most t, here α is a constant real number and ω is a positive weight function on X. It is easy to see that if X is a Gaussian 2e-design in ℝn, then
. We call X a tight Gaussian 2e-design in ℝn if
holds. In this paper we study tight Gaussian 2e-designs in ℝn. In particular, we classify tight Gaussian 4-designs in ℝn with constant weight
or with weight
. Moreover we classify tight Gaussian 4-designs in ℝn on 2 concentric spheres (with arbitrary weight functions). 相似文献
12.
Let Ω be an open domain in ℝ3 or ℝ4 and N a smooth, compact Riemannian manifold. We consider the Dirichlet energy E(u) for maps u:Ω→N and its negative L2-gradient, the tension field τ(u). We study sequences of maps ui:Ω→N with
If the maps are sufficiently regular, we find strong H1-subconvergence away from a generalized submanifold in Ω. If the limit map is regular, too, we can estimate a Willmore-type energy of this generalized submanifold. 相似文献
13.
Daniel Perrucci 《Discrete and Computational Geometry》2005,34(3):475-495
We prove that the zero set of a 4-nomial in n
variables in the positive orthant
has at most three connected components. This bound, which does not
depend on the degree of the polynomial, not only improves the best
previously known bound (which was 10) but is optimal as well.
In the general case we prove that the number of connected
components of the zero set of an m-nomial in n variables in the positive orthant is lower than or equal to (n+1)m-121 + (m - 1)(m - 2)/2,
improving slightly the known bounds.
Finally, we show that for generic exponents, the number of
non-compact connected components of the zero set of a 5-nomial
in three variables in the positive octant is at most 12. This
strongly improves the best previously known bound, which was
10,384. All the bounds obtained in this paper continue to hold
for real exponents. 相似文献
14.
Transversals in r‐partite graphs with various properties are known to have many applications in graph theory and theoretical computer science. We investigate f‐bounded transversal s (or f‐BT), that is, transversals whose connected components have order at most f. In some sense we search for the sparsest f‐BT‐free graphs. We obtain estimates on the smallest maximum degree that 3‐partite and 4‐partite graphs without 2‐BT can have and provide a greatly simplified proof of the best known general lower bound on the smallest maximum degree in f‐BT‐free graphs. © 2011 Wiley Periodicals, Inc. J Graph Theory. 相似文献
15.
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. 相似文献
16.
马宇韬 《数学物理学报(B辑英文版)》2009,29(5):1461-1468
In this article, we consider the continuous gas in a bounded domain ∧ of R^+ or R^d described by a Gibbsian probability measure μη∧ associated with a pair interaction φ, the inverse temperature β, the activity z 〉 0, and the boundary condition η. Define F ∫ωf(s)wA(ds). Applying the generalized Ito's formula for forward-backward martingales (see Klein et M. [5]), we obtain convex concentration inequalities for F with respect to the Gibbs measure μη∧. On the other hand, by FKG inequality on the Poisson space, we also give a new simple argument for the stochastic domination for the Gibbs measure. 相似文献
17.
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. 相似文献
18.
《代数通讯》2013,41(9):3685-3701
Abstract We prove that a tame weakly shod algebra A which is not quasi-tilted is simply connected if and only if the orbit graph of its pip-bounded component is a tree, or if and only if its first Hochschild cohomology group H1(A) with coefficients in A A A vanishes. We also show that it is strongly simply connected if and only if the orbit graph of each of its directed components is a tree, or if and only if H1(A) = 0 and it contains no full convex subcategory which is hereditary of type 𝔸?, or if and only if it is separated and contains no full convex subcategory which is hereditary of type 𝔸?. 相似文献
19.
József Balogh Oded Regev Clifford Smyth William Steiger Mario Szegedy 《Discrete and Computational Geometry》2004,32(2):167-176
We show how to construct an arrangement of n lines having a monotone path of
length
(n2 – (d/\sqrt{log n})), where d > 0 is some constant, and thus
nearly settle the long standing question on monotone path length in line
arrangements. 相似文献
20.
Roman N. Karasev 《Discrete and Computational Geometry》2005,34(1):25-45
Three theorems of this paper generalize previous results of the author
on conjectures of A. Bezdek and V.V. Proizvolov. They show the existence of mappings from a given point set to the set of facets of a given polytope that satistfy some special conditions. Developing the same technique, some results on convex polytope partitions are presented, two of them dealing with partitions with prescribed measures of parts. Then we prove a corollary on the existence of a possibly nonconvex polytope with a given set of vertices, containing given points in its interior. We also consider problems of the following type: find an assignment of vectors from a given set to the parts of a given convex partition of ℝn so that the shifts of the parts by their corresponding vectors either do not intersect by interior points or cover ℝn 相似文献