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.     

Mean projections and finite packings of convex bodies

Consider the convex hullQ ofn non-overlapping translates of a convex bodyC inE ^d ,n be large. IfQ has minimali-dimensional projection, 1i<d then we prove thatQ is approximately a sphere.     

Homomorphisms onC ∞ (E) andC ∞-bounding sets

We prove, for the class of real locally convex spacesE that are continuously and linearly injectable into somec ₀(), that every non-zero homomorphism on the algebraC (E) ofC -functions onE is given by a point evaluation at some point ofE. Furthermore, if every real-valuedC -function on the weak topology of a quasi-complete locally convex spaceE is bounded on a subsetA ofE, thenA is relatively weakly compact.     

Finite sphere packing and sphere covering

A basic problem of finite packing and covering is to determine, for a given number ofk unit balls in Euclideand-spaceE ^d , (1) the minimal volume of all convex bodies into which thek balls can be packed and (2) the maximal volume of all convex bodies which can be covered by thek balls. In the sausage conjectures by L. Fejes Tóth and J. M. Wills it is conjectured that, for alld5, linear arrangements of thek balls are best possible. In the paper several partial results are given to support both conjectures. Furthermore, some relations between finite and infinite (space) packing and covering are investigated.This paper was written while the first named author was visiting the Forschungsinstitut für Geistes- und Sozialwissenschaften at the University of Siegen.     

Über diej-ten Überdeckungsdichten konvexer Körper

Let for positive integersj,k,d and convex bodiesK of Euclideand-spaceE ^d of dimension at leastj V _{j, k} (K) denote the maximum of the intrinsic volumesV _j (C) of those convex bodies whosej-skeleton skel _j (C) can be covered withk translates ofK. Then thej-thk-covering density θ _j,k (K) is the ratiok V _j (K)/V _j,k (K). In particular, θ _d,k refers to the case of covering the entire convex bodiesC and the density is measured with respect to the volume while forj=d-1 the surface of the bodiesC is covered and accordingly the density is measured with respect to the surface area. The paper gives the estimate $$1 \leqslant \theta _{j,k} (K)< e (j + \sqrt {\pi /2} \sqrt {d - j} )< (d + 1) e$$ for thej-thk-covering density and some related results.     

Applications of random sampling in computational geometry,II

We use random sampling for several new geometric algorithms. The algorithms are Las Vegas, and their expected bounds are with respect to the random behavior of the algorithms. These algorithms follow from new general results giving sharp bounds for the use of random subsets in geometric algorithms. These bounds show that random subsets can be used optimally for divide-and-conquer, and also give bounds for a simple, general technique for building geometric structures incrementally. One new algorithm reports all the intersecting pairs of a set of line segments in the plane, and requiresO(A+n logn) expected time, whereA is the number of intersecting pairs reported. The algorithm requiresO(n) space in the worst case. Another algorithm computes the convex hull ofn points inE ^d inO(n logn) expected time ford=3, andO(n ^[d/2]) expected time ford>3. The algorithm also gives fast expected times for random input points. Another algorithm computes the diameter of a set ofn points inE ³ inO(n logn) expected time, and on the way computes the intersection ofn unit balls inE ³. We show thatO(n logA) expected time suffices to compute the convex hull ofn points inE ³, whereA is the number of input points on the surface of the hull. Algorithms for halfspace range reporting are also given. In addition, we give asymptotically tight bounds for (k)-sets, which are certain halfspace partitions of point sets, and give a simple proof of Lee's bounds for high-order Voronoi diagrams.     

Homomorphisms on some function algebras

In this note we prove, for some classes of real locally convex spacesE including all complete Schwartz spaces, that every non-zero homomorphism on the algebraC (E) ofC -functions onE is given by a point evaluation at some point ofE.     

Finite coverings by translates of centrally symmetric convex domains

Bambah and Rogers proved that the area of a convex domain in the plane which can be covered byn translates of a given centrally symmetric convex domainC is at most (n–1)h(C)+a(C), whereh(C) denotes the area of the largest hexagon contained inC anda(C) stands for the area ofC. An improvement with a term of magnitude n is given here. Our estimate implies that ifC is not a parallelogram, then any covering of any convex domain by at least 26 translates ofC is less economic than the thinnest covering of the whole plane by translates ofC.     

The different ways of stabbing disjoint convex sets

We construct a family ofn disjoint convex set in ^d having (n/(d–1)) ^d–1 geometric permutations. As well, we complete the enumeration problem for geometric permutations of families of disjoint translates of a convex set in the plane, settle the case for cubes in ^d , and construct a family ofd+1 translates in ^d admitting (d+1)!/2 geometric permutations.This research was partly supported by NSERC Grants A3062, A5137, and A8761.     

Two comments on Dvoretzky’s sphericity theorem

For any two positive integersk, l and anyɛ>0 there exists anN(k, l, ɛ) so that given anyl convex bodiesC ₁, …,C _l symmetric about the origin inE ⁿ withn≧N there exists a subspaceE ^k so that eachC _i intersectsE ^k, or has a projection intoE ^k, in a set which is nearly spherical (asphericity <ɛ). The measure of the totality ofE ^k which intersect a given body inE ⁿ in a nearly ellipsoidal set is considered and an affine invariant measure is introduced for that purpose.     

Independent collections of translates of boxes and a conjecture due to Grünbaum

