Some characterisations of the ellipsoid

We show that a convex bodyK of dimensiond≧3 is an ellipsoid if it has any of the following properties: (1) the “grazes” of all points close toK are flat, (2) all sections of small diameter are centrally symmetric, (3) parallel (d−1)-sections close to the boundary are width-equivalent, (4)K is strictly convex and all (d−1)-sections close to the boundary are centrally symmetric; the last two results are deduced from their 3-dimensional cases which were proved by Aitchison.     

Constant Minkowskian width in terms of double normals

We extend the notion of a double normal of a convex body from smooth, strictly convex Minkowski planes to arbitrary two-dimensional real, normed, linear spaces in two different ways. Then, for both of these ways, we obtain the following characterization theorem: a convex body K in a Minkowski plane is of constant Minkowskian width iff every chord I of K splits K into two compact convex sets K₁ and K₂ such that I is a Minkowskian double normal of K₁ or K₂. Furthermore, the Euclidean version of this theorem yields a new characterization of d-dimensional Euclidean ball where d 3.     

Exponential Lower Bound for the Translative Kissing Numbers of d -Dimensional Convex Bodies

The translative kissing number H(K) of a d -dimensional convex body K is the maximum number of mutually nonoverlapping translates of K which touch K . In this paper we show that there exists an absolute constant c > 0 such that H(K)≥ 2 ^cd for every positive integer d and every d -dimensional convex body K . We also prove a generalization of this result for pairs of centrally symmetric convex bodies. <lsiheader> <onlinepub>26 June, 1998 <editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; <pdfname>19n3p447.pdf <pdfexist>yes <htmlexist>no <htmlfexist>no <texexist>yes <sectionname> </lsiheader> Received February 18, 1997, and in revised form April 15, 1997.     

On Translational Clouds for a Convex Body

For a d-dimensional convex body K let C(K) denote the minimum size of translational clouds for K. That is, C(K) is the minimum number of mutually non-overlapping translates of K which do not overlap K and block all the light rays emanating from any point of K. In this paper we prove the general upper bound . Furthermore, for an arbitrary centrally symmetric d-dimensional convex body S we show . Finally, for the d-dimensional ball B^d we obtain the bounds .     

Some remarks concerning kissing numbers,blocking numbers and covering numbers

This article shows an inequality concerning blocking numbers and Hadwiger's covering numbers and presents a strange phenomenon concerning kissing numbers and blocking numbers. As a simple corollary, we can improve the known upper bounds for Hadwiger's covering numbers ford-dimensional centrally symmetric convex bodies to 3 ^d –1.     

An acyclicity theorem for cell complexes ind dimension

LetC be a cell complex ind-dimensional Euclidean space whose faces are obtained by orthogonal projection of the faces of a convex polytope ind+ 1 dimensions. For example, the Delaunay triangulation of a finite point set is such a cell complex. This paper shows that the in_front/behind relation defined for the faces ofC with respect to any fixed viewpointx is acyclic. This result has applications to hidden line/surface removal and other problems in computational geometry.Research reported in this paper was supported by the National Science Foundation under grant CCR-8714565     

Covering Convex Bodies by Cylinders and Lattice Points by Flats

In connection with an unsolved problem of Bang (1951) we give a lower bound for the sum of the base volumes of cylinders covering a d-dimensional convex body in terms of the relevant basic measures of the given convex body. As an application we establish lower bounds on the number of k-dimensional flats (i.e. translates of k-dimensional linear subspaces) needed to cover all the integer points of a given convex body in d-dimensional Euclidean space for 1≤k≤d−1. K. Bezdek and A.E. Litvak are partially supported by a Natural Sciences and Engineering Research Council of Canada Discovery Grant.     

Enumeration of three-dimensional convex polygons

A self-avoiding polygon (SAP) on a graph is an elementary cycle. Counting SAPs on the hypercubic lattice ℤ ^d withd≥2, is a well-known unsolved problem, which is studied both for its combinatorial and probabilistic interest and its connections with statistical mechanics. Of course, polygons on ℤ ^d are defined up to a translation, and the relevant statistic is their perimeter. A SAP on ℤ ^d is said to beconvex if its perimeter is “minimal”, that is, is exactly twice the sum of the side lengths of the smallest hyper-rectangle containing it. In 1984, Delest and Viennot enumerated convex SAPs on the square lattice [6], but no result was available in a higher dimension. We present an elementar approach to enumerate convex SAPs in any dimension. We first obtain a new proof of Delest and Viennot's result, which explains combinatorially the form of the generating function. We then compute the generating function for convex SAPs on the cubic lattice. In a dimension larger than 3, the details of the calculations become very cumbersome. However, our method suggests that the generating function for convex SAPs on ℤ ^d is always a quotient ofdifferentiably finite power series.     

The generic contact of convex bodies with circumscribed homothets of a convex surface

LetS ₀ be a convex surface ind-dimensional Euclidean spaceE ^d . Then, ifS ₀ is smooth and strictly convex, we prove that the typical convex body touches the convex suface circumscribed about it and homothetic toS ₀ at preciselyd+1 points.     

