Subdivision algorithms and the kernel of a polyhedron

The kernelK of a convex polyhedronP ₀, as defined by L. Fejes Tóth, is the limit of the sequence (P _n), whereP _n is the convex hull of the midpoints of the edges ofP _n−1. The boundary ∂K of the convex bodyK is investigated. It is shown that ∂K contains no two-dimensional faces and that ∂K need not belong toC ². The connection with similar algorithms from CAD (computer aided design) is explained and utilized. R. J. Gardner was supported in part by a von Humboldt fellowship.     

Packings of Unequal Circles in a Convex Set

   Abstract. In the Euclidean plane let T be a convex set, and let K ₁ , ..., K _n be a family of n ≥ 2 circles packed into T . We show that the density of each such packing is smaller than

On extremal point distributions in the Euclidean plane

We ask for the maximum σ _n ^γ of Σ _i,j=1 ⁿ ‖x _i-x _j‖^γ, where x ₁,χ,x _n are points in the Euclidean plane R ² with ‖x_i-x_j‖ ≦1 for all 1≦ i,j ≦ n and where ‖.‖^γ denotes the γ-th power of the Euclidean norm, γ ≧ 1. (For γ =1 this question was stated by L. Fejes Tóth in [1].) We calculate the exact value of σ _n ^γ for all γ γ 1,0758χ and give the distributions which attain the maximum σ _n ^γ . Moreover we prove upper bounds for σ _n ^γ for all γ ≧ 1 and calculate the exact value of σ ₄ ^γ for all γ ≧ 1. This revised version was published online in June 2006 with corrections to the Cover Date.     

Bounds for Local Density of Sphere Packings and the Kepler Conjecture

This paper formalizes the local density inequality approach to getting upper bounds for sphere packing densities in R ⁿ . This approach was first suggested by L. Fejes Tóth in 1953 as a method to prove the Kepler conjecture that the densest packing of unit spheres in R ³ has density π/\sqrt 18 , which is attained by the ``cannonball packing.' Local density inequalities give upper bounds for the sphere packing density formulated as an optimization problem of a nonlinear function over a compact set in a finite-dimensional Euclidean space. The approaches of Fejes Tóth, of Hsiang, and of Hales to the Kepler conjecture are each based on (different) local density inequalities. Recently Hales, together with Ferguson, has presented extensive details carrying out a modified version of the Hales approach to prove the Kepler conjecture. We describe the particular local density inequality underlying the Hales and Ferguson approach to prove Kepler's conjecture and sketch some features of their proof. Received November 19, 1999, and in revised form April 17, 2001. Online publication December 17, 2001.     

Points surrounding the origin

Suppose d > 2, n > d+1, and we have a set P of n points in d-dimensional Euclidean space. Then P contains a subset Q of d points such that for any p ∈ P, the convex hull of Q∪{p} does not contain the origin in its interior. We also show that for non-empty, finite point sets A ₁, ..., A _d+1 in ℝ ^d , if the origin is contained in the convex hull of A _i ∪ A _j for all 1≤i<j≤d+1, then there is a simplex S containing the origin such that |S∩A _i |=1 for every 1≤i≤d+1. This is a generalization of Bárány’s colored Carathéodory theorem, and in a dual version, it gives a spherical version of Lovász’ colored Helly theorem. Dedicated to Imre Bárány, Gábor Fejes Tóth, László Lovász, and Endre Makai on the occasion of their sixtieth birthdays. Supported by the Norwegian research council project number: 166618, and BK 21 Project, KAIST. Part of the research was conducted while visiting the Courant Institute of Mathematical Sciences. Supported by NSF Grant CCF-05-14079, and by grants from NSA, PSC-CUNY, the Hungarian Research Foundation OTKA, and BSF.     

Unavoidable Crossings in a Thinnest Plane Covering with Congruent Convex Disks

