Piecewise linear paths among convex obstacles

Let ℬ be a set ofn arbitrary (possibly intersecting) convex obstacles in ℝ ^d . It is shown that any two points which can be connected by a path avoiding the obstacles can also be connected by a path consisting ofO(n ^{(d−1)[d/2+1]}) segments. The bound cannot be improved below Ω(n ^d ); thus, in ℝ³, the answer is betweenn ³ andn ⁴. For open disjoint convex obstacles, a Θ(n) bound is proved. By a well-known reduction, the general case result also upper bounds the complexity for a translational motion of an arbitrary convex robot among convex obstacles. Asymptotically tight bounds and efficient algorithms are given in the planar case. This research was supported by The Netherlands' Organization for Scientific Research (NWO) and partially by the ESPRIT III Basic Research Action 6546 (PROMotion). J. M. acknowledges support by a Humboldt Research Fellowship. Part of this research was done while he visited Utrecht University.     

Expectation of intrinsic volumes of random polytopes

Let K be a convex body in ℝ ^d , let j ∈ {1, …, d−1}, and let K(n) be the convex hull of n points chosen randomly, independently and uniformly from K. If ∂K is C ₊², then an asymptotic formula is known due to M. Reitzner (and due to I. Bárány if ∂K is C ₊³) for the difference of the jth intrinsic volume of K and the expectation of the jth intrinsic volume of K(n). We extend this formula to the case when the only condition on K is that a ball rolls freely inside K. Funded by the Marie-Curie Research Training Network “Phenomena in High-Dimensions” (MRTN-CT-2004-511953).     

On the Bethe-Sommerfeld conjecture for higher-order elliptic operators

 We consider the elliptic operator P(D)+V in ℝ ^d , d≥2 where P(D) is a constant coefficient elliptic pseudo-differential operator of order 2ℓ with a homogeneous convex symbol P(ξ), and V is a real periodic function in L ^∞(ℝ ^d ). We show that the number of gaps in the spectrum of P(D)+V is finite if 4ℓ>d+1. If in addition, V is smooth and the convex hypersurface {ξℝ ^d :P(ξ)=1} has positive Gaussian curvature everywhere, then the number of gaps in the spectrum of P(D)+V is finite, provided 8ℓ>d+3 and 9≥d≥2, or 4ℓ>d−3 and d≥10. Received: 10 October 2001 / Published online: 28 March 2003 Mathematics Subject Classification (1991): 35J10 Research supported in part by NSF Grant DMS-9732894.     

On directional convexity

Motivated by problems from calculus of variations and partial differential equations, we investigate geometric properties of D-convexity. A function f: R ^d → R is called D-convex, where D is a set of vectors in R ^d, if its restriction to each line parallel to a nonzero v ∈ D is convex. The D-convex hull of a compact set A ⊂ R ^d, denoted by co^D(A), is the intersection of the zero sets of all nonnegative D-convex functions that are zero on A. It also equals the zero set of the D-convex envelope of the distance function of A. We give an example of an n-point set A ⊂ R ² where the D-convex envelope of the distance function is exponentially close to zero at points lying relatively far from co ^D(A), showing that the definition of the D-convex hull can be very nonrobust. For separate convexity in R ³ (where D is the orthonormal basis of R ³), we construct arbitrarily large finite sets A with co ^D(A) ≠ A whose proper subsets are all equal to their D-convex hull. This implies the existence of analogous sets for rank-one convexity and for quasiconvexity on 3 × 3 (or larger) matrices. This research was supported by Charles University Grants No. 158/99 and 159/99.     

On transfer inequalities in Diophantine approximation, II

Let Θ be a point in R ⁿ . We are concerned with the approximation to Θ by rational linear subvarieties of dimension d for 0 ≤ d ≤ n−1. To that purpose, we introduce various convex bodies in the Grassmann algebra Λ(R ⁿ⁺¹). It turns out that our convex bodies in degree d are the dth compound, in the sense of Mahler, of convex bodies in degree one. A dual formulation is also given. This approach enables us both to split and to refine the classical Khintchine transference principle.     

On the generalized critical values of a polynomial mapping

 Let be a polynomial dominant mapping and let deg f _i ≤d. We prove that the set K(f) of generalized critical values of f is contained in the algebraic hypersurface of degree at most D=(d+s(m−1)(d−1)) ⁿ , where . This implies in particular that the set B(f) of bifurcations points of f is contained in the hypersurface of degree at most D=(d+s(m−1)(d−1)) ⁿ . We give also an algorithm to compute the set K(f) effectively. Received: 11 June 2001 / Revised version: 1 July 2002 Published online: 24 January 2003 The author is partially supported by the KBN grant 2 PO3A 017 22. Mathematics Subject Classification (2000): 14D06, 14Q20, 51N10, 51N20, 15A04     

Estimating the diameter of the space of plane convex figures with respect to an affine-invariant metric