A collection ofn setsA ₁, ...,A _n is said to beindependent provided every set of the formX ₁ ... X _n is nonempty, where eachX _i is eitherA _i orA _i ^c . We give a simple characterization for when translates of a given box form an independent set inR ^d. We use this to show that the largest number of such boxes forming an independent set inR ^d is given by 3d/2 ford2. This settles in the negative a conjecture of Grünbaum (1975), which states that the maximum size of an independent collection of sets homothetic to a fixed convex setC inR ^d isd+1. It also shows that the bound of 2d of Rényiet al. (1951) for the maximum number of boxes (not necessarily translates of a given one) with sides parallel to the coordinate axes in an independent collection inR ^d can be improved for these special collections.Daniel Q. Naiman was supported by National Science Foundation Grant No. DMS-9103126. Henry P. Wynn was supported by the Science and Engineering Research Council, UK.     

Solution of Hadwiger-Levi's Covering Problem for Duals of Cyclic 2k-Polytopes

For a collection C of convex bodies let h(C) be the minimum number m with the property that every element K of C can be covered by m or fewer smaller homothetic copies of K. Denote by C _d ^* the collection of all duals of cyclic d-polytopes, d 2. We show that h(C _2k ^* )=(k +1)2 for any k 2. We also prove the inequalities (d+1) (d+3)/4 h(C _d ^* ) (d+1) 2/2$ for any d 2.     

On the graph of large distances

For a setS of points in the plane, letd ₁>d ₂>... denote the different distances determined byS. Consider the graphG(S, k) whose vertices are the elements ofS, and two are joined by an edge iff their distance is at leastd _k . It is proved that the chromatic number ofG(S, k) is at most 7 if |S|constk ². IfS consists of the vertices of a convex polygon and |S|constk ², then the chromatic number ofG(S, k) is at most 3. Both bounds are best possible. IfS consists of the vertices of a convex polygon thenG(S, k) has a vertex of degree at most 3k – 1. This implies that in this case the chromatic number ofG(S, k) is at most 3k. The best bound here is probably 2k+1, which is tight for the regular (2k+1)-gon.     

On linear sections of lattice packings

Ind-dimensional euclidean spaceE ^d letP be a lattice packing of subsets ofE ^d , and letH be ak-dimensional linear subspace ofE ^d (0<k<d). Then,P induces a packing inH consisting of all setsPH withPP. The relationship between the density of this packing inH and the density ofP is investigated. A result from the theory of uniform distribution of linear forms is used to prove an integral formula that enables one to evaluate the density of the induced packing inH (under suitable assumptions on the sets ofP and the functionals used to define the densities). It is shown that this result leads to explicit formulas for the averages of the induced densities under the rotation ofH. If the densities are taken with respect to the mean cross-sectional measures of convex bodies one obtains analogues of the integral geometric intersection formulas of Crofton.Dedicated to Professor E. Hlawka on the occasion of his seventieth birthdaySupported by National Science Foundation Research Grant DMS 8300825.     

Straffe Untermannigfaltigkeiten in konvexen Hyperflächen

It will be proved that a tight substantial embedding ofS ^m×Sⁿ intoE ^m+n+2 whose image lies in a strictly convex hypersurface is projectively equivalent to the productC ₁×C ₂E ^m+1×E ^m+1=E ^m+n+2 of two convex hypersurfacesC ₁ undC ₂.     

On coverings of plane convex sets by translates of strips

In the euclidean planeE ² letS ₁,S ₂, ... be a sequence of strips of widthsw ₁,w ₂, .... It is shown thatE ² can be covered by translates of the stripsS _i if w ₁ ^3/2 = . Further results concern conditions in order that a compact convex domain inE ² can be covered by translates ofS ₁,S ₂, ....This research was supported by National Science Foundation Research Grant MCS 76-06111.     

Arrangements of oriented hyperplanes

An arrangement ofn oriented hyperplanes or half-spaces dividesE ^d into a certain number of convex cells. We study the numberc _k of cells which are covered by exactlyk half-spaces and derive an upper bound onc _k for givenn andd.     

Distribution-independent properties of the convex hull of random points

Denote byV _n ^(d) the expected volume of the convex hull ofn points chosen independently according to a given probability measure in Euclideand-spaceE ^d. Ifd=2 ord=3 and is the measure corresponding to the uniform distribution on a convex body inE ^d, Affentranger and Badertscher derived that

On hyperplanes and polytopes

We call a convex subsetN of a convexd-polytopePE ^d ak-nucleus ofP ifN meets everyk-face ofP, where 0<k<d. We note thatP has disjointk-nuclei if and only if there exists a hyperplane inE ^d which bisects the (relative) interior of everyk-face ofP, and that this is possible only if [d+2/2]kd–1. Our main results are that any convexd-polytope with at most 2d–1 vertices (d3) possesses disjoint (d–1)-nuclei and that 2d–1 is the largest possible number with this property. Furthermore, every convexd-polytope with at most 2d facets (d3) possesses disjoint (d–1)-nuclei, 2d cannot be replaced by 2d+2, and ford=3, six cannot be replaced by seven.Partially supported by Hung. Nat. Found. for Sci. Research number 1238.Partially supported by the Natural Sciences and Engineering Council of Canada.Partially supported by N.S.F. grant number MCS-790251.     

A simple proof of an approximation theorem of H. Minkowski

It is proved that every convex bodyC inR ⁿ can be approximated by a sequenceC _k of convex bodies, whose boundary is the intersection of a level set of a homogeneous polynomial of degree 2k and a hyperplane. The Minkowski functional ofC _k is given explictly. Some further nice properties of the approximantsC _k are proved.Supported in part by BSF and Erwin Schrödinger Auslandsstipendium J0630.