Two convex disks K and L in the plane are said to cross each other if the removal of their intersection causes each disk to fall into disjoint components. Almost all major theorems concerning the covering density of a convex disk were proved only for crossing-free coverings. This includes the classical theorem of L. Fejes Tóth (Acta Sci. Math. Szeged 12/A:62–67, 1950) that uses the maximum area hexagon inscribed in the disk to give a significant lower bound for the covering density of the disk. From the early seventies, all attempts of generalizing this theorem were based on the common belief that crossings in a plane covering by congruent convex disks, being counterproductive for producing low density, are always avoidable. Partial success was achieved not long ago, first for “fat” ellipses (A. Heppes in Discrete Comput. Geom. 29:477–481, 2003) and then for “fat” convex disks (G. Fejes Tóth in Discrete Comput. Geom. 34(1):129–141, 2005), where “fat” means of shape sufficiently close to a circle. A recently constructed example will be presented here, showing that, in general, all such attempts must fail. Three perpendiculars drawn from the center of a regular hexagon to its three nonadjacent sides partition the hexagon into three congruent pentagons. Obviously, the plane can be tiled by such pentagons. But a slight modification produces a (non-tiling) pentagon with an unexpected covering property: every thinnest covering of the plane by congruent copies of the modified pentagon must contain crossing pairs. The example has no bearing on the validity of Fejes Tóth’s bound in general, but it shows that any prospective proof must take into consideration the existence of unavoidable crossings.     

The maximal (C,α,β) operator on Hp(T×T)