A convex figure K ⊂ ℝ² is a compact convex set with nonempty interior, and αK is a homothetic image of K with coefficient α ∈ ℝ. It is proved that for any two convex figures K₁, K₂ ⊂ ℝ² there is an affine transformation T of the plane such that K₁ ⊂ T(K₂) ⊂ 2.7K₁. Bibliography: 2 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 329, 2005, pp. 58–66.     

Sausages are good packings

LetB ^d be thed-dimensional unit ball and, for an integern, letC _n ={x ¹,...,x ⁿ } be a packing set forB ^d , i.e.,|x ⁱ −x ^j |≥2, 1≤i<j≤n. We show that for every a dimensiond(ρ) exists such that, ford≥d(ρ),V(conv(C _n )+ρB ^d )≥V(conv(S _n )+ρB ^d ), whereS _n is a “sausage” arrangement ofn balls, holds. This gives considerable improvement to Fejes Tóth's “sausage” conjecture in high dimensions. Further, we prove that, for every convex bodyK and ρ<1/32d ⁻²,V(conv(C _n )+ρK)≥V(conv(S _n )+ρK), whereC _n is a packing set with respect toK andS _n is a minimal “sausage” arrangement ofK, holds.     

Super Connectivity of Line Graphs and Digraphs

The h-super connectivity κh and the h-super edge-connectivity λh are more refined network reliability indices than the conneetivity and the edge-connectivity. This paper shows that for a connected balanced digraph D and its line digraph L, if D is optimally super edge-connected, then κ1（L） = 2λ1 （D）, and that for a connected graph G and its line graph L, if one of κ1 （L） and λ（G） exists, then κ1（L） = λ2（G）. This paper determines that κ1（B（d, n） is equal to 4d- 8 for n = 2 and d ≥ 4, and to 4d-4 for n ≥ 3 and d ≥ 3, and that κ1（K（d, n）） is equal to 4d- 4 for d 〉 2 and n ≥ 2 except K（2, 2）. It then follows that B（d,n） and K（d, n） are both super connected for any d ≥ 2 and n ≥ 1.     

The Probability that a Convex Body Intersects the Integer Lattice in a <Emphasis Type="Italic">k</Emphasis>-dimensional Set

Let K be a convex body in ℝ ^d . It is known that there is a constant C ₀ depending only on d such that the probability that a random copy ρ(K) of K does not intersect ℤ ^d is smaller than \fracC₀|K|\frac{C_{0}}{|K|} and this is best possible. We show that for every k<d there is a constant C such that the probability that ρ(K) contains a subset of dimension k is smaller than \fracC|K|\frac{C}{|K|}. This is best possible if k=d−1. We conjecture that this is not best possible in the rest of the cases; if d=2 and k=0 then we can obtain better bounds. For d=2, we find the best possible value of C ₀ in the limit case when width(K)→0 and |K|→∞.     

On a question of K. Bezdek and T. Odor on Γ-parallelotops

K. Bezdek and T. Odor proved the following statement in [1]: If a covering ofE ³ is a lattice packing of the convex compact bodyK with packing lattice Λ (K is a Λ-parallelotopes) then there exists such a 2-dimensional sublattice Λ′ of Λ which is covered by the set ∪(K+z∣z ∈ Λ′). (K ∪L(Λ′) is a Λ′-parallelotopes). We prove that the statement is not true in the case of the dimensionsn=6, 7, 8. Supported by Hung. Nat. Found for Sci. Research (OTKA) grant no. 1615 (1991).     

Voronoi Diagrams and Convex Hulls of Random Moving Points

This report considers the expected combinatorial complexity of the Euclidean Voronoi diagram and the convex hull of sets of n independent random points moving in unit time between two positions drawn independently from the same distribution in R ^d for fixed d\ge 2 as n→∈fty . It is proved that, when the source and destination distributions are the uniform distribution on the unit d -ball, these complexities are Θ(n ^(d+1)/d ) for the Voronoi diagram and O(n ^(d-1)/(d+1) log n) for the convex hull. Additional results for the convex hull are O( log ^d n) for the uniform distribution in the unit d -cube and O( log ^(d+1)/2 n) for the d -dimensional normal distribution. Received November 23, 1998, and in revised form July 8, 1999.     

The expected value of some functions of the convex hull of a random set of points sampled inR d

This paper presents formulas and asymptotic expansions for the expected number of vertices and the expected volume of the convex hull of a sample ofn points taken from the uniform distribution on ad-dimensional ball. It is shown that the expected number of vertices is asymptotically proportional ton ^{(d−1)/(d+1)}, which generalizes Rényi and Sulanke’s asymptotic raten ^(1/3) ford=2 and agrees with Raynaud’s asymptotic raten ^{(d−1)/(d+1)} for the expected number of facets, as it should be, by Bárány’s result that the expected number ofs-dimensional faces has order of magnitude independent ofs. Our formulas agree with the ones Efron obtained ford=2 and 3 under more general distributions. An application is given to the estimation of the probability content of an unknown convex subset ofR ^d .     

