Combinatorial geometry of Minkowski spaces

We study aspects of the Combinatorial Geometry of finite dimensional Banach spaces (i.e., Minkowski spaces) and of convex bodies. Minkowski spaces are used to model radial anisotropy, for example crystal growth. This type of Minkowski space should not be confused with the Minkowskian space of the theory of Special Relativity, nor with the Minkowski planes in the Foundations of Geometry.

The aspects we study are extremal combinatorial distance problems, minimal networks and Helly-type theorems.

Firstly we address combinatorial distance counting questions in the spirit of Erdos. We make a general conjecture on the cardinality of k-distance sets which we prove for all 2-dimensional Minkowski spaces and for all finite dimensional sup norm spaces. We also provide various statements weaker than the conjecture.

Then we show that certain threshold phenomena hold for the asymptotic growth rates of sets of unit vectors satisfying various norm inequalities as the dimension becomes large, in spaces with the p-norm, as well as in general Minkowski spaces. Using this, we find a characterization of the 3-dimensional octahedron in the class of all finite dimensional convex bodies.

We then apply these results to find new lower bounds for Hadwiger numbers of the unit balls of spaces with the p-norm. We discuss the connection between Hadwiger numbers and vertex degrees of Minimal Spanning Trees in Minkowski spaces, and note some further bounds on these numbers. We also consider vertex degrees of Steiner Minimal Trees in smooth Minkowski spaces, extending work of Lawlor and Morgan (1994), and Furedi, Lagarias and Morgan (1991). In particular, we find new upper bounds for vertex degrees in the p-norm, which has algorithmic applications.

Lastly we study Helly-type theorems involving boundaries of convex sets. Some of these results, such as a conjecture of Maehara (1989) may be formulated in a Minkowski space setting. We give a Helly-type theorem for boundaries of convex discs in the plane, and for boundaries of axis-aligned boxes in higher dimensions. We finally examine a certain parameter of Minkowski spaces related to Maehara's conjecture, and completely determine it for all 2- and 3-dimensional spaces.