The two-dimensional classical Hardy space H_p(T×T) on the bidisc are introduced, and it is shown that the maximal operator of the (C,α,β) means of a distribution is bounded from the space H_p(T×T) to L_p(T²) (1/(α+1), 1/(β+1)<p≤∞), and is of weak type (H ₁ ^# (T×T), L₁(T²)), where the Hardy space H ₁ ^# (T×T) is defined by the hybrid maximal function. As a consequence we obtain that the (C, α, β) means of a function f∈H ₁ ^# (T×T)⊃LlogL(T ²) convergs a. e. to the function in question. Moreover, we prove that the (C, α, β) means are uniformly bounded on the spaces H_p(T×T) whenever 1/(α+1), 1(β+1)<p<∞. Thus, in case f∈H_p(T×T), the (C, α, β) means convergs to f in H_p(T×T) norm whenever (1/(α+1), 1/(β+1)<p<∞). The same results are proved for the conjugate (C, α, β) means, too. This research was made while the author was visiting the Humboldt University in Berlin supported by the Alexander von Humboldt Foundation.     

On Order Types of Systems of Segments in the Plane

Let r(n) denote the largest integer such that every family C\mathcal{C} of n pairwise disjoint segments in the plane in general position has r(n) members whose order type can be represented by points. Pach and Tóth gave a construction that shows r(n) < n ^log8/log9 (Pach and Tóth 2009). They also stated that one can apply the Erdős–Szekeres theorem for convex sets in Pach and Tóth (Discrete Comput Geom 19:437–445, 1998) to obtain r(n) > log₁₆ n. In this note, we will show that r(n) > cn ^1/4 for some absolute constant c.     

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.     

The maximal (C,α,β) operator on Hp(T×T)

The two-dimensional classical Hardy space H_p(T×T) on the bidisc are introduced, and it is shown that the maximal operator of the (C,α,β) means of a distribution is bounded from the space H_p(T×T) to L_p(T²) (1/(α+1), 1/(β+1)<p≤∞), and is of weak type (H ₁ ^# (T×T), L₁(T²)), where the Hardy space H ₁ ^# (T×T) is defined by the hybrid maximal function. As a consequence we obtain that the (C, α, β) means of a function f∈H ₁ ^# (T×T)⊃LlogL(T ²) convergs a. e. to the function in question. Moreover, we prove that the (C, α, β) means are uniformly bounded on the spaces H_p(T×T) whenever 1/(α+1), 1(β+1)<p<∞. Thus, in case f∈H_p(T×T), the (C, α, β) means convergs to f in H_p(T×T) norm whenever (1/(α+1), 1/(β+1)<p<∞). The same results are proved for the conjugate (C, α, β) means, too.     

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

Smooth convex bodies with proportional projection functions

For a convex body K ⊂ ℝⁿ and i ∈ {1, …, n − 1}, the function assigning to any i-dimensional subspace L of ℝⁿ, the i-dimensional volume of the orthogonal projection of K to L, is called the i-th projection function of K. Let K, K ₀ ⊂ ℝⁿ be smooth convex bodies with boundaries of class C ² and positive Gauss-Kronecker curvature and assume K ₀ is centrally symmetric. Excluding two exceptional cases, (i, j) = (1, n − 1) and (i, j) = (n − 2, n − 1), we prove that K and K ₀ are homothetic if their i-th and j-th projection functions are proportional. When K ₀ is a Euclidean ball this shows that a convex body with C ² boundary and positive Gauss-Kronecker with constant i-th and j-th projection functions is a Euclidean ball. The second author was supported in part by the European Network PHD, FP6 Marie Curie Actions, RTN, Contract MCRN-511953.     

On L. Fejes Tóth’s “sausage-conjecture”

Letk non-overlapping translates of the unitd-ballB ^d ⊂E ^d be given, letC _k be the convex hull of their centers, letS _k be a segment of length 2(k−1) and letV denote the volume. L. Fejes Tóth's sausage conjecture, says that ford≧5V(S _k +B ^d ) ≦V(C _k +B ^d In the paper partial results are given.     

L p − Lq estimates for convolution operators with n-Dimensional singular measures

Let S ⊂ ℜⁿ⁺¹ be the graph of the function ϕ :[−1, 1] ⁿ → ℜ defined by ϕ (x ₁ , …, x_n) = ∑ _j=1 ⁿ |x_j|^αj, with1<α ₁ ≤ … ≤ α_n, let σ the Euclidean area measure on S. In this article we study the L^p − L^q boundedness of convolution operators with the singular Borel measure on Rⁿ⁺¹ given by μ (E)=σ (E ∩ S)     

Lattice Polytopes with Distinct Pair-Sums

Let P be a lattice polytope in R ⁿ , and let P \cap Z ⁿ = {v ₁ ,\ldots,v _N } . If the N + N\choose 2 points 2v ₁ ,\ldots, 2v _N ;v ₁ +v ₂ ,\ldots, v _N-1 + v _N are distinct, we say that P is a ``distinct pair-sum' or ``dps' polytope. We show that if P is a dps polytope in R ⁿ , then N≤ 2 ⁿ , and, for every n , we construct dps polytopes in R ⁿ which contain 2 ⁿ lattice points. We also discuss the relation between dps polytopes and the study of sums of squares of real polynomials. Received November 10, 2000, and in revised form June 28, 2001. Online publication November 2, 2001.     

Dérivé convexe d’une loi de probabilité et lois stables. Application a un problème d’isomorphisme

The “convex derived set” of a symmetric probability lawF on the real line is defined as the set of limits of laws ∗ _j−1/k ⁿ F(t _j ⁿ η), inf 1≤j≤k _n t _j ⁿ →∞ ifn→∞ and the stable laws it contains are exhibited. A new criterion of stochastic compacity of the set of the powers of a probability law is established. Finally, an isomorphism theorem between somel ^p andL ⁰ spaces is given.

---

---

Laboratoire associé au C.N.R.S. n^o 224 “Processus stochastiques et applications”.     

Poisson Numbers and Poisson Distributions in Subset Surprisology

Given a family of k + 1 real-valued functions f₀ , ?,f_kf_0 , \ldots ,f_k defined on the set { 1, ?,n}\{ 1, \ldots ,n\} and measuring the intensity of certain signals, we want to investigate whether these functions are T₀ , ?,T_k ,T_0 , \ldots ,T_k , the size a of the collection of numbers j ? { 1, ?,n}j \in \{ 1, \ldots ,n\} whose signals f₀ (j), ?,f_k (j)f_0 (j), \ldots ,f_k (j) exceed the corresponding threshold values T₀ , ?,T_kT_0 , \ldots ,T_k simultaneously for all 0, ?,k0, \ldots ,k is surprisingly large (or small) in comparison to the family of cardinalities

Fractional Poisson equations and ergodic theorems for fractional coboundaries

For a given contractionT in a Banach spaceX and 0<α<1, we define the contractionT _α=Σ _j=1 ^∞ a _j T ^j , where {a _j } are the coefficients in the power series expansion (1-t)^α=1-Σ _j=1 ^∞ a _j t ^j in the open unit disk, which satisfya _j >0 anda _j >0 and Σ _j=1 ^∞ a _j =1. The operator calculus justifies the notation(I−T) ^α :=I−T _α (e.g., (I−T _1/2)²=I−T). A vectory∈X is called an, α-fractional coboundary for T if there is anx∈X such that(I−T) ^α x=y, i.e.,y is a coboundary forT _α . The fractional Poisson equation forT is the Poisson equation forT _α . We show that if(I−T)X is not closed, then(I−T) ^α X strictly contains(I−T)X (but has the same closure). ForT mean ergodic, we obtain a series solution (converging in norm) to the fractional Poisson equation. We prove thaty∈X is an α-fractional coboundary if and only if Σ _k=1 ^∞ T ^k y/k ^1-α converges in norm, and conclude that lim _n ‖(1/n ^1-α)Σ _k=1 ⁿ T ^k y‖=0 for suchy. For a Dunford-Schwartz operatorT onL ₁ of a probability space, we consider also a.e. convergence. We prove that iff∈(I−T) ^α L ₁ for some 0<α<1, then the one-sided Hilbert transform Σ _k=1 ^∞ T ^k f/k converges a.e. For 1<p<∞, we prove that iff∈(I−T) ^α L _p with α>1−1/p=1/q, then Σ _k=1 ^∞ T ^k f/k ^1/p converges a.e., and thus (1/n ^1/p ) Σ _k=1 ⁿ T ^k f converges a.e. to zero. Whenf∈(I−T) ^1/q L _p (the case α=1/q), we prove that (1/n ^1/p (logn)^1/q )Σ _k=1 ⁿ T ^k f converges a.e. to zero.     

Analytic Semigroups on H 1 (Ω) Generated by Degenerate Elliptic Operators

One proves that Ay=aΔ y+b⋅ \nabla y , D(A)={y∈ H ¹ (Ω ); aΔ y+b⋅ \nabla y∈ H ₀ ¹ (Ω ), \sqrt a Δ y∈ L ² (Ω )} generates, under suitable conditions on a and b , a C ₀ -analytic semigroup on H ¹ (Ω) . September 5, 1999     

Wavelet expansions of fractal measures

Let μ be a measure on ℝⁿ that satisfies the estimate μ(B _r(x))≤cr ^α for allx ∈ ℝⁿ and allr ≤ 1 (B _r(x) denotes the ball of radius r centered atx. Let ϕ _j,k ^(ɛ) (x)=2 ^nj2ϕ^(ɛ)(2 ^j x-k) be a wavelet basis forj ∈ ℤ, κ ∈ ℤⁿ, and ∈ ∈E, a finite set, and letP _j (T)=Σ_ɛ,k <T,ϕ _j,k ^(ɛ) >ϕ _j,k ^(ɛ) denote the associated projection operators at levelj (T is a suitable measure or distribution). Iff ∈Ls ^p(dμ) for 1 ≤p ≤ ∞, we show thatP _j(f dμ) ∈ L^p(dx) and ||P _j (fdμ)||L _p(dx)≤c2 ^{j((n-α)/p′))}||f||L _p(dμ) for allj ≥ 0. We also obtain estimates for the limsup and liminf of ||P _j (fdμ)||L _p(dx) under more restrictive hypotheses. Communicated by Guido Weiss