Inradii of Simplices

We study the following generalization of the inradius: For a convex body K in the d-dimensional Euclidean space and a linear k-plane L we define the inradius of K with respect to L by , where r(K;x+L) denotes the ordinary inradius of with respect to the affine plane x+L. We show how to determine for polytopes and use the result to estimate for the regular d-simplex T_r ^d . These estimates are optimal for all k in infinitely many dimensions and for certain k in the remaining dimensions. Received July 5, 1996, and in revised form August 8, 1996.     

Induced Subdivisions In <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">s,s</Emphasis></Subscript>-Free Graphs of Large Average Degree

We prove that for every graph H and for every s there exists d=d(H,s) such that every graph of average degree at least d contains either a K_s,s as a subgraph or an induced subdivision of H.     

Monotonicity of the cd-index for polytopes

We prove that the cd-index of a convex polytope satisfies a strong monotonicity property with respect to the cd-indices of any face and its link. As a consequence, we prove for d-dimensional polytopes a conjecture of Stanley that the cd-index is minimized on the d-dimensional simplex. Moreover, we prove the upper bound theorem for the cd-index, namely that the cd-index of any d-dimensional polytope with n vertices is at most that of C(n,d), the d-dimensional cyclic polytope with n vertices. Received September 29, 1998; in final form February 8, 1999     

A counterexample to Valette’s conjecture

We disprove a well-known conjecture of D. Vallete (1978), which states that every d-dimensional self-affine convex body is a direct product of a polytope with a convex body of lower dimension. It is shown that there are counterexamples for dimension d = 4. Additional assumptions under which the conjecture is true are discussed.     

The Number Of Unique-Sink Orientations of the Hypercube*

Let Q_d denote the graph of the d-dimensional cube. A unique-sink orientation (USO) is an orientation of Q_d such that every face of Q_n has exactly one sink (vertex of out degree 0); it does not have to be acyclic. USO have been studied as an abstract model for many geometric optimization problems, such as linear programming, finding the smallest enclosing ball of a given point set, certain classes of convex programming, and certain linear complementarity problems. It is shown that the number of USO is . * This research was partially supported by ETH Zürichan d done in part during the workshop “Towards the Peak” in La Claustra, Switzerland and during a visit to ETH Zürich.     

On the Simplest Inverse Problem for Sums of Sets in Several Dimensions

d -dimensional sets having the smallest cardinality of the sum set. Let be a finite d-dimensional set such that . If , then K consists of d parallel arithmetic progressions with the same common difference. We also establish the structure of K in the remaining cases . Received: February 5, 1996/Revised: November 20, 1997     

Formulae and growth rates of high-dimensional polycubes

A d-dimensional polycube is a facet-connected set of cubes in d dimensions. Fixed polycubes are considered distinct if they differ in their shape or orientation. A proper d-dimensional polycube spans all the d dimensions, that is, the convex hull of the centers of its cubes is d-dimensional. In this paper we prove rigorously some (previously conjectured) closed formulae for fixed (proper and improper) polycubes, and show that the growth-rate limit of the number of polycubes in d dimensions is 2ed−o(d). We conjecture that it is asymptotically equal to (2d−3)e+O(1/d).     

The chance that a convex body is lattice‐point free: A relative of Buffon's needle problem

Given a convex body K ⊂ R ^d, what is the probability that a randomly chosen congruent copy, K^*, of K is lattice‐point free, that is, K^*∩ Z ^d = ∅︁? Here Z ^d is the usual lattice of integer points in R ^d. Luckily, the underlying probability is well defined since integer translations of K can be factored out. The question came up in connection with integer programming. We explain what the answer is for convex bodies of large enough volume. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

A local characterization of the johnson scheme

Within the Johnson schemeI(m, d) we find the graphK(m, d) ofd-subsets of anm-set, two such adjacent when disjoint. Among all connected graphs,K(m, d) is characterized by the isomorphism type of its vertex neighborhoods providedm is sufficiently large compared tod. Partial support provided by NSF (USA), SERC (UK), ZWO (NL).     

Illuminating Spindle Convex Bodies and Minimizing the Volume of Spherical Sets of Constant Width

A subset of the d-dimensional Euclidean space having nonempty interior is called a spindle convex body if it is the intersection of (finitely or infinitely many) congruent d-dimensional closed balls. The spindle convex body is called a “fat” one, if it contains the centers of its generating balls. The core part of this paper is an extension of Schramm’s theorem and its proof on illuminating convex bodies of constant width to the family of “fat” spindle convex bodies. Also, this leads to the spherical analog of the well-known Blaschke–Lebesgue problem.     

The minimum number of vertices of a simple polytope

Ad-polytope is ad-dimensional set that is the convex hull of a finite number of points. Ad-polytope is simple provided each vertex meets exactlyd edges. It has been conjectured that for simple polytopes {fx121-1} wheref _i is the number ofi-dimensional faces of the polytope. In this paper we show that inequality (i) holds for all simple polytopes. Research supported by N.S.F. Grant GP-19221.