Isoperimetric problems for convex bodies and a localization lemma

We study the smallest number ψ(K) such that a given convex bodyK in ℝ ⁿ can be cut into two partsK ₁ andK ₂ by a surface with an (n−1)-dimensional measure ψ(K) vol(K ₁)·vol(K ₂)/vol(K). LetM ₁(K) be the average distance of a point ofK from its center of gravity. We prove for the “isoperimetric coefficient” that

On estimation of the logarithmic Sobolev constant and gradient estimates of heat semigroups

Summary. This paper presents some explicit lower bound estimates of logarithmic Sobolev constant for diffusion processes on a compact Riemannian manifold with negative Ricci curvature. Let Ric≧−K for some K>0 and d, D be respectively the dimension and the diameter of the manifold. If the boundary of the manifold is either empty or convex, then the logarithmic Sobolev constant for Brownian motion is not less than max {(d d+2) ^d 1 2(d+1)D ² exp [−1−(3d+2)D ² K],     (d−1 d+1) ^d K exp [−4D√d K]} . Next, the gradient estimates of heat semigroups (including the Neumann heat semigroup and the Dirichlet one) are studied by using coupling method together with a derivative formula modified from [11]. The resulting estimates recover or improve those given in [7, 21] for harmonic functions. Received: 19 September 1995 / In revised form 11 April 1996     

Degree-uniform lower bound on the weights of polynomials with given sign function

A Boolean function f: {0, 1} ⁿ → {0, 1} is called the sign function of an integer polynomial p of degree d in n variables if it is true that f(x) = 1 if and only if p(x) > 0. In this case the polynomial p is called a threshold gate of degree d for the function f. The weight of the threshold gate is the sum of the absolute values of the coefficients of p. For any n and d ≤ D ≤ $\frac{{\varepsilon n^{1/5} }} {{\log n}} $\frac{{\varepsilon n^{1/5} }} {{\log n}} we construct a function f such that there is a threshold gate of degree d for f, but any threshold gate for f of degree at most D has weight 2^{(dn)d /D4d} 2^{(\delta n)^d /D^{4d} } , where ɛ > 0 and δ > 0 are some constants. In particular, if D is constant, then any threshold gate of degree D for our function has weight 2^{W(nd )}2^{\Omega (n^d )} . Previously, functions with these properties have been known only for d = 1 (and arbitrary D) and for D = d. For constant d our functions are computable by polynomial size DNFs. The best previous lower bound on the weights of threshold gates for such functions was 2^Ω(n). Our results can also be translated to the case of functions f: {−1, 1} ⁿ → {−1, 1}.     

Convex subdivisions with low stabbing numbers

It is shown that for every subdivision of the d-dimensional Euclidean space, d ≥ 2, into n convex cells, there is a straight line that stabs at least Ω((log n/log log n)^1/(d−1)) cells. In other words, if a convex subdivision of d-space has the property that any line stabs at most k cells, then the subdivision has at most exp(O(k ^d−1 log k)) cells. This bound is best possible apart from a constant factor. It was previously known only in the case d = 2. Supported in part by NSERC grant RGPIN 35586.     

The smallest degree sum that yields potentially Kr,r-graphic sequences

We consider a variation of a classical Turán-type extremal problem as follows: Determine the smallest even integer σ(K_r,r,n) such that every n-term graphic sequence π = (d₁,d₂,...,d_n) with term sum σ(π) = d₁ + d₂ + ... + d_n ≥ σ(K_r,r,n) is potentially K_r,r-graphic, where K_r,r is an r × r complete bipartite graph, i.e. π has a realization G containing K_r,r as its subgraph. In this paper, the values σ(K_r,r,n) for even r and n ≥ 4r² - r - 6 and for odd r and n ≥ 4r² + 3r - 8 are determined.     

Curves with infinitely many points of fixed degree

Thed-th symmetric productC ^(d) of a curveC defined over a fieldK is closely related to the set of points ofC of degree ≤d. IfK is a number field, then a conjecture of Lang [Hi] proved by Faltings [Fa2] implies ifC ^(d) (K) is an infinite set, then there is aK-rational covering ofC → ℙ _|K ¹ of degree ≤2d. As an application one gets that for fixed fieldK and fixedd there are only finitely many primes ι such that the set of all elliptic curves defined over some extensionsL ofK with [L∶K]≤d and withL-rational isogeny of degree ι is infinite.     

A Polynomial-Time Algorithm to Approximate the Mixed Volume within a Simply Exponential Factor

Let K=(K ₁,…,K _n ) be an n-tuple of convex compact subsets in the Euclidean space R ⁿ , and let V(⋅) be the Euclidean volume in R ⁿ . The Minkowski polynomial V _K is defined as V _K (λ ₁,…,λ _n )=V(λ ₁ K ₁+⋅⋅⋅+λ _n K _n ) and the mixed volume V(K ₁,…,K _n ) as