共查询到20条相似文献,搜索用时 62 毫秒
1.
Given disjoint setsP
1,P
2, ...,P
d
inR
d
withn points in total, ahamsandwich cut is a hyperplane that simultaneously bisects theP
i
. We present algorithms for finding ham-sandwich cuts in every dimensiond>1. Whend=2, the algorithm is optimal, having complexityO(n). For dimensiond>2, the bound on the running time is proportional to the worst-case time needed for constructing a level in an arrangement
ofn hyperplanes in dimensiond−1. This, in turn, is related to the number ofk-sets inR
d−1
. With the current estimates, we get complexity close toO(n
3/2
) ford=3, roughlyO(n
8/3
) ford=4, andO(n
d−1−a(d)
) for somea(d)>0 (going to zero asd increases) for largerd. We also give a linear-time algorithm for ham-sandwich cuts inR
3 when the three sets are suitably separated.
A preliminary version of the results of this paper appeared in [16] and [17]. Part of this research by J. Matoušek was done
while he was visiting the School of Mathematics, Georgia Institute of Technology, Atlanta, and part of his work on this paper
was supported by a Humboldt Research Fellowship. W. Steiger expresses gratitude to the NSF DIMACS Center at Rutgers, and his
research was supported in part by NSF Grants CCR-8902522 and CCR-9111491. 相似文献
2.
Vladimir Shpilrain 《Israel Journal of Mathematics》1995,91(1-3):307-316
LetE be a bounded Borel subset of ℝn,n≥2, of positive Lebesgue measure andP
E the corresponding ‘Pompeiu transform”. We prove thatP
E is injective onL
p(ℝn) if 1≤p≤2n/(n-1). We explore the connection between this problem and a Wiener-Tauberian type theorem for theM(n) action onL
q(ℝn) for various values ofq. We also take up the question of whenP
E is injective in caseE is of finite, positive measure, but is not necessarily a bounded set. Finally, we briefly look at these questions in the
contexts of symmetric spaces of compact and non-compact type. 相似文献
3.
For a domainU on a certaink-dimensional minimal submanifold ofS
n orH
n, we introduce a “modified volume”M(U) ofU and obtain an optimal isoperimetric inequality forU k
k
ω
k
M (D)
k-1
≤Vol(∂D)
k
, where ω
k
is the volume of the unit ball ofR
k
. Also, we prove that ifD is any domain on a minimal surface inS
+
n
(orH
n, respectively), thenD satisfies an isoperimetric inequality2π A≤L
2+A2 (2π A≤L2−A2 respectively). Moreover, we show that ifU is ak-dimensional minimal submanifold ofH
n, then(k−1) Vol(U)≤Vol(∂U).
Supported in part by KME and GARC 相似文献
4.
The paper deals with the structure of intermediate subgroups of the general linear group GL(n, k) of degree n over a field k of odd characteristic that contain a nonsplit maximal torus related to a radical extension of degree n of the ground field k. The structure of ideal nets over a ring that determine the structure of intermediate subgroups containinga transvection
is given. Let K = k( n?{d} ) K = k\left( {\sqrt[n]{d}} \right) be a radical degree-n extension of a field k of odd characteristic, and let T =(d) be a nonsplit maximal torus, which is the image of the multiplicative group of the field K under the regular embedding in G =GL(n, k). In the paper, the structure of intermediate subgroups H, T ≤ H ≤ G, that contain a transvection is studied. The elements of the matrices in the torus T = T (d) generate a subring R(d) in the field k.Let R be an intermediate subring, R(d) ⊆ R ⊆ k, d ∈ R. Let σR denote the net in which the ideal dR stands on the principal diagonal and above it and all entries of which beneath the principal diagonal are equal to R. Let σR denote the net in which all positions on the principal diagonal and beneath it are occupied by R and all entries above the principal diagonal are equal to dR. Let E(σR) be the subgroup generated by all transvections from the net group G(σR). In the paper it is proved that the product TE(σR) is a group (and thus an intermediate subgroup). If the net σ associated with an intermediate subgroup H coincides with σR,then TE(σR) ≤ H ≤ N(σR),where N(σR) is the normalizer of the elementary net group E(σR) in G. For the normalizer N(σR),the formula N(σR)= TG(σR) holds. In particular, this result enables one to describe the maximal intermediate subgroups. Bibliography: 13 titles. 相似文献
5.
B. Chazelle H. Edelsbrunner M. Grigni L. Guibas M. Sharir E. Welzl 《Discrete and Computational Geometry》1995,13(1):1-15
LetS be a set ofn points in ℝ
d
. A setW is aweak ε-net for (convex ranges of)S if, for anyT⊆S containing εn points, the convex hull ofT intersectsW. We show the existence of weak ε-nets of size
, whereβ
2=0,β
3=1, andβ
d
≈0.149·2
d-1(d-1)!, improving a previous bound of Alonet al. Such a net can be computed effectively. We also consider two special cases: whenS is a planar point set in convex position, we prove the existence of a net of sizeO((1/ε) log1.6(1/ε)). In the case whereS consists of the vertices of a regular polygon, we use an argument from hyperbolic geometry to exhibit an optimal net of sizeO(1/ε), which improves a previous bound of Capoyleas.
Work by Bernard Chazelle has been supported by NSF Grant CCR-90-02352 and the Geometry Center. Work by Herbert Edelsbrunner
has been supported by NSF Grant CCR-89-21421. Work by Michelangelo Grigni has been supported by NSERC Operating Grants and
NSF Grant DMS-9206251. Work by Leonidas Guibas and Micha Sharir has been supported by a grant from the U.S.-Israeli Binational
Science Foundation. Work by Emo Welzl and Micha Sharir has been supported by a grant from the G.I.F., the German-Israeli Foundation
for Scientific Research and Development. Work by Micha Sharir has also been supported by NSF Grant CCR-91-22103, and by a
grant from the Fund for Basic Research administered by the Israeli Academy of Sciences. 相似文献
6.
LetS be a compact set inR
2 with nonempty interior,L(u,k) be a line 〈u, x〉 =k, and ζ
u
(k) be the linear Lebesgue measure ofS∩L(u,k). It is well known that for a convexS, ζ
u
(k) is unimodal, that is, as a function ofk, it is first non-decreasing and then nonincreasing for everyu∈R
2. Further, ifS is centrally symmetric with respect toM, ζ
u
(k) achieves maximum whenL(u, k) passes throughM. Converse propositions are considered in this paper for polygonalS with Jordan boundary. It is shown that unimodality alone does not suffice for convexity. However, if ζ
u
(k) achieves maximum wheneverL(u, k) passes through some fixed pointM then unimodality yields convexity as well as central symmetry. It is also shown that continuity of ζ
u
(k) in the interior of its support implies convexity ofS. This last result, however, is false for non-polygonal sets.
Research supported by National Science Foundation Grant GP-28154. 相似文献
7.
For 1≤k≤n-1, the k-plane transformT
k,n
carries functionsf defined onR
n
to functionsT
k,n
f defined on the set of affine k-planes inR
n
. It is known thatT
k,n
mapsL
p
intoL
q
for certain values ofp andq. In this article we formulate conjectures for the exact values of the norm of theT
k,n
, and state also a conjecture asserting that theL
q
norm ofT
k,n
f changes monotonically whenf is replaced by its symmetric decreasing rearrangement.
Conferenza tenuta il 6 marzo 1997
The first author was supported in part by NSF grants DMS-9206319 and DMS-9501293. The second author was supported in part
by NSF grant DMS-9500840 相似文献
8.
R. A. Dwyer 《Discrete and Computational Geometry》1997,17(2):123-136
It is proved that, for any fixedd ≽ 3 and 0 ≤k ≤ d - 1, the expected combinatorial complexity of the Euclidean Voronoi diagram ofn random &-flats drawn independently from the uniform distribution onk-flats intersecting the unit ball in ℝd is Ξ(n
d/(d-k)) asn → ∞. A by-product of the proof is a density transformation for integrating over sets ofd + 1k-flats in ℝd 相似文献
9.
Given a substitution σ ond letters, we define itsk-dimensional extension,E
k (σ), for 0≤k≤d. Thek-dimensional extension acts on the set ofk-dimensional faces of unit cubes inR
d with integer vertices. The extensions of a substitution satisfy a commutation relation with the natural boundary operator:
the boundary of the image is the image of the boundary. We say that a substitution is unimodular (resp. hyperbolic) if the
matrix associated to the substitution by abelianization is unimodular (resp. hyperbolic). In the case where the substitution
is unimodular, we also define dual substitutions which satisfy a similar coboundary condition. We use these constructions
to build self-similar sets on the expanding and contracting space for an hyperbolic substitution. 相似文献
10.
Fix integers n, x, k such that n≥3, k>0, x≥4, (n, x)≠(3, 4) and k(n+1)<(
n
n+x
). Here we prove that the order x Veronese embedding ofP
n
is not weakly (k−1)-defective, i.e. for a general S⊃P
n
such that #(S) = k+1 the projective space | I
2S
(x)| of all degree t hypersurfaces ofP
n
singular at each point of S has dimension (
n
/n+x
)−1− k(n+1) (proved by Alexander and Hirschowitz) and a general F∈| I
2S
(x)| has an ordinary double point at each P∈ S and Sing (F)=S.
The author was partially supported by MIUR and GNSAGA of INdAM (Italy). 相似文献
11.
Hanno Lefmann 《Discrete and Computational Geometry》2008,40(3):401-413
We consider a variant of Heilbronn’s triangle problem by investigating for a fixed dimension d≥2 and for integers k≥2 with k≤d distributions of n points in the d-dimensional unit cube [0,1]
d
, such that the minimum volume of the simplices, which are determined by (k+1) of these n points is as large as possible. Denoting by Δ
k,d
(n), the supremum of this minimum volume over all distributions of n points in [0,1]
d
, we show that c
k,d
⋅(log n)1/(d−k+1)/n
k/(d−k+1)≤Δ
k,d
(n)≤c
k,d
′/n
k/d
for fixed 2≤k≤d, and, moreover, for odd integers k≥1, we show the upper bound Δ
k,d
(n)≤c
k,d
″/n
k/d+(k−1)/(2d(d−1)), where c
k,d
,c
k,d
′,c
k,d
″>0 are constants.
A preliminary version of this paper appeared in COCOON ’05. 相似文献
12.
Henry Teicher 《Journal of Theoretical Probability》1995,8(4):779-793
Conditions are obtained for (*)E|S
T
|γ<∞, γ>2 whereT is a stopping time and {S
n=∑
1
n
,X
j
ℱ
n
,n⩾1} is a martingale and these ensure when (**)X
n
,n≥1 are independent, mean zero random variables that (*) holds wheneverET
γ/2<∞, sup
n≥1
E|X
n
|γ<∞. This, in turn, is applied to obtain conditions for the validity ofE|S
k,T
|γ<∞ and of the second moment equationES
k,T
2
=σ
2
EΣ
j=k
T
S
k−1,j−1
2
where
and {X
n
, n≥1} satisfies (**) and
,n≥1. The latter is utilized to elicit information about a moment of a stopping rule. It is also shown for i.i.d. {X
n
, n≥1} withEX=0,EX
2=1 that the a.s. limit set of {(n log logn)−k/2
S
k,n
,n≥k} is [0,2
k/2/k!] or [−2
k/2/k!] according ask is even or odd and this can readily be reformulated in terms of the corresponding (degenerate kernel)U-statistic
. 相似文献
13.
We show that the total number of faces bounding any one cell in an arrangement ofn (d−1)-simplices in ℝ
d
isO(n
d−1 logn), thus almost settling a conjecture of Pach and Sharir. We present several applications of this result, mainly to translational
motion planning in polyhedral environments. We than extend our analysis to derive other results on complexity in arrangements
of simplices. For example, we show that in such an arrangement the total number of vertices incident to the same cell on more
than one “side” isO(n
d−1
logn). We, also show that the number of repetitions of a “k-flap,” formed by intersectingd−k given simplices, along the boundary of the same cell, summed over all cells and allk-flaps, isO(n
d−1
log2
n). We use this quantity, which we call theexcess of the arrangement, to derive bounds on the complexity ofm distinct cells of such an arrangement.
Work on this paper by the first author has been partially supported by National Science Foundation Grant CCR-92-11541. Work
on this paper by the second author has been supported by Office of Naval Research Grant N00014-90-J-1284, by National Science
Foundation Grants CCR-89-01484 and CCR-91-22103, and by grants from the U.S.-Israeli Binational Science Foundation, the G.I.F.—the
German-Israeli Foundation for Scientific Reseach and Development, and the Fund for Basic Research administered by the Israeli
Academy of Sciences. 相似文献
14.
We extend the scalar curvature pinching theorems due to Peng-Terng, Wei-Xu and Suh-Yang. Let M be an n-dimensional compact minimal hypersurface in S n+1 satisfying Sf 4 f_3~2 ≤ 1/n S~3 , where S is the squared norm of the second fundamental form of M, and f_k =sum λ_i~k from i and λ_i (1 ≤ i ≤ n) are the principal curvatures of M. We prove that there exists a positive constant δ(n)(≥ n/2) depending only on n such that if n ≤ S ≤ n + δ(n), then S ≡ n, i.e., M is one of the Clifford torus S~k ((k/n)~1/2 ) ×S~... 相似文献
15.
R. J. Cook 《Proceedings Mathematical Sciences》1989,99(2):147-153
Letf(x)=θ1
x
1
k
+...+θ
s
x
s
k
be an additive form with real coefficients, and ∥α∥ = min {|α-u|:uεℤ} denote the distance fromα to the nearest integer. We show that ifθ
1,…,θ
s
, are algebraic ands = 4k then there are integersx
1,…,x
s
, satisfying l ≤x
1,≤ N and ∥f(x)∥ ≤ N
E
, withE = − 1 + 2/e.
Whens = λk, 1 ≤λ ≤ 2k, the exponentE may be replaced byλE/4, and if we drop the condition thatθ
1,…,θ
s
, be algebraic then the result holds for almost all values of θεℝ
s
. Whenk ≥ 6 is small a better exponent is obtained using Heath-Brown’s version of Weyl’s estimate. 相似文献
16.
Bernardo M. Ábrego Silvia Fernández-Merchant Bernardo Llano 《Discrete and Computational Geometry》2010,43(1):1-20
Given a finite set P⊆ℝ
d
, called a pattern, t
P
(n) denotes the maximum number of translated copies of P determined by n points in ℝ
d
. We give the exact value of t
P
(n) when P is a rational simplex, that is, the points of P are rationally affinely independent. In this case, we prove that t
P
(n)=n−m
r
(n), where r is the rational affine dimension of P, and m
r
(n) is the r -Kruskal–Macaulay function. We note that almost all patterns in ℝ
d
are rational simplices. The function t
P
(n) is also determined exactly when |
P
|≤3 or when P has rational affine dimension one and n is large enough. We establish the equivalence of finding t
P
(n) and the maximum number s
R
(n) of scaled copies of a suitable pattern R⊆ℝ+ determined by n positive reals. As a consequence, we show that
sAk(n)=n-\varTheta (n1-1/p(k))s_{A_{k}}(n)=n-\varTheta (n^{1-1/\pi(k)})
, where A
k
={1,2,…,k} is an arithmetic progression of size k, and π(k) is the number of primes less than or equal to k. 相似文献
17.
Riccardo Benedetti Francois Loeser Jean Jacques Risler 《Discrete and Computational Geometry》1991,6(1):191-209
For every polynomial mapf=(f
1,…,f
k): ℝ
n
→ℝ
k
, we consider the number of connected components of its zero set,B(Z
f) and two natural “measures of the complexity off,” that is the triple(n, k, d), d being equal to max(degree off
i), and thek-tuple (Δ1,...,Δ4), Δ
k
being the Newton polyhedron off
i respectively. Our aim is to boundB(Z
f) by recursive functions of these measures of complexity. In particular, with respect to (n, k, d) we shall improve the well-known Milnor-Thom’s bound μ
d
(n)=d(2d−1)
n−1. Considered as a polynomial ind, μ
d
(n) has leading coefficient equal to 2
n−1. We obtain a bound depending onn, d, andk such that ifn is sufficiently larger thank, then it improves μ
d
(n) for everyd. In particular, it is asymptotically equal to 1/2(k+1)n
k−1
dn, ifk is fixed andn tends to infinity. The two bounds are obtained by a similar technique involving a slight modification of Milnor-Thom's argument,
Smith's theory, and information about the sum of Betti numbers of complex complete intersections. 相似文献
18.
We compute the greatest solutions of systems of linear equations over a lattice (P, ≤). We also present some applications of the results obtained to lattice matrix theory. Let (P, ≤) be a pseudocomplemented lattice with
and
and let A = ‖a
ij
‖
n×n
, where a
ij
∈ P for i, j = 1,..., n. Let A* = ‖a
ij
′
‖
n×n
and
for i, j = 1,..., n, where a* is the pseudocomplement of a ∈ P in (P, ≤). A matrix A has a right inverse over (P, ≤) if and only if A · A* = E over (P, ≤). If A has a right inverse over (P, ≤), then A* is the greatest right inverse of A over (P, ≤). The matrix A has a right inverse over (P, ≤) if and only if A is a column orthogonal over (P, ≤). The matrix D = A · A* is the greatest diagonal such that A is a left divisor of D over (P, ≤).
Invertible matrices over a distributive lattice (P, ≤) form the general linear group GL
n
(P, ≤) under multiplication. Let (P, ≤) be a finite distributive lattice and let k be the number of components of the covering graph Γ(join(P,≤) −
, ≤), where join(P, ≤) is the set of join irreducible elements of (P, ≤). Then GL
a
(P, ≤) ≅ = S
n
k
.
We give some further results concerning inversion of matrices over a pseudocomplemented lattice.
__________
Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 11, No. 3, pp. 139–154, 2005. 相似文献
19.
We prove inequalities about the quermassintegralsV
k
(K) of a convex bodyK in ℝ
n
(here,V
k
(K) is the mixed volumeV((K, k), (B
n
,n − k)) whereB
n
is the Euclidean unit ball). (i) The inequality
holds for every pair of convex bodiesK andL in ℝ
n
if and only ifk=2 ork=1. (ii) Let 0≤k≤p≤n. Then, for everyp-dimensional subspaceE of ℝ
n
,
whereP
E
K denotes the orthogonal projection ofK ontoE. The proof is based on a sharp upper estimate for the volume ratio |K|/|L| in terms ofV
n−k
(K)/V
n−k
(L), wheneverL andK are two convex bodies in ℝ
n
such thatK ⊆L. 相似文献
20.
Amiram Braun 《Israel Journal of Mathematics》1982,43(2):116-128
LetR=F{x
1, …, xk} be a prime affine p.i. ring andS a multiplicative closed set in the center ofR, Z(R). The structure ofG-rings of the formR
s is completely determined. In particular it is proved thatZ(R
s)—the normalization ofZ(R
s) —is a prüfer ring, 1≦k.d(R
s)≦p.i.d(R
s) and the inequalities can be strict. We also obtain a related result concerning the contractability ofq, a prime ideal ofZ(R) fromR. More precisely, letQ be a prime ideal ofR maximal to satisfyQϒZ(R)=q. Then k.dZ(R)/q=k.dR/Q, h(q)=h(Q) andh(q)+k.dZ(R)/q=k.dz(R). The last condition is a necessary butnot sufficient condition for contractability ofq fromR. 相似文献