Geometry of Minkowski spaces. Survey

EXPOSITIONES ELSEVIER

Expo, Math. 22 (2004): 93-144 http://www.elsevier.de/expornath

MATHEMATICAE

The Geometry of Minkowski Spaces - A Survey. Part II* H. Martini a and K. J. Swanepoel 2 1 Fakult~it fiir Mathematik, Technische Universit~t Chemnitz, 09107 Chemnitz, Germany 2 Department of Mathematics, Applied Mathematics and Astronomy, University of South Africa, PO Box 392, Pretoria 0003, South Africa Abstract. In this second part of a series of surveys on the geometry of finite dimensional Banach spaces (Minkowski spaces) we discuss results that refer to the following three topics: bodies of constant Minkowski width, generalized convexity notions that are important for Minkowski spaces, and bisectors as well as Voronoi diagrams in Minkowski spaces. Keywords: Minkowski Geometry, Minkowski spaces, finite dimensional normed spaces, bisectors, Voronoi diagrams, bodies of constant width, generalized convexity

1

Introduction

This paper isthe second part of a planned seriesof surveys on Minkowski Geometry, which is the geometry of finitedimensional normed linear spaces (= Minkowski spaces). The origins and basic developments of Minkowski Geometry are connected with names such as Riemann, Minkowski and Busemann, see the Preface of [283] and [196, § 2] for more information. This field can be located at the intersection of Finsler Geometry, Banach Space Theory and Convex Geometry, but it is also closely related to Distance Geometry (in the spirit of Meager and Blumenthal [28]) and was enriched by many results from applied disciplines such as Operations Research, Optimization, Theoretical Computer Science and Location Theory. The motivation for this series of surveys is given by the facts that there are hundreds of papers in Minkowski Geometry, widespread in very different fields, previous surveys are old, and the recent excellent monograph [283] covers mainly the analytical part of the theory. In Part I [196] we placed special emphasis on planar results, in some cases with simplified proofs. Thus Part I can be seen as fundamental for the parts following it. In Part II we survey three topics from Minkowski Geometry that are very geometric in nature and show interesting relations to further disciplines, such as Classical Convexity, Abstract Convexity, Computational Geometry and the Foundations of Geometry. B o d i e s o f c o n s t a n t w i d t h are well studied in Convex Geometry. The extensive knowledge on these special convex bodies in Euclidean space is summarized in the surveys [60] and [131]. Although these surveys and the monograph [283] also contain material on bodies of constant width in Minkowski spaces, a complete summary is missing. Our first *MSC 2000 Subject Classification: Primary 46-02; secondary 52A21,46B20. E-mail addresses: [email protected], [email protected] 0732-0869104122/02-93 $30.00/0

94

H. Martini and K. J. Swanepoel

section below is the first and, as we believe, complete survey on this subject. It gives an example of how strongly Classical Convexity and Minkowski Geometry are related to each other. G e n e r a l i z e d convexity notions in the sense of metric convexity were studied in Distance Geometry and Abstract Convexity. Some of these notions are especially interesting in the context of Minkowski Geometry and applications thereof, e.g. in Location Science and Computational Geometry. We present an overview, particularly showing the state of the art regarding the theory of d-convex sets. We also take into consideration other types of generalized convexity notions in normed linear spaces. Geometric properties of bisectors in Minkowski spaces yield various deep characterizations of special normed linear spaces, or of Minkowski spaces within more general classes of spaces. This viewpoint is also related to Foundations of Geometry. Furthermore, the study of Voronoi d i a g r a m s is based in a natural manner on the geometry of bisectors and their extensions. During the last decade, these topics were mainly investigated in Computational Geometry, in many cases even for linear spaces equipped with a nonsymmetric unit ball. Since this more general approach is still based on the tools typical for Minkowski Geometry, it is also considered in the third part of this survey. Finally we mention here the contents of our planned Part III which is in preparation: smoothness of norms, Chebyshev sets, isometrics (Hyers-Ulam and Beckman-Quarles type theorems, as well as Banach-Mazur distance), isoperimetric problems, and various notions of orthogonality and angle measures. A Part IV is also planned and will contain subjects more related to Discrete Mathematics. We finish this introduction by some notation used in all three sections below. We let M d denote a d-dimensional Minkowski space, i.e., a d-dimensional real normed linear space with norm I1" II and unit ball B := {x e M d : Ilxl[ ~ 1}. As usual we write E g for the d-dimensional Euclidean space. Points and vectors are in boldface. The origin is denoted by o. A convex body K c M d is a compact, convex subset of M d with nonempty interior. For two distinct points x, y E M d we denote the linear segment joining them by [x,y], and the ray emanating from x and passing through y by [~, y). (This notation for a segment differs from the notation in Part I. This is so that it corresponds to the usual notation for d-segments, see the section on generalized convexity notions below). For further general notation and definitions we refer to Part I [196]. 2

Bodies of c o n s t a n t w i d t h in Minkowski spaces

2.1 Introduction If the distance between any pair of parallel supporting hyperplanes of a convex body K in d-dimensional Euclidean space E ~, d >_ 2, is the same, then K is called a body of constant width. Since the time of Euler or even further back it has been known that there are many non-spherical bodies of constant width, the most famous one being the Reuleaux triangle, cf. [232]. Most of the results on bodies of constant width derived up to 1934 are collected in the classical monograph [40]. More recent surveys, showing the pertinent results obtained before 1993, are [60] and [131, Section 5]. Various related concepts (like bodies of constant brightness, etc.) are also discussed in the books [98] and [244]. And there is even a

The Geometry of Minkowski Spaces - A Survey. Part II

95

monograph on bodies of constant width, see [208]. It is natural to extend the notion of bodies of constant width to Minkowski spaces, and in [60] and [131] this more general point of view is also taken into consideration. In addition, we refer to Chapter 4 of Thompson's monograph [283] and [36, Chapter V], where wider discussions of some geometric properties of bodies of constant width in Minkowski spaces are given. However, with many references not cited in [60], [131] and [283], and since the literature on such bodies in Minkowski spaces is sufficiently grown and widespread, one is motivated enough to write an independent summary on this topic. Nevertheless, for practical reasons our sequence of subsections will follow that from [60] and [131].

2.2 Basic Notions We start by introducing Minkowski analogues of various notions from (Euclidean) convex geometry. Note that a unit functional ~ in the dual (Md) * of M d is associated in a natural way with a directed hyperplane of M d. The Minkowski support function of a convex body K is defined by h(K, ~) := sup{~(x) : x E K} for any unit functional E (Md) *. Thus h(K, ~) is the signed distance from the origin o to the supporting hyperplane H = {x : ~(x) = 1} of K. The Minkowski width (or Minkowski breadth) of K in direction ~ is given by w(K, ~) = h(K, ~) + h(K, -~), and K is said to be of constant Minkowski width w(K) C N+ if w(K, ~) = w(K) for any unit functional ~. For later use, we also introduce the central symmetral A K of a convex body K C M d, defined by "t

AK

:-- 2 ( g + ( - g ) ) , where the (Minkowski or) vector addition is defined by/(1 + K2 := {x + y : x E K1, y E /(2}. A segment ~ , q], whose different endpoints p, q are from the boundary bd K of K, is called a diametrical chord (or a~ine diameter) of K if there exist two parallel supporting hyperplanes/-/1 ¢ / / 2 of K such that p E/-/1 and q E/-/2; in this situation we say that ~p, q] is generated by HI, H2. In Euclidean space E d, a chord [p, q] of K is called a normal o / K at p C bd K if K has a supporting hyperplane//1 with p E/-/1 such that ~, q] is orthogonal to//1. If, moreover, there is a supporting hyperplane H2 ~ q which is parallel to HI, then [p, q] is called a double normal of K. To transfer these notions to Minkowski spaces, we first need a suitable notion of orthogonality. Let H be a hyperplane and u ¢ o a vector in M d. The vector u (or a line with u as its direction vector) is said to be normal to H, denoted by u -~ H, if the two supporting hyperplanes of the unit ball B which are parallel to H generate a diametrical chord of B having direction u and passing through o. (Thus, if B is not strictly convex there may be infinitely many directions normal to H.) A chord [p, q] of a convex body K C M d is a Minkowski normal of K at p • bd K if K has a supporting hyperplane/-/1 9 p such that [p, q] is normal to HI. Also, ~, q] is a Minkowski double normal of K if, in addition, there is a supporting hyperplane/-/2 S q parallel to//1. Finally, a point x from the interior int K of K C ]~d is called an equichordal point of K if all chords of K passing through x have the same Minkowski length.

2.3 Geometric properties and characterizations There are various well known properties of bodies of constant width in E ~, d _> 2, characterizing them within the class of all d-dimensional convex bodies. A collection of such

96

H. Martini and K. J. Swanepoel

characterizations is given in [60, Section 2], and the analogous characterizations of bodies of constant Minkowski width can be summarized by T h e o r e m 1. A convex body K C M d is of constant Minkowski width w(K) E R + if and only if one of the following statements holds true. (1) The central symmetral /XK satisfies A K = ~

• B.

(2) For each pair H1, H2 of parallel supporting hyperplanes of K and every direction u normal to H1, H2 there exists a diametrical chord of K having direction u and generated by H1, H2. (3) For each pair H1, H2 of parallel supporting hyperplanes of K, every diametrical chord of K generated by H1, H2 is normal to H1, H2. (4) All diametrical chords of K have length w(K). Proofs of the equivalences of (1) and (2) to constant Minkowski width are presented in [85], and the analogues referring to (3) and (4) are verified in [60, Section 2], see also [88] and [127]. Our next statement (I) is also proved in [85], and (II) is an easy consequence of it. In both (I) and (II) there are now restrictions on the unit ball. T h e o r e m 2. In a Minkowski space following statements hold true.

Md

with smooth and strictly convex unit ball the

(I) A convex body K C M d is of constant Minkowski width if and only if any two parallel Minkowski normals of K coincide. (II) A convex body K C M d is of constant Minkowski width if and only if every chord ~p, q], which is a Minkowski normal of K at p, is also a Minkowski normal of K at q. It should be noticed that without any restrictions on B the above coincidences of Minkowski normals still imply that K is of constant Minkowski width, but the converse may fail to be true. Vredica [298] has shown that a convex body K C M d is of constant Minkowski width if and only if for all x, y E int K there is a set C of constant Minkowski width such that C C_ int K and x, y E bd C. In [189] it is proved that a convex body K in the Euclidean plane is of constant (Euclidean) width w(K) = d i a m K if and only if any two mutually perpendicular chords of K with a common point have total length not smaller than diam K. One might ask for a characterization of those norms where the analogous statement holds, if Euclidean perpendicularity of the chords is replaced by normality. The formulation of the monotonicity lemma in Minkowski spaces involves only Minkowski balls, cf. [196, Section 3.5] or [283, Lemma 4.1.2]. In [132] Heppes proves a characterization theorem which can be treated as a monotonicity lemma for bodies of constant width in E 2. Griinbaum and Kelly [123] extend one of the implications from [132] to strictly convex Minkowski planes, and in [19] the characterization theorem of Heppes is extended to arbitrary Minkowski planes, namely as the two-dimensional part of the following

The Geometry of Minkowski Spaces - A Survey. Part II

97

T h e o r e m 3. Any hyperplane section S of a convex body K C M d of constant Minkowski width splits K into two compact, convex sets such that at least one of them has the same diameter as S. For d -- 2 this property characterizes the bodies of constant Minkowski width within the class of two-dimensional convex bodies. Similar characterization theorems, referring to double normals and the unimodality of chord parametrizations of planar curves, are obtained in [16] and [17]. A further characterization of bodies of constant Minkowski width is given in [134]. Another type of result is the characterization of special representatives within the class of bodies of constant Minkowski width. For example, Petty and Crotty [220] prove T h e o r e m 4. If a convex body K C M d has constant Minkowski width and, in addition, an equichordal point, then K is homothetic to the unit ball B. In a different way, a part of their proof was earlier obtained by Hammer [127], together with further observations on diametrical chords in Minkowski planes. Hammer and Smith [128] prove that if all binormal chords of a curve of constant width in the Euclidean plane divide its circumference into two equal parts, then it is a circular disc. The Minkowski version of this theorem is announced there without proof. Let r denote the inradius of a convex body K C M d, i.e., the largest real number such that K contains some translate ofrB, and R be the circumradius of K, that is the smallest real number such that K is contained in some translate of RB. The boundaries of these translates of rB and R B are said to be inspheres and circumspheres of K, respectively. Chakerian [57] (see also [88]) shows that the following statement holds. T h e o r e m 5. If a convex body K C M d has constant Minkowski width w E •+, then the equality r+R=w holds. Moreover, the corresponding insphere and circumsphere of K are concentric. Conversely, these properties do not imply constant width in M d, but a generalization of Theorem 5 is given in [240]; cf. Section 2.6 below. Some geometric properties of planar bodies of constant width in the Minkowski plane (1~)*, whose unit ball is the isoperimetrix I (i.e., the convex figure of minimal perimeter for given area) of the original plane 1 ~ , are discussed in [150] and [55]. For example, if C is a figure of constant width w E ]R+ relative to (1~)*, then A(C) + A(C, - C ) = ~. A(I), where A(C) is the area of C and A(C, - C ) denotes the mixed area (cf. [244, § 5.1]) of C and - C . They also give further relationships between M 2 and (1~)*, e.g.: 1. if C has constant width w relative to (1~)* and P(C) is the perimeter of C relative to M ~, then P(C) = w . A(I), 2. if C is a smooth convex curve of constant width relative to (Mu) * such that each of its diametrical chords bisects the Minkowski circumference (or the Minkowski area), then C is homothetic to I.

98

H. Martini and K. J. Swanepoel

2.4 Special bodies of constant width The simplest figure of constant width w E R + in E 2 apart from a circle is the Reuleaux triangle whose first mechanical usage is ascribed by Reuleaux to Hornblower, the inventor of the compound steam-engine, see [232, § 155]. It is bounded by three circular arcs of radius w which are centred at the vertices of an equilateral triangle (with side-length w). There are different ways to define its analogue for Minkowski planes. Replacing the notions "circular" and "equilateral" by their Minkowski analogues, Ohmann [211], Chakerian [56] and Wernicke [300] describe Minkowski Reuleaux triangles as extremal figures with respect to certain metrical problems, see also Section 2.8 below. In addition, the planes with parallelograms or centrally symmetric hexagons as unit circles are the only ones where Reuleaux triangles exist as Minkowski circles, cf. [300]. The paper [231] of Reimann is also geometrically related to Reuleaux triangles in Minkowski planes. Sallee [237] extends these considerations by constructing certain Minkowski Reuleaux polygons. Another type of Reuleaux polygon in M 2 has been described by Hammer [127]. Its Euclidean variant yields figures of constant width bounded by finitely many circular arcs of possibly different radii (see Rademacher and Toeplitz [228, p. 167] for the Euclidean

case). Petty [216] uses the Minkowski analogue of the notion "evolute" to construct special curves of constant width in Minkowski planes.

2.5 Completeness in Minkowski spaces A bounded subset C of M d is called complete (or diametrically complete or diametrically maximal) if it cannot be enlarged without increasing its diameter diam C := sup~,uec IIx YlI. In other words, C is complete if it is the intersection of all translates ~ + ~B with x E C and A > diam C. Any complete set C having the same diameter diam C = diam K as a convex body K C M d with K C C is said to be a completion of K. Various results on complete sets in Minkowski spaces are compiled in [36, Chapter V] and [112]. In Euclidean space, the following two statements hold true. • A convex body K C E d is complete if and only if it is of constant width. • Every convex body K C E g has at least one completion. The first statement is the classical theorem of Meissner, see [204] and [40, §§ 64], and the second one is known as P~l's theorem, cf. [213] and [40, §§ 64]. It is easy to see that constant width implies completeness also in Minkowski spaces, see, e.g., [88, § 2] for an explicit proof. For d = 2, 3 and smooth unit balls Meissner [204] investigated the converse, followed by Kelly [149] without restrictions regarding the dimension and smoothness. However, the proofs in [204] and [149] with respect to this converse implication are erroneous for d :> 3: there are complete sets that are not of constant width, even if the unit ball is smooth and strictly convex. Such an example was constructed by Eggleston [85], who also gives an example with a polyhedral unit ball. Thus, the extension of Meissner's classical theorem to Minkowski spaces is true only for d = 2. However, in higher dimensions the completeness of K C M d implies constant width if K is smooth and strictly convex, cfi [88, Theorem (3.18)]. However, there is a related equivalence theorem holding for all Minkowski spaces. A convex body K C M d is said to have the spherical

The Geometry of Minkowski Spaces - A Survey. Part II

99

intersection property if K is the intersection of all balls with centre x E K and radius diam K, cf. also Section 2.6. Using this notion Eggleston [85] also proves T h e o r e m 6. A compact set X C M ~ is complete if and only if it has the spherical intersection property, or if and only if each boundary point of X has distance d i a m X from at least one other point of X . An alternative proof of the first statement in this theorem can be found in [88, § 3]. Eggleston [85] compares Minkowski spaces in which the classes of complete sets, sets of constant width and spheres coincide (cf. also [88, § 3]). In [84] he erroneously states that the only Minkowski spaces in which sets of constant width are necessarily balls are those whose unit ball B is a parallelotope. In order to obtain the right answer to this question, one has to look at the classification of all irreducible sets, i.e., of all convex bodies K centred at the origin for which the identity K = Q + ( - Q ) is only possible if Q is centrally symmetric, see Griinbaum [121] and Shephard [249] for first investigations in this direction. A thorough study of irreducible polytopes (i.e., polyhedral unit balls for which sets of constant Minkowski width are necessarily balls) is given by Yost [304], see also [244, § 3.3]. For example, each convex d-polytope, d >_ 3, centred at the origin and having less than 4d vertices is irreducible. Investigating four-dimensional polyhedral unit balls in view of irreducibility, Pay£ and Yost [215] obtain examples of Minkowski spaces that are interesting regarding the n-ball property and semi-M-ideals (notions from Banach space theory). Eggleston [85] also shows that if the unit ball B is a d-dimensional parallelotope, then every complete set is homothetic to the unit ball. The converse is proved by V. Soltan [261], i.e., we have T h e o r e m 7. If every complete set in M ~ is homothetic to the unit ball B, then B has to be a parallelotope. The two-dimensional case is contained in Theorem 8.1 of [127]. The infinite dimensional case has been looked at by Dalla and Tamvakis [67] and Franchetti [90]; they also investigate completeness in relation to constant width. Eggleston [85] also shows the following T h e o r e m 8. Any bounded set S C M d can be embedded in a complete set of the same diameter. Uniqueness of completion in Minkowski planes plays an essential role with respect to Borsuk's partition conjecture in such planes, see [36, § 33] and Section 2.10 below. Groemer [112] investigates the uniqueness of completion in d-dimensional Euclidean and Minkowski spaces, e.g. in view of maximal tight covers of a bounded set S C M d (which are convex bodies K of maximal volume satisfying S C K and having the same diameter as S). He shows that every maximal tight cover of a bounded set S C M d is a completion of S and that any two such completions are translation equivalent; for strictly convex norms there is precisely one completion of this type. Furthermore, symmetry properties of such "maximal completions" are studied, and cardinalities of the set of completions for a given set (without the maximality assumption) are discussed. Various results from [112] are new even for the Euclidean case. We also refer to [21], where some of Groemer's

100

H. Martini and K. J. Swanepoel

theorems are summarized and used to get further results. Vre6ica [298] observes that each bounded subset of M ~ has a completion within any circumball (i.e., a smallest Minkowski ball containing this set); a sharpening is obtained in [88]. Sallee [242] describes methods for constructing complete sets in M d containing an arbitrarily given set X. He pays special attention to the problem of preassigning boundary parts of such sets and, following ideas from [239], also to questions of preserving symmetries (if this is desired). Some of Sallee's results are reproved in [21], and it is shown there that these constructions carry over to infinite dimensions, as the result of Vredica [298] does. On the other hand, it is shown in [21] that, while in finite dimensions there is a completion C satisfying C f3 B = S N B, the analogue fails in infinite dimensions (here B denotes a circumsphere of the bounded set S C Md).

2.6 Intersection properties Due to Eggleston [85] a convex body K C M d has the spherical intersection property if K is the intersection of all balls with centre x E K and radius diam K (see also Theorem 6 above). In Euclidean space, the property of constant width and the spherical intersection property are equivalent, cf. [85] and [60, p. 62]. In Minkowski spaces this is no longer true, but the spherical intersection property is still equivalent to the notion of completeness, see Theorem 6 above and [85]. For a body of constant width K C M d let t(K) denote the smallest number of balls whose intersection equals K. V. Soltan [263] proves some results on the possible values of t(K). For example, he derives necessary and sufficient conditions for t(K) < c¢. For d = 2, he determines unit balls that admit given even values for t(K). Groemer [112] uses the spherical intersection property to study bounded sets with unique completion in M a. Sallee [240] generalizes Theorem 5 above. He shows that it still holds if one replaces "constant width w E ~+" by "the spherical intersection property". Section 2 of [21] contains also some properties of sets which can be presented as intersections of balls. Analogously, Bavand [22] introduces the s-adjoint transform in E 2, which associates to a two-dimensional convex body K its s-adjoint K*(s) as the intersection of all discs of radius s whose centres are from K. Explaining the connection of this transform to hyperconvexity (cf. our section on d-convexity as well as [25, 52, 198]) and to the concept of constant width, he gives a new construction of the completion of a compact set in the plane. He also presents applications related to stochastic point processes and statistical mechanics. One might ask for extensions of these Euclidean results to Minkowski planes. Baronti and Papini [21] establish various properties connecting completeness and the spherical intersection property for infinite dimensions. Kupitz and Martini [163] consider a related notion: a set S C E 2 of diameter 1, say, has the weak circular intersection property if the intersection of all unit discs whose centres are from S is a set of constant width 1. They determine the least number of points to be added to a finite planar set of given diameter such that the resulting set has the weak circular intersection property. Nothing seems to be known about this notion in higher dimensions or Minkowski spaces. The dissertation [186] contains Helly-type theorems for sets of constant Minkowski width.

The Geometry of Minkowski Spaces - A Survey. Part II

101

2. 7 Curvature and mixed volumes Let K C Ed be a body of constant width w(K) E R + whose boundary bd K is twice continuously differentiable, and let R1 ( u ) , . . . , Rd-1 (u) denote the principal radii of curd-1 vature at the point x E b d K with outward unit normal u. If Fl(u) := ~"~i=1 R/(u), then FI(u) + Fl(-u) = (d - 1). w(K) (1) for each u • S d-l, see [40, p. 128]. This can be extended to all bodies of constant width by introducing the surface area function S(K,w), w • B, where B denotes the field of Borel subsets of S d-1. The "mixed surface area function" S(K1,..., Kn-1;w) of convex bodies K1,... ,K~-I • E d is a completely additive set function defined for w • B. Thus for any convex body K0 C Ed the mixed volume (cf. [244, § 5.1]) is given by

V(Ko, Kz,..., K~-z) = -nl /

h(Ko, u)S(KI,..., Kn-1; du).

(2)

8d-1

Here the presented integral is the Radon-Stieltjes integral of h(K0, u) with respect to the function S(K1,..., K~-l;W). Then s(g,w) :=- S(K,..., K,w) is called the surface area function (or first curvature measure of second kind), cf. [244, § 4.2]. Since, if K is of constant width, K + ( - K ) is a homothet of the Euclidean ball, the linearity and homogenity of S(K, w) as a function of K imply

S(K, w) + S(K, -w) = w(K) . #(w),

(3)

where #(w) is the spherical Lebesgue measure of the Borel set w C S ~-1. By a known integral representation of S(K, w) in terms of F1 (see [244, § 4.2]), (3) is equivalent to (2) if K has a sufficiently smooth boundary, and basically due to the Aleksandrov-FenchelJessen uniqueness theorem (cf. [244, § 7.2]) it can be concluded that (3) is a characteristic property of all bodies of constant width in Eu. It turns out that, in terms of relative differential geometry (see also [40, § 38] and [60, § 6]), these relations can be extended to Minkowski spaces. Namely, for a smooth convex body K C Ed let L(bd K, x) denote the canonical linear mapping of its tangent space bd K~ at x E bd K into the tangent space of S d-1 at u E S d-l, where a: and u are connected by the usual Gauss mapping via parallel normals, with u as unit outward normal of bd K at x. If for a smooth unit ball B in M d, Be denotes the tangent space of bd B at e having the same unit normal as b d K at x, then the linear mapping J : bdK~ --+ Be can be defined by J = L(bd K, x). L-l(bd B, e) and is, as the canonical linear mapping of bd K into bd B via parallel normals, invertible with J ' ! = L(bd B, e). L-l(bd K, z). Thus we may write J = J(u), where u is the outward unit normal of b d K at ~, and of bd B at e. The relative principal radii of curvature -Rz,...,-Rd-1 of bd K at ~ are the reciprocals of the eigenvalues of J(u), and the corresponding relative principal directions are the eigenvectors of J(u). Following [40, p. 64], we write (R1,..-,R~} for the uth elementary symmetric function of the relative principal radii of curvature R1,...,Rd-1, and we let Fv(K, u) = (R1,... ,Rv} at u as above, With this notation, Chakerian [57] proves

102

H. Martini and K. J. Swanepoel

T h e o r e m 9. Let K be a smooth convex body of constant Minkowski width w(K) c ]~+ in

M d. Then -Ri(u) +-Rd-~(-u) = w(K),

u c S d-l,

i= l,...,d-1,

and, in particular, FI(K, u) + F I ( K , - u ) = (d - 1). w(K), u e S d-1. We set S(K,..., K, B , , . . , B; w) =: S(K, r; B; w) by using the notation given in connection with (2). Here the convex body K appears r times and B appears n - r - 1 times. Chakerian [57] also proves T h e o r e m 10. I l K is a body of constant Minkowski width in M d, then

S(K, 1; B; w) + S(K, 1; B; - w ) = 2. S(B, w)

(4)

with w E B. Conversely, if the unit ball B is smooth, (4) implies that K is of constant Minkowski width. Here the smoothness assumption in the second implication cannot be omitted, as an easy construction (with B the convex hull of a Euclidean ball centred at the origin and two points x, - x outside this ball) shows. Hug [139, § 1.4] obtains a further result on surface area measures of bodies of constant Minkowski width, and he also gives an extension of this which is closely related to pairs of constant Minkowski width (for the latter notion see our Section 2.12 below). In [139] one can find also various related characterizations of unit balls. If a convex body K C E 2 has sufficiently smooth boundary, one may denote its radius of curvature at x E bd K with outward normal u = (cos a, sina) by R(a). In this notation we can give a necessary criterion on a function R(a) to present the radius of curvature of a body K C E ~ of constant width w(K) E R+: R(~) + n ( ~ + ~) = w(K).

(5)

In Minkowski planes we have the same result. The sum of the radii of curvature at analogously opposite boundary points of a plane body of constant Minkowski width is constant and equals w(K). In terms of difference bodies (which are homothets of central symmetrals) this was first observed by Vincensini [295, p. 24], and Sz.-Nagy [281, p. 31], and Petty reproved this, see [216, Theorem (6.14)]. Chakerian [59] shows that for a figure K of constant width in M 2 the integral

I(K) = ~

R2dS,

where R is the relative radius of curvature and dS denotes the relative arc length element, can also be expressed by the functional

I(K) = / / n ( x l ,

x2)dxldx2,

where n(xl, x2) denotes the number of diameters of K passing through x = (xl, x2) E K. Let C be a twice continuously differentiable curve in E 2. The Four Vertex Theorem says that C has at least four vertices which are the points of C where the curvature of

The Geometry of Minkowski Spaces - A Survey. Part II

103

this curve has a stationary value. Heil [129] derives a generalized version of the analogous theorem for Minkowski planes. His considerations imply that any curve of constant Minkowski width has at least six vertices. Defining the k-th quermassintegral of a convex body K C E d in terms of mixed volumes by Wk(K) := V ( K , . . . , K, B , . . . , B) (here K appears n - k times, and B appears k times, see [40, p. 49]), the equality k

It.\

i=0

holds if K is a body of constant width w ( g ) e R +, cf. [77]. Chakerian [58] generalizes (6) as follows: For convex bodies K, L, M with K + L = M let V(K, k; *) denote the mixed volume with K occuring k times and • representing n - k fixed entries, and V(L, i; M, k i; *) be the mixed volume of i times L and k - i times M with the same n - k fixed entries as above. Then k

i=0

Assuming L = - K , M = we(K) • B and setting the remaining entries equal to the unit ball B of M e, an analogue of (6) for bodies of constant Minkowski width is obtained, see

also [601. Guggenheimer [124, p. 327] announces related results on bodies of constant width relative to a unit ball which is no longer centrally symmetric, i.e., only a gauge body.

2.8 Inequalities The BIaschke-Lebesgue Theorem states that among all figures of constant width w E R + in E 2 only the Reuleaux triangle has minimum area (see [60, § 7] and, for a short proof, e.g. [56]). The analogous theorem for Minkowski planes was obtained by D. Ohmann and, independently, by K. Giinther in their dissertations (both in Marburg, 1948); Ohmann published his approach in [211], see also Petty [216, pp. 15-16]. Since Reuleaux triangles of fixed width in Minkowski planes can have different areas in general, we describe the construction of the particular type which this theorem refers to. Let the Minkowski unit vectors rl, r~, ra E 1~ have the property rl + r2 + ra -- o. Then, by suitable translates of the segments [o, ri], one can form a triangle ala2aa with al = o and a2, a3 E bd B, cf. Figure 1. Connecting now the vertices al and a2 as well as a2 and aa by corresponding boundary arcs of B (see again the figure), we get a figure of constant Minkowski width 1 whose boundary contains the points al, a2 and a3. Due to Ohmann any homothetical copy of such a figure is called a general Reuleaux triangle in M 2. With this notation we can formulate T h e o r e m 11. Among all figures of constant width w C ]~+ in a Minkowski plane, a general Reuleaux triangle has minimum area. Chakerian [56] presents another proof of this theorem, and also Kubota and Hemmi [161] give an independent approach by investigating various inequalities for convex figures in E 2. From this they deduce that precisely the above mentioned analogues of Reuleaux triangles are extremal with respect to an inequality in terms of diameter and minimal

104

H. Martini and K. J. Swanepoel

a2

F i g u r e 1. Constructing a Reuleaux triangle

width. Deriving a differential equation for the relative support function of a convex set, Ghandehari [103] gives an optimal control formulation of the Blaschke-Lebesgue theorem in Minkowski planes. The Firey-Sallee Theorem says that among all Euclidean Reuleaux polygons having n > 3 vertices and width w E R + the regular one has maximal area. In [238] Sallee announces without proof that his methods for getting this result in E 2 can be modified to obtain analogous results in Minkowski planes. Lenz [183] proves that in a Minkowski plane whose unit circle B is a Radon curve the ball has largest area among all bodies of fixed constant width. However, by the RogersShephard inequality [236] in any Minkowski space the ball has the largest volume among all bodies of fixed constant width. Wernicke [300] shows that the area of a Reuleaux triangle A of width 1 in a Minkowski plane satisfies ~1 <_ ~Area(B) <-- k' where equality holds iffthe unit ball B is an affine regular hexagon (left hand side) or a parallelogram (right hand side). Furthermore, he proves that only in planes with B a parallelogram or a centrally symmetric hexagon there exist Reuleaux triangles that are Minkowski circles. Castro Feitosa [88] uses extremal properties of bodies of constant width in ~ to extend various inequalities of Scott [246] for convex figures in E ~ to convex figures in Minkowski planes. E.g., he uses the facts that among all convex figures in M~ with given diameter and circumradius the sets with largest thickness (= minimal width), perimeter, inradius or area are of constant width. Further inequalities for the area of figures of constant Minkowski width and related results are derived in [54] and [151]. In [151] an upper bound on the area of a figure C C ~ of constant width in terms of the Minkowski arc length of its pedal curve and other quantities is given; this bound is attained iff C is homothetic to a pedal curve of the isoperimetrix of M 2. Investigating products of dual cross section measures of convex bodies and their polar reciprocals, Ghandehari [104] proves that the d-dimensional volume of the polar reciprocal K* of a body K C M d of constant width 2 satisfies V(K*) > V(B*), in which B* is the polar reciprocal of the unit ball B. Here equality holds if and only if K = B. Another type of inequality is considered in [190]. For X a finite point set in E d with ddimensional convex hull P, the points x~, xj E X are called antipodal if there are different

The Geometry of Minkowski Spaces - A Survey. Part II

105

parallel supporting hyperplanes H', H " of the polytope P with xi 6 H ' , xj E H". If E ~ is endowed with a Minkowski metric, one might ask for the number of pairs in X whose Minkowski distance is maximal. This number is not larger than the number a(X) of antipodal pairs in X, and if P is of constant Minkowski width, then equality holds. In [190] several upper bounds on a(X) are given.

2.9 Inscribed and circumscribed bodies As is well known, a hexagon (regular in the considered norm) can be inscribed in any Minkowski circle. We refer to [283, Chapter 4] for a broad and nice representation of related results and how this can be applied to construct curves of constant Minkowski width, in particular Reuleaux triangles. As a special case of a result of Doliwka [79] (conjectured by Lassak [172]) we have that any planar body of constant Minkowski width 1, say, has an inscribed pentagon whose vertices are in at least unit distance to each other. A generalization to arbitrary equilateral inscribed polygons is announced by Lassak (personal communication).

2.10 packings, coverings, lattice points Loomis [186] considers so-called three-coverings within the family of bodies of constant width w in Minkowski spaces. A set K three-covers the set L if L C {al, a2, a3} + K for some three points al, a2, an. Among other results, Loomis shows that a Reuleaux triangle of width w three-covers any figure of constant width w. Further on, if B is a centrally symmetric octagon, then each figure of constant width three-covers every other set of the same constant width. Inspired by a question of P. C. Hammer, Sallee [237] considers bodies of constant width in association with lattices. In analogy to the Euclidean situation, he defines a Minkowski Reuleaux polygon to be a set of constant width w in M 2 which is the intersection of a finite number of (properly chosen) translates of wB. Saying that a set S avoids another set X if int S A X = 0, he proves the following statements for any Minkowski plane with strictly convex unit ball B: Every set of maximal constant width avoiding a square unit lattice L is a Minkowski Reuleaux triangle P where each of the three open "edges" of P contains at least one point of L. If the lattice L is replaced by a locally finite family X of convex sets in an arbitrary Minkowski plane, then the corresponding maximal sets are Reuleaux polygons in M 2 all of whose open "edges" contain points from X. Surveys on the famous partition problem of Borsuk are presented by Griinbaum [122], [36, Chapter V] and Raigorodskii [229], see also [1, Chapter 15]. This problem is closely related to bodies of constant width, cf. [60], [131], [33] and also [36, Chapter VIII]. A first investigation of Borsuk's problem in Minkowski planes is due to Griinbaum [120]. He shows that if B is not a parallelogram, then any set of diameter 1 can be covered by three balls each of diameter less than 1. Let F C M ~ be a bounded set of diameter h. What is the smallest integer k such that F is the union of k sets each of which has a diameter strictly smaller than h? Denoting this smallest number by aB(F), Boltyanski and V. Soltan [39] prove that for d -- 2 one has aB(F) 6 {2, 3, 4}, where aB(F) ----4 occurs if and only if B is a parallelogram and the convex hull of F is a homothet of B. And aB(F) > 2 holds if and only if one of the following two conditions is satisfied: (i) There is a unique completion of F to a figure C of constant width h. (ii) For any two parallel supporting hyperplanes of C at least one has nonempty intersection with F.

106

H. Martini and K. J. Swanepoel

2.11 Rotors in polytopes It is obvious that bodies of constant width in E d are rotors in cubes and in some other polytopes. On the other hand, there are also polytopes with rotors not of constant width (but still having various similar properties). With this (a little extended) point of view, a remarkable list of related references can be taken from [40, pp. 139-140], [60, p. 80] and [131, p. 367]. Regarding Minkowski geometry, Ghandehari and O'Neill [105] derive inequalities for the self-circumference U of rotors in equilateral triangles and figures of constant width. Here U is measured by taking these rotors or figures of constant width themselves as gauge figures or unit circles of a Minkowski plane. The inequalities compare their areas and mixed areas (taking also the polar reciprocal) with U. Some higher dimensional results are also given in [105]. Weakly related, Sorokin [275] studies certain classes of convex bodies which can roll in Minkowski spheres.

2.12 Concepts related to constant Minkowski width and ]urther results Heil's concept of reducedness (cf. [130]) is in a sense dual to completeness. A convex body K C E d which does not properly contain a convex body of the same minimal width is called a reduced body. For a discussion of results on reduced bodies see [131, §§ 5.4]. The most striking open questions on reduced bodies in E d are: (a) Do there exist reduced polytopes for d _> 3? (b) Is a strictly convex reduced body in E d, d > 3, necessarily of constant width? Recently Lassak and Martini [173] extended this notion to Minkowski spaces. It is easy to see that for certain norms (with the Manhattan norm as most simple case) and d _> 3 reduced polytopes exist, whereas in [173] the extension of (b) is again only verified for d = 2. Furthermore, it is shown that there exist reduced bodies in Minkowski spaces of dimensions d :> 3 having minimal width 1, say, but arbitrarily large diameter. Let 5(K, u) denote the (d - 1)-dimensional volume of the orthogonal projection of a convex body K C E d onto the subspace orthogonal to u E S d-1. Usually ~(K, u) is called the brightness of K at u, cf. Chapters 3, 4, 8, and 9 of [98] for related results. A convex body K C M d is said to be of constant brightness with respect to B if 5(K, u) is proportional to 5(B, u). Chakerian [57] shows that if both B and K in M 3 have C 2 boundary with everywhere positive curvature, then K is a homothet of B. More generally, Petty defines the Minkowski brightness of K c M d at u E S d-1 as the minimal Minkowski cross section area of the cylinder K + L, where L is the 1-subspace of direction u. In [217] and [218] he derives results on bodies of constant Minkowski brightness. The k-girth of a convex body K E E d in direction u is given by the mixed volume d V ( K , . . . , K, B , . . . , B, [u]), where K appears k times, the Euclidean ball B occurs n k - 1 times, and [u] denotes the unit line segment parallel to u, see also Section 2.7 above. Chakerian [57] considers sets of constant k-girth in Minkowski spaces, and Petty [218] studies bodies of constant Minkowski curvature. Due to Maehara [188], two convex bodies/(1, K2 C ]E~ are said to be a pair of constant width if K 1 + (-/(2) is a ball. Analogously, Sallee [241] defines a pair K1,/£2 of convex

The Geometry of Minkowski Spaces - A Survey. Part II

107

bodies to be a pair of constant width in M d if h(K1, u) + h(K2, - u ) = A . h(B, u) for some A > 0 and all directions u E S d-1. Among other results, he proves that K1 is a summand of the unit ball B iff there is a / ( 2 such that {K1,/(2} is a pair of constant width in M d. Also Sallee's generalization of Theorem 5 with respect to sets having the spherical intersection property in M d (cf. Section 2.6 above) can be formulated in terms of pairs of constant width in M d, cf. [240]. Petty and Crotty [220] show that there are d-dimensional Minkowski spaces with convex bodies having exactly two equichordal points. Rodriguez Palacios [235] points out that results on summands of Banach spaces may be interpreted in terms of sets having constant width in Banach spaces. In view of multiplication with scalars, Minkowski addition and suitable combinations thereof, the family of all convex bodies in E d forms an abelian semigroup with scalar operators. Having such an algebraic structure and the Hausdorff metric in mind, Ewald and Shephard [87] introduce an equivalence class structure for the subclass of bodies of constant width, which yields an incomplete normed linear space. They remark that (due to a hint of Griinbaum) their respective results may be easily extended to bodies of constant Minkowski width. Such extensions were given by Sorokin [275], even for nonsymmetric unit balls which, on the other hand, have to be smooth and strictly convex. Taking the minimum width of certain representatives as a metric (in the above mentioned space), Lewis [185] shows that then a conjugate Banach space with complete norm is obtained. For related considerations we also refer to [86]. Finally we shortly mention the concept of bodies of constant affine width in the sense of affine differential geometry, see Siiss [280] for an early contribution. For further references to this subject we refer to the final paragraphs of the surveys [60] and [131] and, in particular, to the investigations in [135] and [24], relating the concept of affine width to that of Minkowski width.

3

Generalized convexity notions in Minkowski geometry

3.1 Introduction In Section 3 we deal with modifications of the usual convexity notion, in most cases yielding natural extensions of basic theorems on convex sets. The main part will refer to a type of metric convexity which is usually called d-convexity, but also other kinds of convexity will be discussed. The letter 'd' is used in two different meanings: for the dimension of the space, and for the historically fixed notions of d-segment and d-convexity. Since the distinction will always be clear from the context, we let it as it is. The notion of d-segment is based on so-called metric betweenness points and the metric betweenness relation which were first considered by Menger [206, Part I] and Blumenthal [27, Chapter II] in the context of complete, convex metric spaces. See also [207], [28, Chapter II], [114], [234], [5], [253], [29, Part 3], and [256]. Also based on betweenness points, Meager and Busemann proposed to complete Fr~chet's axioms for a metric space to ensure the existence of geodesics, cf. [45, Chapters I and II], [47, Chapter I], and its continuations [48] and [51]. Replacing usual straight line segments in the common definition of convex sets by d-segments, the concept of d-convex sets is obtained, see [216], [114], [5], [53], [253], and [256] for the definition and first investigations. (We note that

108

H. Martini and K. J. Swanepoel

Petty [216] speaks about the concept of "Minkowski convexity".) Wider presentations of this concept can be found in the monographs [37], [270] and [36] (see the chapters with the headline "d-convexity"), and it is also mentioned in the Handbook of Convex Geometry, cf. [193, § 4]. For further generalized convexity notions we refer to [70, § 9], [293] and [250].

3.2 d-segments in Minkowski spaces Let 9' be a simple curve in a d-dimensional Minkowski space M d which is parametrized by [to, tn] and whose length is defined, in an elementary way, by

[9'1 := sup{y ' rla,-1 - a, ll:

e N, ai = 9'(t ),to < tl < . . . < t , } ,

i=1

with the endpoints a0 = 9'(t0), an = 9'(t,~). A metric segment is a curve isometric to a closed segment of the real line, a metric line is a curve isometric to the real line, and a geodesic (cf. [45, § 3] and [47, p. 32]) is a curve that is locally a metric segment, i.e., each point of the curve has a closed neighbourhood which is a metric segment. For a metric d(x, y) (= [Ix - Yll in a Minkowski space), the set [a, b]a := {z E Md: d(a, b) = d(a, z) + d(z, b)} is called the d-segment with endpoints a, b E M d. It is easy to show that any metric segment with endpoints a, b is contained in In, bid and, on the other hand, that [a, bid is the union of all metric segments with endpoints a, b. Each point z E M d satisfying a # z # b and d(a, b) = d(a, z) + d(z, b) is said to be a betweenness point of the distinct points a and b. See Meager [206, p. 77], who introduced betweenness points for arbitrary metric spaces and studied basic properties of the related betweenness relation (cf. also [27, Chapter II], and [28, Chapter II]). It is clear that the betweenness relation is closely related to the triangle inequality and therefore, in Minkowski spaces, to the (strict) convexity of the unit ball [109], el. our first survey [196, § 3]. In particular, any metric segment is a straight line segment iff the unit ball B of the Minkowski space is strictly convex, see [96], [73, p. 144], [42], [43], [257], and [76], also for further equivalent properties. We recall that strict convexity is equivalent to many notions such as the monotone property of the distance function and Chebyshev sets; see [196, § 3] as well as the further references [9] and [92]. Extensions of this characteristic property to more general spaces and related observations are given in [252], [209], [42], [230], [94], [75], [95], [303], and [292]. See also [9] and [29, Chapters 6 and 7]. For detailed discussion of the following observations we refer to [196, § 4]. Got~b and H/irlen [109] and, independently, Toranzos [290] have shown that the extreme points of the unit ball B of a Minkowski space coincide with the directions of unique metric segments, i.e., of curves 9' from a to b such that 171 = Ila-bll . Nitka and Wiatrowska [210] observe that the origin o is a betweenness point of p, q c bd B iffthe straight line segment [p, ~o(q)] c bd B, where ~o(q) denotes the reflection of q at o. From this it follows that, given three arbitrary non-collinear points a, b, c E M d, one can always find a norm such that b is betweenness point of a and c. To see this, it suffices to choose a Minkowski ball centred at b whose boundary contains [a, ~b(c)]. Verheul [294] says that a metric space Z is modular if [a, bid N [b, C]d n [c, a]d is nonempty for any triple a, b, c C X, and X is called median if this intersection is always exactly one point. He shows that a Minkowski space is median iff it is isometric to gld,

The Geometry of Minkowski Spaces - A Survey. Part II

109

the d-dimensional Minkowski space with norm tlx[] = ~i~1 [xi[, i.e., iff the unit ball is a cross-polytope. Verheul uses lattice-theoretic techniques to study modular metrics and modular Banach spaces. Finally we want to give a geometric description of d-segments in terms of the boundary structure of the unit ball, see [257] and [36, § 9]: For x, y e M d, denote by B~, By the Minkowski balls of radius []x - Yll with centres x and y, respectively. Furthermore, we write F® for the face of B~ in bd Bx that contains y and, analogously, Fy for the face of By in bd By containing x, see Fig. 2. We denote by C~ the cone with apex x consisting of all points x + A(a + x), where a e F~, A >_ 0, and by Cy the cone with apex y and the representation y + ;~(b - y), b E Fy and A >_ 0. Then the d-segment with endpoints x, y is the intersection of the cones Cz and Cy (which are symmetric with respect to the midpoint of the straight line segment [x, y]), i.e., we have [x, Y]d = C~ A Cy. Soltan [270, Theorem 11.22] extends this observation to the infinite dimensional case.

s / t

B~

x

.'"

Y

i • i"

Figure 2. Construction of a d-segment

3.3 Fundamentals of d-convexity As Menger emphasizes in [206, Part I], the usual definition of convexity, using straight line segments, cannot be used for general metric spaces, and he defines a metric space X to be metrically convex if for any two distinct points a:, y E X there exists a betweenness point z, i.e., d(x, z) + d(z, y) = d(x, y) has to be satisfied. With this concept, sometimes also called "Menger convexity" or M-convexity (see, e.g., Busemann [47, § 6]), convex metric spaces were studied, cf. the basic reference [28, § 14] (or Section 3.8 below). A slight modification yields the notion of d-convexity which is more interesting for Minkowski spaces and seems to have been first defined by Petty [216] and, independently, by de Groot [114]. Using the term "d-segment", one can formulate this definition (referring to a Minkowski space M d) as follows. A set A C M d is d-convex if for any points a, b E A the d-segment In, bid is contained in A. Equivalently, A c M d is d-convex provided for any three points a, b C A, x E M d,

110

H. Martini and K. J. Swanepoel

the equality IIa - bl] = IIa - xll + II~ - bll implies that :~ E A. Since [a, b] c [a, bld for any a, b E M e, each d-convex set is also convex in the usual sense (i.e., linearly convex). Obviously the converse is not necessarily true. A broad presentation of the theory of d-convex sets in Minkowski spaces and linear normed spaces of any dimension is given in [270, Chapter II], see also Chapter II, § 24 and the first six research problems in Chapter VIII of [36]. Forerunners of these presentations are [38] and [37]. In the following, we will be concerned with the most important results in this direction, and we will try to give a historically correct representation how these results came to be.

3.4 d-convex sets in metric (and Minkowski) spaces This section refers to results about d-convex sets which even hold in metric spaces, but are also important for Minkowski geometry. Since it is easy to prove that the intersection of an arbitrary family of d-convex sets is itself d-convex, the following notion makes sense. The smallest d-convex set containing a set A C M d (i.e., the intersection of all d-convex sets containing A) is called the d-convex hull of A and denoted by convd A. (Note that cony A is used for the usual convex hull.) A well known procedure to obtain cony A from A is that of segment joining: Considering the union of all straight line segments [a, b] with a, b E A, a finite iteration of segment joining yields cony A (by Carath~odory's theorem). The following theorem, which is due to [289] and [102], refers to the analogous procedure with d-segments. For this we introduce the following notation. For an arbitrary set A C M d we write Po(A) = A, and then define Pi(A) = U{[x,y]d: x , y E P~-I(A)} for each i _ 1. T h e o r e m 12. For an arbitrary set A C M d, the set 0 Pi(A) is the d-convex hull of A. i=1

Using the inequality diam P1 (A) _< 2. diam A for the diameter of PI(A), the authors of [174] show the following: Let a(A) := diam(conve(A)) diamA , and let fl(A) denote the smallest number k for which convaA = U Pk(A) (if such a k does not exist, then fl(A) = ee). k>0

Then a(A) <_2~(A). A metric space X (in particular, a Minkowski space) is called an a-space (~-space) if a(A) < oe (fl(A) < oo) for any bounded set A C X, and it is called an a*-space (~*-space) if a*(X) = sup a(A) (fl*(X) = sup fl(A)) is finite, where the supremum is taken over all bounded subsets A of X. This notation is from [174], where examples are given as well. Spaces where a(A) = oo or f~(A) = oo are also considered there. See also

[270, pp. i07-Iii], [36, § 9 and § 11], and below. From a(A) < 2/3(A) we have that these four classes of spaces satisfy the following diagram of inclusions: (class of ~*-spaces) M (class of a*-spaces)

C C

(class of fl-spaees) M (class of a-spaces)

The following results are derived in [270, § 14]: For any set A C NI2 convd A = cony A U P1 (A) = P1 (cony A) = cony P1 (A) = P2 (A)

The Geometry of Minkowski Spaces - A Survey. Part II

111

and for bounded A C M ~ diam(conv~A) __ 2. diamA

and

convd(clA) = cl(convdA).

Besides various further observations on (special) metric spaces, in [101] and [258] the following results are obtained: • For any bounded set A C M d and the unit ball B o f M d the inequality a(A) <_a(B) holds, yielding also a*(M d) = a(B) and the property that for any a' with 1 _< a ' < a(B) a set Q c M d exists such that a(Q) = a'. • We have 1 < a * ( l ~ ) < 2 with equality on the left-hand side iff B is d-convex, and on the right-hand side iff B is a parallelogram. • We have ~*(M~) E {1, 2} with/~*(N~) = 1 iff B is a parallelogram. The following definition is taken from [267]. A point z C A is said to be d-extreme with respect to a set A in a metric space if z ~ [~, y]~ for any ~, y C A \ {z}. We denote by extd A the family of all d-extreme points of a set A. It follows that for a dconvex set A the point z E A is d-extreme iff A \ {z} is d-convex. Furthermore we have extd(convd A) C extd A. In [182] the following notion is given. A point z E A is called a d-boundary point of a set A in a metric space if there exists a point y E A such that z ~ [y, X]d for any x E A \ {z}. We write bdd A for the family of all d-boundary points of a set A. Based on extd A C bdd A it is shown in [267] that for compact subsets A of a metric space convd A = convd(bdd A) holds. Furthermore, we mention here that an overview to results on d-convex sets in Cartesian products of metric spaces is given in [270, pp. 117-121]; various observations from there are weakly related to Minkowski spaces, see also [254], [164], [174] and [274]. In particular, the paper [165] of Lassak has to be mentioned here. Among other interesting observations, it contains the result that the Helly number of such Cartesian products equals the maximal Helly number of the considered metric spaces (for the notion of Helly number see below after Theorem 20). Thus [165] contains results more general than those for Minkowski spaces discussed at the end of Section 3.5 below, and these results of Lassak have consequences even for the study of Cartesian products of abstract convexities, cf. again [270, pp. 117-121].

3.5 d-convexity in Minkowski spaces Now we turn to results and observations that no longer hold for all metric spaces but for Minkowski spaces. Our first theorem in this group of results gives a characterization of d-convex sets in a Minkowski space M ~ and is taken from [255]. T h e o r e m 13. A set A C 1~d is d-convex iff for arbitrary points a, b E A any simple arc of length []a-b][ and with endpoints a, b (i.e. a metric segment) from a to b is contained in A. An immediate consequence is that each d-convex set is convex in the usual sense. On the other hand, there are many examples of convex sets A C M d that are not d-convex,

112

H. Martini and K. J. Swanepoel

and such sets might be unit balls or even d-segments of M d, see [270, § 11] or [36, § 9]. E.g., the unit ball of the gl norm (i.e., the cross-polytope C whose vertices are presented by the unit vectors of a Cartesian coordinate system) is not d-convex since its d-convex hull is the cube having the vertices of C as midpoints of its facets. For d-segments that are not convex see the discussion of d-convex hulls below. However, the following theorem holds. T h e o r e m 14. The following conditions are equivalent for any Minkowski space M d. 1. The unit ball B of M d is strictly convex. 2. The families of d-convex and linearly convex sets in M d coincide. 3. For any a, b e M d one has [a, b] = [a, b]d.

These equivalences were observed by many authors, see [43, 290, 13, 257, 76] and our discussion of d-segments above. (Similar equivalences are shown to hold for star-shaped and d-star-shaped sets in [274], see also below.) In [270, § 11] it is shown that M d is strictly convex iff the set of extreme points of A coincides with extd A for any convex set A C M d, and connections between strictly convex spaces and convex and d-convex functions are discussed in [273], cf. also Section 3.7 below. Related open questions are given in [36, Chapter VIII] (see Problem 1 there). As usual, we will use the abbreviations ext A, bd A, rbd A for the set of extreme, boundary and relative boundary points of a set A. The following structure of inclusions is known (see [270, § 11]), where A C M d denotes a convex set: ext A

U

C rbd A

U

(7)

extd A C bdd A We continue with results on d-extreme and d-boundary points in Minkowski spaces derived in [267], see also [268]. For example, extdA = 0 (or ext A = bddA) for any d-convex set A in a Minkowski plane M 2 iff its unit circle B is a parallelogram. Also bdd A = rbd A for any convex (or d-convex) set A C M 2 iff B is not a parallelogram, and extd A ¢ 0 for all compact, convex (or d-convex) sets A C M 2 iff B is not a polygon. A Minkowski plane 1M~ is called angular if there are three extreme points a, b, c of its unit circle B such that the segments [a, b], [b, c] are from the boundary of B. In [267] it is shown that a normed plane 1M~ is not angular iff A = convd(extdA) for any compact d-convex set A C 1M~. Sharpening the structure of inclusions (7) it is shown in [268] that for any dconvex set A C M d with nonempty interior the inclusions extd A C ext A C bdd A C bd A hold. Our next observations are mainly taken from [268] and give still more information related to this structure of inclusions. Namely, for any convex set A C M d the equality rbd A = bdd A holds iff o E bdd K for any proper convex cone K with apex o, and ext A C bdd A iff o E bdd K for any acute convex cone K with apex o. If, in particular, the set A is diametrically complete (cf. Section 2.5), then also rbd A = bdd A. If M d is a ~*-space, then extd A -- ~ for any d-convex set A with dim A > 2 iff the unit ball of M d is

The Geometry of Minkowski Spaces - A Survey. Part II

113

a cross-polytope. If M d is an a-space, then extd A = bdd A for any d-convex set A C M d iff the unit ball is a cross-polytope. Lassak [171] studies certain extensions of the notion of d-extreme points in Minkowski spaces. Here we also mention results of Lassak (cf. [164] and [167], but also [270, § 13]) on concepts related to affinely or convexly independent sets of points, yielding also results on strictly convex normed spaces, E-spaces and further types of spaces. The following statements can be found in [102] and [100] (see also [101] for a summary): • The supporting (or inscribed) cone with apex at any point of a d-convex set A C M d is itself d-convex. • For any d-convex set A C M d, its affine hull, relative interior or closure is d-convex as well. • Each face of a d-convex set A C M d is d-convex ( ~ a half-space is d-convex iff its bounding hyperplane is d-convex). • Any d-convex body A is the intersection of all closed d-convex half-spaces supporting A. In particular, it is proved in [270, § 11] that a set A C •d is d-convex iff each x E b d A belongs to at least one d-convex supporting hyperplane of A. Also, if a set A C M d is open, then convd A is open, and convd(cl A) C cl(cOnvd A), cf. [101] and [174]. On the other hand, if A C M d is itself d-convex, then cl A and relint A are also d-convex, cf. [102]. Related results for unbounded d-convex sets were obtained in [102] and [100], see also [36, § 11]. E.g., the maximal inscribed cone of an unbounded d-convex set in M d is also d-convex. A Minkowski space is d-strictly convex if for any two points x, y on the unit sphere, Ix, Y]d intersects the interior of the unit ball. Calder [53] studies an infinite dimensional analogue called weak uniform convexity, and proves that l ~ has this property. It is easily seen that the finite-dimensional l d hence any Minkowski space with a parallelotope as unit ball, is d-strictly convex. Calder also shows what amounts for Minkowski spaces to the following: Each closed d-convex set A in a d-strictly convex Minkowski space is Chebyshev, i.e., for any point a there is a unique point b E A nearest to the point a. (In particular, d-convex subsets of l d are Chebyshev.) We continue now with properties of d-convex hulls. For instance, with the help of d-convex hulls (of two points) it can be shown that in certain Minkowski spaces (which are not a-spaces) even d-segments might not be d-convex. The following example is given in [101] for d = 3, and it is extended to any d > 3 in [270, Example 12.1], see also [36, § 9]. Let M d, d _> 3, be a Minkowski space whose unit ball B is a d-cube (maximum norm), and let x, y be any two different points with the property that the segment Ix, y] is not parallel to any spatial diagonal (connecting two opposite vertices) of B. Then the d-convex hull of x, y is the whole space M d. (On the other hand, Ix, Y]d is obviously a bounded set.) We also note that for d -- 2 any d-segment is a d-convex set and refer to the related Problem 1 in [36, Chapter VIII], see also [257]. An analogue of the example above for the infinite dimensional situation is also given in [270, Example 11.2].

114

H. Martini and K. J. Swanepoel

We continue with properties of Minkowski spaces with d-convex unit balls. In [259] it is proved that if the unit ball B of M d, d > 3, is d-convex, then it cannot be a polytope. An alternative proof is given in [36, § 11]. In [270, § 12] it is shown that if B is d-convex, then for any k with 1 _< k < d there are infinitely many d-convex linear k-subspaces. V. Soltan [259] adds the observations that if a d-convex unit circle in a Minkowski plane is a polygon, then it has 4k + 2 (k > 1) sides, and that for any of these numbers Minkowski planes exist whose unit circles are d-convex (4k + 2)-gons. The next theorem is proved in [258]. T h e o r e m 15. The following conditions are equivalent: 1. The unit ball B of a Minkowski space M d is d-convex. 2. diam(convd A) = diam A for any bounded set A C M d. Strongly related is the equivalence of the conditions a(A) < c~ (for any bounded set A) and a(S) < c~, see again [258]. Here we also mention the observation of Petty [216] that the isoperimetrix of a Minkowski plane has to be d-convex. Various results on d-convexflats are also related to this. Since all the properties under consideration are translation invariant, it suffices to look at subspaces. A key result in this connection is the following statement from [101], which again implies the coincidence of linear convexity and d-convexity in the case of strictly convex unit balls. T h e o r e m 16. A linear subspace L of l~ d is d-convex iff for any point x E b d B n L the face Oz of x in bd B is contained in L. In [258] it is shown that for any Minkowski space M d there exist one-dimensional dconvex subspaces I1,..., Id whose direct vector sum yields the whole space, implying also that every Minkowski plane is an a-space. On the other hand, a Minkowski space is an a-space iff it has d-convex ( d - 1)-subspaces L 1 , . . . , Ld whose intersection is the origin, see again [258]. For arbitrary nontrivial linear subspaces L1, L2 of M d, the expression •(L1, L2) = 0(L1 N B, L2 A B)

(8)

with Q as Hausdorff distance defines a metric on the family G of all nontrivial subspaces of M d, and the topology determined by this metric in G does not depend on the choice of the corresponding norm. The set Gk of all k-dimensional linear subspaces is contained in G, and so Gk is a metric space with the metric (8). If Ek is used to denote the family of all d-convex k-dimensional linear subspaces, we have Ek C Gk, i.e., Ek is a subspace of the metric space Gk. For the following result we refer to [102], see also [36, § 11]. T h e o r e m 17. The set En-1 (with the metric (8)) is compact. One can easily show that there exist d-dimensional Minkowski spaces and positive integers k < d - 1 such that Ek is not compact, see e.g. [36, Example 11.11]. Our next results refer once more to a-, ~-, a*- and/~*-spaces. In [174] it is shown that, ifM d has the representation M d = M I @ " .~M,~ with norm I1"II = ~ I1"Ili, then oL*(~d) i=l

=

The Geometry of Minkowski Spaces - A Survey. Part II

115

m

E a*(Mi). For any bounded set A in a/3-space we have cl(convdA) = convd(clA), and i=1

if the d-convex hull of a set A is a polytope, then fl(A) is finite (cf. [174]). It is not hard to find Minkowski spaces that are a-spaces but not a*-spaces, see [270, Example 9.3]. Furthermore it is easy to construct Minkowski spaces for which convdB is bounded but not closed, i.e., which are a*-spaces but not ~-spaces, and also one can easily describe ~-spaces that are not fl*-spaces (see [270, Example 9.2], [36, Example 10.4], and [270, Examples 12.4 and 12.5]). In addition, for any Minkowski space M ~, d > 2, one has d _< 2z*(~), which is exact for ~ , cf. [174]. Using the following notions, one can describe unit balls of fl*-spaces geometrically. A one-dimensional linear subspace I of M d is said to be special if it is the intersection of d - 1 d-convex linear (d - 1)-subspaces. A point x E bd B is special if it is the intersection of bd B and a special subspace of M d. The following theorem (cf. [262]) gives a geometric picture of unit balls of/3*-spaces. T h e o r e m 18. If M d is a fl*-space, then its unit ball is the convex hull of the closure of all its special points. Let ]Rk+t be the direct sum of its subspaces ~k and R s, and let B1 C ]R~ , B~ C ]RZ be unit balls of Minkowski spaces M k and 1~ obtained from R k and R l, respectively. If the normed space M k+s , obtained from R k+z, has the unit ball B = conv{B1 U B2}, then lY[k+t is said to be the join o f M k a n d M s. Then the norm o f M k+s is II.[[ = [].]11+[l.l]2 where I]" 111 and I[" [[2 are the norms o f M k and Ml,respectively. The following results are obtained by P. Soltan, see [254] and [255]: Let M k+s be the join o f M k and M s, and a, b, x be points from M k+s such that (a - ~) e M k, (b - x) e M I. Then x E [a, bid. From this one can deduce the equality convd A

=conv

d rl

(A) +

c o n y d 71"2 (A)

for an arbitrary set A C M k+l , where ~rt denotes the parallel projection of M k+s along ~l onto R k, and v2 vice versa. In addition, we have diam(convd B) = diam(convd B1) -t- diam(convd B2). We say that the family of all d-convex sets in M d has the d-cone property if for any d-convex set A C M d and any point z E M d convd(A U z) = U { [ z , a]d, a e A} holds. Furthermore, the family of all d-convex sets in M d has the d-jointness property if for any two d-convex sets A, B c M d the set convd(A U B) is the union of all d-segments In, bid with a E A, b E B. Also M d is said to be the join of linear subspaces L 1 , . . . , Lk if it is their direct vector sum and the unit ball B of M d satisfies B -- conv(B n U~=lkLi). In [260] the following theorem is established. T h e o r e m 19. For a Minkowski space M g the following conditions are equivalent. 1. The family of all d-convex sets in M d has the d-cone property.

116

H. Martini and K. J. Swanepoel

2. The family of all d-convex sets in M d has the d-jointness property. 3. M d is the join of some linear subspaces L 1 , . . . , Lk each of which has a strictly convex unit ball or is two-dimensional. We say that the family of all d-convex sets in M d has the normality property if any two disjoint d-convex sets A, B can be separated by some complementary d-convex half-spaces (or if there are d-convex sets C, D with A C C, B C D and C U D = Md). Using this notion, V. Soltan [260] shows the following. T h e o r e m 20. The following properties of a Minkowski space M d are equivalent. 1. The family of all d-convex sets in 1~d has the normality property, i.e., any two dconvex sets A, B with relint A A relint B = 0 are strictly separable by some d-convex hyperplane. 2. The vector sum A + B of any two d-convex sets A, B is itself a d-convex set. 3. The vector sum of any two d-convex linear subspaces L, M of M d is a d-convex subspace of M d. 4. The space M d is the join of some of its linear subspaces L1,... ,Lk each of which has a strictly convex unit ball or is two-dimensional. In [101] and [100] it is shown that if d-convex sets A1,A2 C M d satisfy relintA1 A relint A2 = 0, then there are such maximal (under inclusion) closed d-convex cones K1,/{2 such that A1 C/{1, A2 C K2 and relint/{1 A relint/{2 = 0. At the end of this section we will discuss some combinatorial aspects of d-convexity, in particular related to generalizations of Helly's theorem. The Helly dimension him F of an (infinite) family F of sets in R d was introduced in [254], see also [38], [37, Chapter IV] and [36, Chapter II]. It is the smallest integer m > 0 such that for every collection {M1,..., Ms} C F with s > m + 1 the following holds: if each (m + 1)-subfamily from this collection has a common point, then M1 A ... A Ms ~ 0. If F does not have this property, then him F = co. Thus if 0 < him F < co is assumed, then him F is the largest integer m for which there are sets M 1 , . . , , Mm+1 E F such that each m of them have nonempty intersection and M1 A ... A Mm+l -- 9. (In the literature one can also find the HeUy number of F, which in general differs from him F only by one, cf. [70], [270] and [83].) For a Minkowski space M d one can now consider the family Cd of all d-convex sets and the family Kd of all d-convex bodies (i.e. with non-empty interior) with the conventions him Cd = him M d and him Ka = him (b) M d, calling the first of these numbers the HeUy dimension of the space M d. It easily follows that, due to Cd D ]Kd, h i m M d > him (b) M d, and from [165] (even for metric spaces), [37, § 18] and [36, § 14] one can read off various further results on these numbers. E.g., if M d is representable as a join of the spaces L 1 , . . . , L~, then himMId = max him (b) Li, i=l,...,k

The Geometry of Minkowski Spaces - A Survey. Part II

117

a result obtained by Lassak [165] even for metric spaces. Further results on the Helly dimensions of special set families (see e.g. Chapter IV in [36]) can be carried over to Minkowski spaces if such a set family is exactly the family of d-convex sets. Analogously one can extend further classical theorems, such as those of Radon and CaratModory, in terms of d-convexity, see [270, Chapter II], [164], and [167].

3. 6 On d-star-shaped sets in Minkowski spaces Again we start with some results holding even in metric spaces. A set A C X is called d-star-shaped with respect to z E A if [z, x]d C A for any x E A. The family of all points z E A with respect to which A is d-star-shaped is said to be the d-kernel of A and denoted by kernd A = {z e A : x E A =~ [z, x]d C A}. The authors of [274] prove that for any x, y C X and all 5 > d(x, y) the "metrical ellipsoid" U(x, y, 5) = {z e X : d(x, z) + d(z, y) <_ 5} is d-star-shaped, where its "foci" x, y belong to kernd U(x, y, 5). From this it follows that any d-segment Ix, Y]d and any ball B~(x) of radius 5 around x are d-star-shaped. We continue with results about d-star-shaped sets restricted to Minkowski spaces and define (besides the d-kernel kernd A of a set A C M d) also the set K(A) as the intersection of all maximal (under inclusion) d-convex sets contained in A. Obviously, one has K(A) C kerndA C kern A, with kern A as the usual kernel of A, defined by kernA = {z E A : x e A =~ [z, x] C A}. In addition, it is clear from the considerations above that any d-star-shaped set is star-shaped in the usual sense. Again from [274] we take T h e o r e m 21. For a Minkowski space M d the following conditions are equivalent.

1. The families of d-star-shaped and star-shaped sets coincide. 2. K(A) = kern A for any set A C M d. 3. kernd A = kern A .for any set A C M d.

4. The unit ball of M d is strictly convex. For any set A and every x E A let A~ := {z E A : [X,Z]d C A}, and for N C A we write AN = N{A~ : x • N}. A point x • A is a k-extremal point o.f A if w it relint S for any (k + 1)-dimensional simplex S c A. It is shown in [285] that for a compact set A c 1~4, where M d \ A is connected, the following holds: If N is the union of all (d - 2)-extremal points of A, then A is d-star-shaped iff AN ¢ 0; in this case we even ' have AN = kerndA. Furthermore, a point x • A is said to be locally d-convex in A if there is a neighbourhood N ( x ) of x such that N(x) MA is d-convex; otherwise x is locally d-nonconvex in A. Besides other related results, the paper [284] contains the following statement: For a compact, connected set A C M d we have x • kernd A iff each y E A which is locally d-nonconvex in A has a neighbourhood N(y) such that Ix, z]d C A for z • A N N ( y ) . Moreover, a closed connected set A C M d is d-convex iffany of its points is locally d-convex. Further related results on d-star-shaped sets are obtained in [274], [264], [265], [286], [287], [288], and [35], see also [270, § 14]. In particular we want to mention results that are related to Krasnosel'ski's theorem: if every d + 1 points of a star-shaped set A C E d are visible in A from a point x • A, then all points of A are visible in A from

118

H. Martini and K. J. Swanepoel

a point of A (note that y E A is visible in A from x E A if [x, y] c A). E.g., in [35] an analogue of Krasnosel'ski's theorem by means of d-visibility (i.e., visibility defined with the help of d-segments instead of usual segments) is given, which has a forerunner already in [38], see also [36, § 15]. A further extension of the usual visibility notion is proposed in Problem 5 of [36, Chapter VIII].

3. 7 Some applications of d-convexity First we mention that the notion of a convex function can be successfully extended to d-convex functions, cf. [273, 266, 269]. Continuing [81], the authors of [197] investigate the Fermat-Torricelli problem from Location Science in Minkowski spaces, i.e., the search of those points having the minimal sum of distances to arbitrarily given points. For solving certain cases of this problem they use the concept of concurrent d-segments. Verheul [294] uses the concept of modular Banach spaces for getting related results on Steiner trees. Brown [41] considers Menger's betweenness relation in the context of Approximation Theory in Minkowski spaces. In Computational Geometry d-segments are also studied, see [153]. In particular we observe that any Voronoi region of a Voronoi diagram in M d is in fact d-star-shaped. Again with the background of computational geometry, partitions of compact point sets into special (convex) parts by cuts in prescribed directions (with various practical applications) can be successfully studied in terms of d-convexity, see [227], [271] and [195]. Also one should mention that there are many results on d-convexity in ordinary (including infinite) graphs, see the respective parts of [270]. The only survey we could find in this field is [272]. In the context of combinatorial geometry, fixing systems of d-convex bodies are studied in [34].

3.8 Further convexity notions in Minkowski geometry First we will discuss the notion of B-convexity (ball convexity) which is introduced by Lassak in [166]. (To avoid confusion, we note that another notion of B-convexity is considered in [106], also for normed linear spaces, but quite different in nature.) A set A in a metric space X is said to be B-convex if, for any finite number of points, A contains the intersection of all closed balls containing these points. In [166] the relation diam convBA = diam A for any set A C X is shown, where convBA denotes the intersection of all B-convex sets containing A, also called the B-convex hull of A. That paper contains further results for Minkowski spaces. E.g., if A is B-convex, then also the affine hull, the interior and the relative interior of A are B-convex. For each boundary point x of a B-convex body K there exists a B-convex hyperplane supporting K at x, and any B-convex body K is representable as an intersection of B-convex closed half-spaces or (in the bounded case) of balls. In Euclidean space, usual convexity and ball convexity coincide, and in [168] this statement is shown to hold also for smooth unit balls. This paper contains further generalizations of the above statements, such as the observation that a set A is B-convex and compact iff it is an intersection of balls. Also various results on B-convex hulls, B-convex cones and related separation properties are derived. It is interesting to compare B-convexity with the notion of d-convexity, as it is done in [169]. For instance, let us consider two Minkowski spaces, one with unit ball B and the other with metric d such that the d-convex hulls of finite sets are closed. Then the families of B-convex sets and d-convex sets are identical iff the families of B-convex subspaces and

The Geometry of Minkowski Spaces - A Survey. Part II

119

d-convex subspaces are identical. Furthermore, in a Minkowski plane a set is d-convex iff it is B-convex with respect to the isoperimetrix as unit ball. And if d* denotes the metric induced by the dual B* of the unit ball B, then the following holds: If a one-dimensional subspace is d*-convex, then the perpendicular hypersubspace is B-convex. More generally, Lassak studies in [170] families of convex sets closed under intersections, homotheties and unions of increasing sequences of sets, having the families of d-convex and of B-convex sets as subcases. And we also remark that the concept of B-convexity can be extended to arbitrary Banach spaces, cf. [26] and [61] and the references given there. Mazur [201] shows that in Euclidean space, if Q is compact and convex, the relation Q = convs(Q) holds, and Phelps [226] characterizes all Minkowski spaces in which this holds for any compact convex subset. Brown [41] obtains related results referring to Approximation Theory in Minkowski spaces, in particular to find geometric properties of suns (a notion closely related to Chebyshev sets). A related type of ball convexity is studied by Mayer [198], see also [52]. Mayer introduces this "hyperconvexity" for smooth, strictly convex Minkowski spaces. In the planar case, the linear segment I connecting two arbitrary points of a (linearly) convex set A with I C A is replaced by a suitable arc C of a Minkowski unit circle, again satisfying C C A for arbitrary points from A. With this property A is then "hyperconvex'. Mayer proves several theorems about hyperconvex sets, particularly using curvature arguments and extending some of his statements also to higher dimensions. Due to Menger [206], a set A in a metric space with metric d is said to be metrically convex if for any pair of different points x, z E A there exists a point y E A with x ¢ y ¢ z such that d(x, z) = d(x, y ) + d ( y , z) holds, see also the beginning of Section 3.3 above. This type of convexity, its consequences and applications are discussed in [28, § 14], [47, Chapter I] and [70, §§ 9.9]. In Minkowski spaces, metrically convex sets are no longer necessarily convex. E.g., in l~ the intersection of the unit ball and the system of the d coordinate axes is a metrically convex set. On the other hand it is easy to see that any subset of a strictly convex Minkowski space is metrically convex iff it is linearly convex. Let M d be a Minkowski space with norm I1"II. A mapping f of M d is called H"II-contractive if for any x, y e M d the relation Ill(x) - f(Y)ll -< IIx - Y[I holds. Besides various related results, Gruber [118] shows that a set F is the fixed point set of some II • II-c°ntractive mapping of a Minkowski plane onto itself iff F is closed .and and metrically convex with respect to I1" II; see also the references there for related investigations. In another paper Gruber [119] gives a characterization of Chebyshev sets in Minkowski planes by means of a sharpening of metric convexity. Another kind of convexity was introduced by Boltyanski, see, e.g., [36, Chapter III] for a summary. Namely, let H denote an arbitrary subset of the unit sphere S d-1 in Euclidean d-space. Each half-space of the form {x : (~, y) < ~} with y E H and ,~ e R is said to be an H-convex half-space, and any set representable as intersection of a family of H-convex half-spaces is called an H-convex set. There are relations between H-convexity and dconvexity in a Minkowski space M d, cf. [36, § 24]. E.g., one can identify H with the set of all Euclidean unit vectors orthogonal to d-convex hyperplanes. With this convention, a closed convex set A C M d with interior points is d-convex iff it is H-convex, and so also Helly-type statements can be generalized for Minkowski spaces with the help of Hconvexity.

120

H. Martini and K. J. Swanepoel

There are more types of generalized convexity notions that might be successfully combined with Minkowski geometry. However, we did not find further substantial references related to this. 4

Bisectors a n d Voronoi d i a g r a m s

4.1 Introduction Various unsatisfactory definitions of planes in Euclidean space led Leibniz to define a plane as the locus of points having equal distances from two different points p and q. Since this definition can be carried over to various types of metric spaces, it makes sense to introduce, in this general setting, the analogous point sets as bisectors (or equidistant sets) with respect to p and q, see [194], [44], [46], [148], [9], and [214] for early contributions to this notion, the oldest being the theorem of Mann [194] that a Minkowski space is Euclidean if its bisectors are convex. A really deeper study of geometric properties of bisectors in Minkowski spaces started only with the development of Computational Geometry. In the following we will survey results on bisectors in Minkowski Geometry. The main applications of bisectors in this field are • constructions of (generalized) Voronoi diagrams and • motion planning with respect to translations, but also interesting characterizations of special types of Minkowski spaces can be obtained. There are various other definitions of bisectors, and also the given geometric configuration {p, q} can be modified. Therefore we will also present results on natural extensions and related concepts. E.g., many recent results about Voronoi diagrams in the spirit of Computational Geometry were obtained without the assumption that the unit ball is centrally symmetric (i.e., it is often assumed to be a gauge body), and also the notion of angular bisector is interesting in these spaces. In addition, bisectors were used to characterize Minkowski spaces within classes of more general types of spaces. We will also survey results on Voronoi diagrams closely related to Minkowski spaces. Basic references containing material about this viewpoint are [153], [14], and [15], but see also the monograph [212]. Furthermore, we present applications of Voronoi diagrams (such as translational motion planning) and similar concepts. Finally some further related topics, namely besides angular bisectors also sets equidistant to only one given site, are discussed.

4.2 Basic geometric properties of bisectors The bisector of two points p ~ q in a Minkowski space M d is the set

B(p, q) : =

(x e Md: Ilz -- Pll ---- [Ix -- q[[).

The tools needed to study bisectors mainly belong to the field of classical convexity. In particular, one has to consider intersections of homothets of a convex surface, cf. our first survey [196, §§ 3.3] for an extensive discussion of related results. In addition one has to underline that applications of bisectors in computational geometry (mainly referring to Voronoi diagrams) often allow an immediate consideration of underlying gauges (i.e. the unit ball does not necessarily have a centre of symmetry), where computational geometers

The Geometry of Minkowski Spaces - A Survey. Part II

121

mainly use the term "convex distance function", in other words, the unit ball is a compact, convex body with the origin o in its interior. So in this section the underlying real linear space has a gauge, and whenever we consider the particular case of a Minkowski space, this will be said explicitly or will be clear from the context. Geometric properties of bisectors in (special) Minkowski planes were first studied by [160], [180] and [181] in the ~1 metric and, more generally, in ~p norms. Independently, [233] found an interesting duality between the maximum and Manhattan norm in the plane by using geometric properties of bisectors, d-segments and circles in these norms; a discrete version of this duality and the needed geometry of bisectors is presented in [71]. For two-dimensional gauges, the first explicit proofs of the properties presented below, and related ones, were given in [200, 66, 142, 187], see also [63]. For unit bails in the plane and centred at the origin, an earlier contribution is due to Holub [136], and some if his results were presented in [196]. For special norms, investigations were done by Lee [180] and in [301]. A broad presentation can be found in the second chapter of [1871. In a Minkowski plane consider two different points p and q. Let the line segment [p, q] be horizontal, with p to the left of q, and let Bp, Bq be translates of unit balls having the centres p and q, respectively. The top point of Bp, denoted by tp, is the leftmost point of T~Bp, and the top point of Bq, denoted by tq, is the right most point of TNBq, where T is the top supporting line of Bp and Bq parallel to [p, q]. Analogously, the bottom points bp, bq are defined with the help of the bottom supporting line D of Bp and Bq which is parallel to [p, q], see Figure 3.

~{]+t

B y

/

ZI'bp

'

D

Figure 3. Constructinga bisector

Proposition 22. In a Minkowski plane the bisector B(p, q) is fully contained in the bent strip bounded by the rays ~, tp), [q, tq), [p, bp), and [q, bq). It is homeomorphie to a line iff ~, q] is not parallel to a non-degenerate segment in bd Bp, and it contains two two-dimensional regions iff ~, q] is parallel to some non=degenerate line segment in bd Bp. This statement can be easily verified by considering B(p, q) as the union of all intersections of equally sized homothetical copies of bd Bp and bd Bq with centres p and q, respectively. Thus in Figure 3 we have x E B(p, q). If the Minkowski plane is strictly convex, the bent strip in the above proposition is in fact only a strip bounded by two

122

H. Martini and K. J. Swanepoel

parallel lines. It is furthermore easy to see from the above proposition that it is only in strictly convex planes that the bisector is always contained in a strip bounded by two parallel lines. So one can conclude that, e.g., for strictly convex unit balls all bisectors are homeomorphic to lines (Holub [136] found this characterization for Minkowski planes, see also [196, § 3.3]). This can be analogously transferred to higher dimensions, see [143] for d = 3. Independently, this statement was verified for d _> 3 and Minkowski unit balls by Horv~th [137], i.e., together with Example 3 from [137] referring to the converse implication we have T h e o r e m 23. If the unit ball of a Minkowski space M d is strictly convex, then all bisectors are homeomorphie to a hyperplane. On the other hand, there exists a space M d for every d > 3 such that each bisector is a topological hyperplane, but the unit ball of M d is not strictly convex. The authors of [143] give a local formulation for unit balls B in 3-space that are not necessarily centrally symmetric: if each supporting line of B parallel to the line through the two sites p, q meets B in exactly one point, then B(p, q) is homeomorphic to a plane; see also [187, § 3]. Closely related is a paper of J. E. Valentine [291]: A Minkowski plane is said to satisfy Euclid's Proposition 7 provided for four points a, b, c, d, with c, d on the same side of aft{a, b} and I l a - c l l = I l a - d l l as well as Nb-cll = lib-rill , the coincidence c = d holds. It is proved in [291] that a real Banach space is strictly convex iff each of its 2-subspaces satisfies Euclid's Proposition 7. In addition, the paper [65] contains some further geometric properties of bisectors in Minkowski planes that are somehow unexpected. They can be summarized by T h e o r e m 24. In a Minkowski plane with strictly convex unit bail, bisectors do not necessarily have asymptotic lines, and pairs of bisectors can exist that intersect infinitely many times. In the terminology of [156] (see also [153, § 1.2]) this means that strictly convex norms are not always nice metrics. However, the authors of [65] derive a necessary and sufficient condition for a given bisector to have an asymptotic line. They prove that if the boundary of the strictly convex unit ball is a semialgebraic curve, then the intersection of any two bisectors has a finite number of connected components (yielding therefore a nice metric). Based on Blaschke's notion of shadow boundary (of the unit ball, cf. the surveys [219] and [131] for related results), Hetzelt [133] geometrically describes the asymptotic behaviour of bisectors in Minkowski spaces, which is then applied to Approximation Theory. Horv£th [138] proves that in a Minkowski 3-space all bisectors are homeomorphic to a plane iff all shadow boundaries of the unit ball are topological circles. Refining the methods suggested by Proposition 22 and Figure 3 above, the authors of [145] (cfi also [144] and [299]) construct bisectors B(p, q) in the plane where the distances from p and q are measured with respect to different gauges. Here the bisector can contain bounded or unbounded two-dimensional regions, and pieces of the bisector may even appear inside the region of all points closer to p than to q. In particular, polyhedral gauges are taken into consideration, and applications in Location Science are discussed. Finally we mention here a paper of Guggenheimer [125], in which properties of bisectors where the unit ball is a triangle are discussed.

The Geometry of Minkowski Spaces - A Survey. Part II

4.3

123

Characterization theorems based on bisectors

We start with characterizations of inner product spaces within the family of normed linear spaces by bisector properties. An old result of this type was proved by Mann [194]: A Minkowski space is Euclidean iff all its Leibnizian half-spaces (consisting of all those points which are nearer to the origin than to another point) are convex. It is clear that, considering the bounding hyperplanes of Leibnizian half-spaces, this means that all bisectors are hyperplanes. Thus, strictly speaking Mann's theorem is a forerunner of a known characterization theorem of Day [72] that was obtained as a corollary of a result of James [146], but see also [202]. Namely, we have T h e o r e m 25. All bisectors in a Minkowski space M d are hyperplanes iff the unit ball is an ellipsoid, i.e., •d

is a Euclidean space.

Strongly related characterizations are collected in § 3 of Amir's book [8]. For example, Kalisch and Straus [148] define a subset A of a Minkowski space M d to be a determining set if l i p - a l l = I I q - a l l for a l l a E A implies that p = q. They show t h a t M d is Euclidean iff every A C 1~d not contained in a hyperplane is a determining subset of M d. Not cited in [8], but strongly related to Mann's observation is a result of Panda and Kapoor [214]. They show that replacing "hyperplanes" in Theorem 4 by "convex" gives the same characterization, and they continue with similar results, taking special care for ~p spaces. Considering tilings in infinite dimensional Banach spaces, Klee [152] points out that the results in [148] and [214] are near to his investigations. There are several sharpenings and extensions of Theorem 4 that should be mentioned here. First we mention that the famous Blaschke-Marchaud characterization of ellipsoids by plane shadow boundaries (cf. the surveys [219] and [131] for related references) implies that for d _~ 3 a d-dimensional Minkowski space is Euclidean iff each bisector is contained in a region bounded by two parallel hyperplanes. (For d = 2 this property characterizes strict convexity, see Proposition 22 and the remark following it.) Woods [302] extends Mann's result to distance functions whose unit ball is not necessarily centrally symmetric or convex. In a series of papers on ellipsoid characterizations (see [115, 116, 117]) Gruber gives further generalizations, such as the following: The statement of Mann still holds if the unit ball is star-shaped with respect to the origin, but not necessarily bounded, convex, or centrally symmetric. Also, Satz 5 in [115] says that a bounded distance function yields the Euclidean norm iff there is a subset Q of the Euclidean unit sphere S d-1 having interior points with respect to S d-1 and the property that for each x E Q the Leibnizian half-space of {o, x} is convex. Theorem 25 could also be deduced from another theorem of Gruber (see [116, Satz 3]): If K is a convex body in E d (d ~_ 3) and the intersection of the boundaries of the bodies K ' and K is contained in a hyperplane for all translates K ' of K (K' # K), then K has to be an ellipsoid. Goodey [110] gives a further extension: If K1,/(2 are convex bodies in E d , d ~_ 3, and the intersection of the boundaries of the bodies/(1 and K s is contained in a hyperplane for all translates K s of K2 (K s # K1), then /(1, K2 are homothetic ellipsoids, see also [111] and [113]. For special (convex) surfaces this result was earlier obtained by Shaidenko [247]. Beem [23] extends Theorem 25 to indefinite inner product spaces considering the flatness of bisectors in real Hausdorff topological vector spaces.

124

H. Martini and K. J. Swanepoel

Guijarro and Tom~s [126] define a perpendicular bisector in a real normed space to be a hyperplane containing the midpoint of the segment ~ , q] and satisfying an orthogonality condition with respect to ~v, q] which is defined by a certain generalization of the inner product. They show that the space is Euclidean iff for all pairs p ¢ q the perpendicular bisector and B(p, q) coincide. Next we mention an interesting characterizing property of Hilbert spaces. It is easy to see that for p ¢ q in Euclidean space the bisector B(p, q) is a usual sphere if one considers differently weighted distances from p and q, respectively. More precisely, such a bisector is an Apollonius sphere, i.e., the geometric locus of those points for which the ratio of the distances from p and q (defined by the different weights) is constant. Answering a question of Stechkin, Danelich [68] proves that a normed linear space whose Apollonius spheres (or weighted bisectQrs) are spheres in the norm is a Hilbert space. Here two characterization theorems should be mentioned that are more related to reflection (inversion) than to bisectors. Namely, in a Minkowski space M ~ the inversion at its unit sphere is the mapping x - - + x/I]xl] 2 for all x C M d \ {o}. Stiles [278] proves the following two statements. T h e o r e m 26. If there exists a line in a Minkowski plane whose inversive image is a

Minkowski circle, then the plane is Euclidean. Also, if in a d-dimensional Minkowski space the inverse image of any supporting hyperplane of the unit ball is centrally symmetric, then this space is Euclidean. For special norms this mapping was also investigated in [108]. We also mention that in [7] a type of angle bisectors of triangles is used to characterize inner product spaces, and similar results are given in [6]. Busemann [44] proposes an extension of Leibniz's definition of a plane (namely to be the bisector B(p, q) of two points p ¢ q in Euclidean space) to certain metric spaces. More precisely, he assumes that such a metric space S is finitely compact (i.e., every bounded sequence of points has a convergent subsequence) and that any two distinct points from S lie on a metric line. He shows that S is a finite dimensional Euclidean or hyperbolic space iff all its bisectors are linear, i.e., for any bisector B(p, q) with x, y E B(p, q), ~ ~ y, also the metric line through x and y is in B(p, q). Motivated by Fr@chet's characterization of normed linear spaces [91] among general metric spaces and continuing Busemann's work [44] on bisectors, Andalafte and Blumenthal [9] characterize Minkowski spaces and also Euclidean spaces among all finitely compact, metric spaces by properties that are closely related to bisectors, see also [29, Chapter 7]. In [45, Chapter IV], [46, § 16], [47, § 46.1 and § 47.4], and [51, Chapter IV] one can find further characterizations of finite-dimensional normed linear spaces, Euclidean, hyperbolic and spherical spaces via bisectors similar to the results from [44]. In [51, Chapter IV] the flatness of bisectors is used, see also [223] for a stronger statement in the planar case; Guggenheimer [125] gives related results for gauges. A similar characterization of Minkowski planes, namely by the flatness of bisectors with respect to a given point and a given line, is derived in [49], and for a generalization we refer to [50]. Note that the concurrency of bisectors in triangles is discussed in [49], see also [125] for gauges. Also in the spirit of [44], Andalafte and Freese [12] give a characterization of inner product spaces within a large class of metric spaces.

The Geometry of Minkowski Spaces - A Survey. Part II

125

Danzer [69] introduces convex sets in a metric space S as intersections of Leibnizian half-spaces. Then from Busemann's investigations in [44] the following can be concluded if S is a Minkowski space M d and A C M d is an arbitrary closed convex set in the above sense: M d is an inner product space iff any two different points from A have a betweenness point in the sense of Menger, cf. Section 3.2 above. ~.~

Sets equidistant to more than two points In view of vertices in Voronoi diagrams it is essential to investigate sets that are equidistant to three or more given sites. Although the the term "k-sectors" would be more appropriate, we will follow many authors and use the notion of k-bisectors for sets equidistant to k > 2 given points. It is clear that the union of the midpoints of all spheres (defined by the given metric or norm) that pass through all these k points is the k-bisector. We refer to [196, §§7.1] for a discussion of the following result of Kramer and N~meth [159], see also [158].

P r o p o s i t i o n 27. A Minkowski plane is smooth iff through any three non-collinear points there passes at least one Minkowski circle. The analogous statement for strictly convex gauges was derived in [200], [199] and [142], related further observations are collected in § 2 of Ma's dissertation [1~7]. The proof of Kramer and N@meth is generalizable to give the forward implication in ddimensional spaces with gauges. According to Kramer and N@meth this was a conjecture of Turin. However, the corresponding statement was proven earlier by Gromov [113]. T h e o r e m 28. Let ]~d be equipped with a gauge ~fB. If the unit ball B is smooth then at least one sphere passes through any d + 1 non-collinear points. Using complicated topological methods, Makeev [191] reproves that theorem; see also [192], where a local version is shown. Based on results from the theory of additive complexity, L@ [175, 176] proves that for p an even integer there exists an upper bound on the number of/p-spheres in ddimensional space that can pass through d + 1 points in general position, this upper bound depending only on d but not on p. In [178] and [179] he proves further related results for the d-dimensional situation. E.g. the following observation, based on Goodey's [110] characterization of homothetical ellipsoids, is established in [179]: If the gauge in dspace, d _> 3, is not determined by an ellipsoid, then there exist d + 1 affinely independent points such that their (d + 1)-bisector consists of more than one point. There are drastic differences between the geometric properties of k-bisectors in twoand three-dimensional spaces. However, a deeper study in 3-space is only very recent. First we consider 3-bisectors for d = 3. For smooth and strictly convex gauges it is shown in [142] that all 3-bisectors of three non-collinear points are homeomorphic to a line. On the other hand, for non-smooth gauges in 3-space there is even no general upper bound on the number of their connected components, cf. [177]. This is sharpened in [143] and [187, § 3]: Using the concept of silhouettes (also called sharp shadow boundaries in Convexity Theory), they give conditions for the connectedness of 3-bisectors, or for the precise number of their connected components. They assume that each supporting line of the unit ball B, which is parallel to any segment connecting two of the three

126

H. Martini and K. J. Swanepoel

non-collinear given sites, meets B in exactly one point. The union of these points for one of the three directions is called the silhouette of B in the respective direction. It is homeomorphic to a simple closed curve partitioning the boundary of B into two open half-spheres. The results mentioned above are obtained by studying suitable intersection properties regarding pairs of such half-spheres, namely with respect to the connectedness of these intersections. It is pointed out in [143] that these results might be the starting point for computing 3-bisectors, e.g. for polyhedral unit balls; Lastly we consider 4-bisectors in 3-space. In [142] the following statement is established. T h e o r e m 29. For each n > 0 there exist a smooth, strictly convex Minkowski 3-space

and four points in it such that the corresponding 4-bisector contains exactly 2n + 1 points. If the four points are moved independently in small three-dimensional neighbourhoods, the 4-bisector still contains at least 2n + 1 points. There are further related results in [175, 176] and [187], for example referring to special Ip norms, polyhedral gauges and algorithmical approaches to corresponding bisectors in 3-space. E.g., in [187, §§ 3.2] the following selected results for polyhedral gauges with k facets are established, in every case assuming that the occuring silhouettes are simple closed polygons. * A bisector which has n vertices can be computed in optimal time e ( n + k). . Any 3-bisector is the union of segments and rays, and it has O(k 2) vertices. . For k _> 6 there exist 4-bisectors consisting of at least two points.

3.5 Voronoi diagrams The interdisciplinary concept of Voronoi diagrams can be roughly described as follows: In a space D let there be given a set S of fixed sites, together with a well-defined quantity of influence that a site s E S can exert on a point x E D. The Voronoi region of s then consists of all points x E D that are stronger influenced by s than by any other member of S. The survey [14] presents some different names for Voronoi regions in various scientific fields, such as Thiessen polygons in Meteorology and Geography, or Wigner-Seitz zones in Chemistry and Physics. However, the first scientists who gave a formal introduction to this concept were the mathematicians Dirichlet [78] and Voronoi [296], [297], and so the structure created by Voronoi regions of n _> 3 point sites in the Euclidean plane (taking the Euclidean distance as quantity of influence) has been called a Dirichlet tessellation or Voronoi diagram. Voronoi [297] was also the first who considered the dual structure, in which any two point sites are connected by a segment if their Voronoi regions have common boundary. Delaunay [74] observed that the same structure is obtained in the following way: two point sites are linearly connected iff they lie on a circle whose interior has empty intersection with S. Hence this dual concept is usually called Delaunay triangulation. From the geometric point of view, Voronoi diagrams and their generalizations (in higher dimensions and non-Euclidean geometries, or with sites that are no longer points) were mainly studied in Computational Geometry and Stochastic Point Processes, or as special filings. Basic references showing the large variety of existing literature in these and

The Geometry of Minkowski Spaces - A Survey. Part II

127

related directions are Aurenhammer [14], Klein [153], Okabe, Boots and Sugihara [212], Fortune [89], and Aurenhammer and Klein [15], and various textbooks and monographs in Computational Geometry contain chapters on Voronoi diagrams. Basic references for stochastic geometers are the two monographs [212] and [279]. Among the various ways of generalizing the original concept, we are interested in geometric properties of Voronoi diagrams in Minkowski spaces and their direct generalizations with respect to gauges. Perhaps the oldest result on Voronoi diagrams in Minkowski spaces is due to Mann [194]. He proved that if for all lattices of the underlying space the closed Voronoi region of a lattice point is convex then the norm is Euclidean. (It should be noticed that Gruber [116] generalized this to distance functions with bounded star-shaped unit balls, and for Minkowski spaces Horv~th [137] continued Mann's investigations on lattice-like Voronoi diagrams.) Chew and Drysdale [63] note that Voronoi regions in Minkowski planes are star-shaped (the proof holding in Minkowski spaces as well and in fact gives that the regions are dstarshaped). On the other hand, convexity fails to hold already in the gl-plane, see also [153, p. 23]. This star-shapedness and the convexity of the unit ball yield the possibility to apply divide & conquer algorithms for planar Voronoi diagrams. Thus Hwang [140], Lee and Wong [181] investigate the gl-plane, and Lee [180] the gp-planes; they succeed with algorithms to construct Voronoi diagrams of n sites in O (n log n) time. In [301] an optimal algorithm for the computation of a Voronoi diagram is given, where the distance function is based on polygonal unit balls, and Chew and Drysdale [63] present a construction in O(n logn) time for arbitrary gauges in the plane. Kiihn [162] gives a randomized parallel algorithm for the computation of Voronoi diagrams in Minkowski planes, and Skyum [251] constructs the dual of the Voronoi diagram for arbitrary gauges in the same time complexity as Chew and Drysdale did. The paper [66] deals with the question when two planar Voronoi diagrams for the same sites, but for different distance functions, have the same combinatorial structure. If C, D denote two smooth, strictly convex unit balls and the corresponding Voronoi diagrams Vc(S), VD(f(S)) have the same combinatorial structure for each set S of at most four points (for some bijection f of the plane), then f is linear and f(C) = D, up to scaling. Even stronger (in the case where D is an ellipse) [66] contains T h e o r e m 30. Let C be the unit ball of a Minkowski plane that is not Euclidean. Then there exists a set of 9 points whose Voronoi diagram with respect to C has a combinatorial structure that no Euclidean Voronoi diagram can achieve.

Related investigations regarding the ~1 and t~¢ metric are presented by Chew [62]. Further particular results on Voronoi diagrams with respect to gauges were obtained for three dimensions, and they are based in a natural way on the results on 4-bisectors given above. For example, Theorem 29 implies that there exists no upper bound on the number of vertices of a Voronoi diagram of four points in a smooth, strictly convex Minkowski 3-space. However, for special cases more can be said. For example in [32] it is shown that for n given points in general position (the precise definition depending on the norm) in 3-space the complexity of a Voronoi diagram is O(n 2) if the unit ball is an octahedron, a cube or a tetrahedron (with any interior point of the tetrahedron as the

128

H. Martini and K. J. Swanepoel

origin). More generally, Tagansky [282] obtains O(k3a(k)n21ogn) for polyhedral unit balls with k facets in 3-space. This was improved in [141] to O(n2k3a(min(k,n))) if the unit ball again has k facets, which simplifies to O(n 2) for k fixed. Here a(n) is the (extremely slowly growing) inverse of the Ackermann function, see [2, §§4.1]. See also [187] for related geometric reflections. Also in d-space some special cases were investigated. From a result of Sharir [248] on lower envelopes it follows that the complexity of a Voronoi diagram of n points in d-space with the/p-norm is in O(nd+~), the constant, however, tending to c~ with p. Also, the above result on octahedral and tetrahedral unit balls from [32] is extended there to arbitrary d for d-cubes and d-simplices as unit balls, with complexity O(n [d/2]).

3.6 More general Voronoi diagrams and applications Some more general Voronoi diagrams were already discussed above, such as Gruber's result on star-shaped unit balls, see Section 4.3. Another concept was successfully invented by Klein in 1988, see [154], [156], and the main reference [153]. This is the concept of abstract Voronoi diagrams, where assumptions on the boundaries of Voronoi regions are mainly topological in nature (e.g., their pathwise connectedness is assumed, and bisecting curves must have only finitely many intersection components). It turns out that this approach is still sufficiently strong to solve the corresponding algorithmical problems, see [15, § 4.6]. A related axiomatic approach was proposed by Stiffer [277]. We will not follow that line and only mention that the family of nice metrics [153], important in this framework, is also a generalization of gauges. Another extension is obtained by generalizing the geometric configuration under consideration, e.g., by assuming that the sites are no longer points but segments, lines, or polygons. Then the Voronoi diagrams are not necessarily piecewise linear anymore, but consist of semi-algebraic pieces if the norm is for example Euclidean or polyhedral. Their complexity is still defined to be the total number of cells, a notion which is made precise in semi-algebraic geometry, see [30]. There are also results in this direction which are combined with gauges. For example, the complexity of the Voronoi diagram with respect to a family of lines in Euclidean 3-space is O(n 3+~) (cf. [248]). It is shown in [64] that for polyhedral unit balls with a constant number of edges in 3-space the Voronoi diagram of n lines is of complexity O(n2a(n)log n), where again a(n) is the above-mentioned inverse of the Ackermann function. In addition, there exist line families satisfying the lower bound e(n2a(n)). Having translational motion planning (cf. [245]) in mind, Leven and Sharir [184] investigate planar Voronoi diagrams with polygonal sites with respect to gauges with unit ball of a simple shape, i.e., simple enough to guarantee that certain steps of constructing the Voronoi diagram can be done in constant time. For investigating the translational motion of the unit ball amidst polygonal barriers (which are now the given sites) their main tool is the following statement: With respect to a sufficiently simple convex distance function, the Voronoi diagram of N polygonal convex sites, having n sides altogether, can be computed in time O(n logN). Analogously, the authors of [203] consider translational motion planning with respect to k polygonal sites having a total of n vertices and a convex m-gon P as moved object. Using the respective Voronoi diagram generated by the gauge

The Geometry of Minkowski Spaces - A Survey. Part II

129

with unit ball P, they give a O(k log n log m) algorithm. A further discussion of motion planning and its relations to Voronoi diagrams is given in [15, § 5.4]. Voronoi diagrams are also used in Location Science, see [80]. Another application field for Voronoi diagrams is that of Minimum Spanning Trees, see [15, § 5.2], and also [140] and [155].

4.7 Subjects related to Voronoi diagrams The first subject to look at is the dual concept of Delaunay triangulations. There seem to be only two papers combining these triangulations with (special) gauges, namely [251] and [243]. Considering partitions of finite point sets by Euclidean spheres, one gets a natural relation between Delaunay triangulations in Euclidean space and oriented matroids. The author of [243] explores Delaunay triangulations and the corresponding oriented matroids for gauges. One of the results is that in smooth, strictly convex Minkowski planes which are not Euclidean there exist eight points such that their Minkowski Delaunay triangulation is not the projection of the lower envelope of a 3-polytope, and the corresponding oriented matroid is not realizable. In [251] an O(n log n) algorithm for Delaunay triangulations with respect to gauges is obtained. Farthest-point Voronoi diagrams with respect to the maximum norm axe considered

in [2051. 4.8 Angular bisectors For unit vectors a ¢ b in a Minkowski plane M 2 we call the convex set bounded by the rays [o, a}, [o, b} an angle <~aobwith the origin o as its apex. Glogovskii [107] defines the angular bisector of
For independent x and y, a point z = )~lX+Auy (A1, A2 > 0) is called the angular bisector of <~xoy provided A(x, z) = A(z, y). This is equivalent to the property

where~ := ~ .

that there exists a point z in the plane through o, x and y such that ]~'-~H = I~"-Y]]. It is easy to see that such a bisector always exists. A Minkowski space is said to have the angle ~+y bisector property if for all independent x, y with Hx]l = HYl] = 1 the element z = ll*+ull satisfies A(x, z) = A(z, y) = 1A(x, y). It is proved in [93] that any Minkowski space having the angle bisector property is Euclidean, and it is asked whether this implication still holds for a weakening of the angle bisector property. In [11] the angle bisector property from [93] is considered in more general spaces.

130

H. Martini and K. J. Swanepoel

The following definition of an angular bisector is considered by Busemann [49]: A ray [o, c) is said to be an angular bisector of <~aob in M 2 if c is the midpoint of the chord [a, b] of the unit circle B of M 2. Using only distances and hence avoiding angular measures, the bisector of an angle in the Euclidean plane can then be described by the following property: (P) Inside a convex angle with sides N1, N2 and apex a, there is a ray M with apex a such that any segment [al, a2] with ai E Ni and as -~ a (i = 1, 2) intersects M in a point b .for which

Ila - alll _ iib- lii il - 2il lib- a2[I In [49] Busemann characterizes the Minkowski planes as those Desarguesian planes (which themselves are planes whose geodesics fall on ordinary affine lines) which satisfy (P). Assuming that the circles, whose convexity follows from (P), are differentiable, he gives the same characterization of Minkowski planes among all two-dimensional straight Gspaces, cf. [47, Chapter 1] for a definition. Phadke [225] shows that the differentiability hypothesis in the second characterization is not needed. Dfivelmeyer [82] proves that a ginkowski plane is Radon (see [196, § 6.1.2]) iff Glogovskii's and Busemanns' definitions of angular bisectors coincide. A concept from computational geometry is closely related to angular bisectors, see [3] and [4]. Namely, for the case of a given polygon P, a straight skeleton is obtained as the interference pattern of certain wavefronts propagated from the edges of P. Until now, this concept waits its extension to normed planes and spaces, although there are relations to other types of distance functions, cf. [20]. g.9

Sets equidistant to only one site

Although point sets equidistant to only one given site (such as a hyperplane) are no longer bisectors, some results on such sets are very close to those on bisectors presented here. For example, some interesting characterizations of Minkowski spaces, or their extensions with gauges, can be obtained by using such equidistant loci. The authors of [99] show that for a closed subset A of a Minkowski space with strictly convex or differentiable norm and almost every r > 0 the r-level set (= union of all points whose distance from A is r) contains a relatively open subset which is a (d-1)-dimensional Lipschitz manifold and whose complement relative to the level set has ( d - l)-dimensional Hausdorff measure zero (for Minkowski planes a sharper result is obtained). Within a large class of spaces (containing the hyperbolic ones and also spaces which were studied in connection with Hilbert's fourth problem), Phadke [221] gives a characterization of the linear spaces equipped with gauges. Namely, these spaces are characterized by the property that the equidistant loci on both sides of any hyperplane are themselves hyperplanes. In [222] he gives a sharpening for the planar case and continues with related results in [224]. For d = 2 and under strong differentiability and regularity assumptions, his characterization theorem is a special case of a theorem of Funk [97].

Acknowledgements. This paper was written under a grant from the D F G - N R F agreement. It was partially written during a Research in Pairs visit of both authors to Oberwolfach, September/October 2001, and during a visit of Martini t o Unisa, January 2002. We thank Rolf Klein, Marek Lassak, Valeriu Soltan and Tony (A. C.) Thompson for valuable remarks and suggestions~ and for providing certain literature.

The Geometry of Minkowski Spaces - A Survey. Part II

131

References [Abbreviations] Jbuch. Jahrbuch fiber die Fortschritte der Mathematik Zbl. Zentralblatt MATH M R Mathematical Reviews [1] M. Aigner, G. M. Ziegler: Proofs from The Book, 2nd ed., Springer, Berlin et al., 2001. MR 2001j:00001. [2] P. K. Agarwal and M. Sharir: Davenport-Sehinzel sequences and their geometric applications. In: Handbook of Computational Geometry, eds. J.-R. Sack and J. Urrutia, Elsevier, Amsterdam, 2000, pp. 1--47. [3] O. Aichholzer, F. Aurenhammer: Straight skeletons for general polygonal figures in the plane, Voronoi's Impact on Modern Sciences II, Ed. A. M. Samoilenko, Proc. Inst. Math. National Acad. Sci. Ukraine, Vol. 21, Kiev, (1998), pp. 7-21. [4] O. Aichholzer, F. Aurenhammer, D. Alberts, B. G~rtner: A novel type of skeletons for polygons, J. UCS 1 (1995), 752-761. MR 97c:52028. [5] A. D. Aleksandrov, V. A. Zalgaller: Two-dimensional manifolds of bounded curvature. (Foundations of the intrinsic geometry of surfaces.) (in Russian), Trudy Mat. Inst. Steklov. 63, Izd. AN SSSR, Moscow, 1962. MR 27 #1911. [6] C. Alsina, P. Guijarro, M. S. Tom~s: Characterization s of inner product structures involving the radius of the inscribed or circumscribed circumference. Arch. Math. (Brno) 32 (1996), 233-239. MR. 97j:46017. [7] C. Alsina, P. Guijarro, M. S. Tom~: Some remarkable lines of triangles in real normed spaces and characterizations of inner product structures. Aequationes Math. 54 (1997), 234-241. MR 99b:39031. [8] D. Amir: Characterizations MR 88m:46001.

of inner product spaces, BirkhKuser-Verlag, Basel,

1986.

[9] E. Z. Andalafte, L. M. Blumenthal: Metric characterizations of Banach and Euclidean spaces, Fund. Math. 55 (1964), 23-55. MR 29 #2625. [10] E. Z. Andalafte, R. W. Freese: New metric characterizations of Banach spaces, Houston J. Math. 11 (1985), 147-150. MR 86j:51024. [11] E. Z. Andalafte, R. W. Freese: Characterization of inner product spaces in V- and L-spaces, J. Geom. 33 (1988), 3-10. MR 89m:51027. [12] E. Andalafte, R. Freese: Weak homogeneity of metric Pythagorean orthogonality, J. Geom. 56 (1996), 3-8. MR 97d:51022. [13] E. Z. Andalafte, J. E. Valentine: Criteria for unique metric lines in Banach spaces, Proc. Amer. Math. Soc. 39 (1973), 367-370. MR 47 #2499. [14] F. Aurenhammer: Voronoi diagrams - a survey of a ~ndamental geometric data structure, ACM Computing Surveys 23 (1991), 345-405. [15] F. Aurenhammer, R. Klein: Voronoi diagrams, Handbook of Computational Geometry, Chapter 5, Eds. J.-R. Sack and J. Urrutia, North-Holland, Amsterdam, 2000, pp. 201-290. [16] G. Averkov: Constant Minkowskian width in terms of double normals, Journal of Geometry, to appear. [17] G. Averkov: A monotonicity lemma for bodies of constant Minkowskian width, 5 pp., submitted. [18] G. Averkov: On the geometry of simpliees in Minkowski spaces, 12 pp., submitted.

132

H. Martini and K. J. Swanepoel

[19] G. Averkov, H. Martini: A characterization of constant width in Minkowski planes, 10 pp., submitted. [20] G. Barequet, M. T. Dickerson, M. T. Goodrich: Voronoi diagrams for convex polygon-offset distance functions, Discrete Comput. Geom. 25 (2001), 271-291. MR 2002k:52034. [21] M. Baronti, P. L. Papini: Diameters, centers and diametrically maximal sets, Rend. Circ. Mat. Palermo, Ser. II, 38 (1995), 11-24. MR 96f:52009. [22] F. Bavaud: Adjoint transform, overconvexity and sets of constant width, Trans. Amer. Math. Soc. 333 (1992), 315-324. MR 92k:52002. [23] J. K. Beem: A bisector characterization of indefinite inner products, Geom. Dedicata 5 (1976), 453-458. MR 55 #13222. [24] L. Beretta, A. Maxia: Insiemi convessi e orbiformi, Univ. Roma e Ist. Naz. Alta Mat. Rend. Mat. (5) 1 (1940), 1-64. MR 1,264g. [25] E. Blanc: Sur une ggngralisation des domaincs dYpaisseur constante, C. R. Acad. Sci. Paris 219 (1944), 662-663. MR 7,475f. [26] M. Blank: Characterization of spaces whose B-convex bodies are intersections of balls, Bull. Polish Acad. Sci. Math. 40 (1992) 185-187. MR 97d:46012. [27] L.M. Blumenthah Distance geometries: A study of the development of abstract metrics, University of Missouri, Columbia, 1938. [28] L. M. Blumenthal: Theory and applications of distance geometry, Second ed., Chelsea PuN. Co., New York, 1970. MR 42 #3678. (lst ed. Clarendon Press, Oxford, 1953. MR 14,1009a) [29] L. M. Blumenthal, K. Menger: Studies in geometry, W. H. Freeman and Co., San Francisco, CA, 1970. MR 42 #8370. [30] J. Bochnak, M. Coste, M.-F. Roy: Real algebraic geometry, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) 36, Springer-Verlag, Berlin, 1998. MR 2000a:14067. [31] A. Bogdewicz: Some metric properties of hyperspaces, Demonstratio Math. 33 (2000), 135-149. [32] J.-D. Boissonnat, M. Sharir, B. Tagansky, M. Yvinec: Voronoi diagrams in higher dimensions under certain polyhedral distance functions, Discrete Comput. Geom. 19 (1998), 485-519. MR 99c:52020. [33] V. G. Boltyanski, The partitioning of plane figures into parts of smaller diameter (in Russian), Colloq. Math. 21 (1970), 253-263. MR 42 #2366. [34] V. Boltyanski, H. Martini: Fixing and hindering systems in combinatorial geometry, Beitr~ige Algebra Geom. 40 (1999), 551-563. MR. 2000i:52007. [35] V. Boltyanski, H. Martini, P. S. Soltan: Star-shaped sets in normed spaces, Discrete Comput. Geom. 15 (1996), 63-71. MR 97c:52009. [36] V. Boltyanski, H. Martini, P. S. Soltan: Excursions into combinatorial geometry, Springer, Berlin, 1997. MR 98b:52001. [37] V. G. Boltyanski, P. S. Soltan: Combinatorial geometry of various classes of convex sets (in Russian). Stiinca, Kishinev, 1978. MR 80g:52001. [38] V. G. Boltyanski, P. S. Soltan: Combinatorial geometry and convexity classes (in Russian), Uspehi Mat. Nauk 33 (1978), no. 1, 3-42. MR 58 #7392. [39] V. G. Boltyanski, V. P. Soltan: Borsuk's problem (in Russian). Mat. Zametld 22 (1977), 621-631. MR 58 #2586. [40] T. Bonnesen, W. Fenchel: Theorie der konvexen KSrper. Ergebn. Math. und ihrer Grenzgebiete, Bd. 3, Springer, Berlin 1934, Zbl. 8,77. [41] A. L. Brown: Suns in normed linear spaces which are finite-dimensional, Math. Ann. 279 (1987), 87-101. MR88k:46015.

The Geometry of Minkowski Spaces - A Survey. Part II

133

[42] R. J. Bumcrot: Geometrical concepts in normed linear spaces, Portugal. Math. 26 (1967), 1-6. MR 40 #6381. [43] R. J. Bumcrot: Algebraic versus metric concepts in a normed linear space, Simon Stevin 41 (1967/1968), 252-255, MR 38 #3714. [44] H. Busemann: On Leibniz's definition of planes, Amer. J. Math. 63 (1941), 101-111. MR 2,258e. [45] H. Busemaan: Metric methods in Finsler spaces and in the foundations of geometry, Annals of Mathematics Studies No. 8, Princeton University Press, Princeton, N3, 1942. MR 4,109e. [46] H. Busemann: Local metric spaces, Trans. Amer. Math. Soc. 56 (1944), 200-274. MR 6,97f. [47] H. Busemann: The geometry of geodesics, Academic Press Inc., New York, NY, 1955. MR 17,779a. [48] H. Busemann: MR 45 #5936.

Recent synthetic

differential geometry. Springer, New York-Berlin, 1970.

[49] H. Busemann: Planes with analogues to Euclidean angular bisectors, Math. Stand. 36 (1975), 5-11. MR 51 #8961. [50] H. Busemann: Remark on "Planes with analogues to Euclidean angular bisectors", Math. Seand. 38 (1976), 81-82, MR 53 #9042. [51] H. Busemann, B. B. Phadke: Spaces with distinguished geodesics, Marcel Dekker, Inc., New York, NY, 1987. MR 88g:53075. [52] J. Buter: Uberkonvexe Mengen in der Ebene. Proc. Akad. Wetensch. Amsterdam 41 (1938), 756762. Zbl. 20.07602. [53] J. R. Calder: A property oflp spaces, Proc. Amer. Math. Soc. 17 (1966), 202-206. MR 32 ~8112 [54] Y. D. Chai, Yong I1 Kiln: Geometric inequalities in the Minkowski plane, The Youngnam Math. J. 1 (1994), 1-7. [55] Y. D. Chai, Yong I1 Kim: Curves of constant relative breadth, Kyungpook Math. J. 37 (1997), 365-370. MR 98k:52010. [56] G. D. Chakerian: Sets of constant width. Pacific J. Math. 19 (1966), 13-21. MR 34 ~4986. [57] G. D. Chakerian: Sets of constant relative width and constant relative brightness, Trans. Amer. Math. Soc. 129 (1967), 26-37. MR 35 #3545. [58] G. D. Chakerian: Mixed volumes and geometric inequalities, In: Convexity and Related Combinatorial Geometry, Proc. 2nd Univ. Oklahoma Conf., Lecture Notes in Pure and Appl. Math. 76, pp. 57-62, Marcel Dekker, Inc., New York 1982. MR 83g:52010. [59] G. D. Chakerian: The number of diameters through a point inside an oval, Rev. Uni6n Matem. Argentina 29 (1984). 282-290. [60] G. D. Chakerian, H. Groemer: Convex bodies of constant width, In: Convexity and its Applications, Eds. P. M. Gruber and J. M. Wills, Birlda~iuser,Basel, 1983, pp. 49-96. MR 85f:52001. [61] D. Chen, B.-L. Lin: On B-convex and Mazur sets of Banaeh spaces, Bull. Polish Acad. Sci. Math. 43 (1995), 191-198. MR 97f:46027. [62] L. P. Chew: Near-quadratic bounds for the L1 Voronoi diagram of moving points, Comput. Geom. 7 (1997), 73-80. MR 97m:68194. [63] L. P. Chew, R. L. Drysdale: Voronoi diagrams based on convex distance functions, Proc. 1st ACM Sympos. Comput. Geom., Baltimore (1985), pp. 235-244. [64] L. P. Chew, K. Kedem, M. Sharir, B. Tagansky, E. Welzh Voronoi diagrams of lines in 3-space under polyhedral convex distance functions, Proe. 6th ACM-SIAM Symp. on Discrete Algorithms, 1995, pp. 197-204, ACM, New York, 1995. MR 96e:68128. Also in Journal of Algorithms 29 (1998), 238-255. [65] A. G. Corbolan, M. Maz6n, T. Recio: Geometry of bisectors for strictly convex distances, Internat. J. Comput. Geom. Appl. 6 (1996), 45-58. MR 97b:52001.

134

H. Martini and K. J. Swanepoel

[66] A. G. Corbolan, M. Mazdn, T. Recio. F. Santos: On the topological shape of planar Voronoi diagrams, Proc. 9th Ann. ACM Sympos. Comput. Geom. (1993), 109-115. [67] L. Dalla, N. K. Tamvakis: Sets of constant width and diametrically complete sets in normed spaces, Bull. Soe. Math. Grace (N.S.) 26 (1985), 27-39. MR 87i:52002. [68] I. A. Danelich: Normed spaces which satisfy Apollonius' theorem, Mat. Zametki 20 (1976), 247252. English Translation Math. Notes 20 (1976), 696--699. MR 55 #8766. [69] L. Danzer: Uber Durehschnittseigenschaften n-dimensionaler Kugelfamilien, J. Reine Angew. Math. 208 (1961), 181-203. MR 25 #5453. [70] L. Danzer, B. Griinbaum, V. Klee: Helly's theorem and its relatives, In: Convexity, Proc. Sympos. Pure Math. 7, Ed. V. Klee, Amer. Math. Soc., Providence, R.I., 1963, pp. 101-180, MR 28 #524 [71] P. P. Das: The discrete version of a geometric duality theorem, J. Geom. 38 (1990), 23-38. MR 91h:51017. [72] M. M. Day: Some characterizations of inner-product spaces, Trans. Amer. Math. Soc. 62 (1947), 320-337. MR 9,192c. [73] M. M. Day: Normed linear spaces, Third ed., Ergebnisse der Mathematik und ihrer Grenzgebiete, Bd. 21, Springer, New York-Heidelberg, 1973. MR 49 #9588. [74] B. Delaunay: Sur la sphere vide. A la memoire de Georges Voronoi, Izv. Akad. Nauk SSSH, Otdelenie Mat. i Estestv. Nauk 7 (1934), 793-800. [75] C. R. Diminnie, A. G. White: Remarks on strict convexity and betweenness postulates, Demonstratio Math. 14 (1981), 209-220. MR 82k:52004. [76] C. Diminnie, A. White: A note on strict convexity and straight lines in normed spaces, Demonstratio Math. 10 (1977), 827-829. MR 57 #13452. [77] A. Dinghas: Verallgemeinerungen eines Blaschkeschen Satzes iiber konvexe K6rper konstanter Breite, Rev. Math. Union Interbalkan. 3 (1940), 17-20. MR 2,261g. [78] P. G. L. Dirichlet: Uber die Reduction der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen, J. Reine Angew. Math. 40 (1850), 209-227. [79] K. Doliwka: On five points in the boundary of a plane convex body pairwise in at least unit relative distances, J. Geom. 53 (1995), 76-78. MR 96g:52013 [80] Z. Drezner, H. W. Hamacher (eds.), Facility location, Applications and theory, Springer-Verlag, Berlin, 2002. MR 2003e:90003 [81] R. Durier, C. Michelot: Geometrical properties of the Fermat-Weber problem, Europ. J. Oper. Res. 20 (1985), 332-343. MR 87a:90048. [82] N. Dfivelmeyer: A characterization of Radon curves, J. Geom, to appear. [83] J. Eckhoff: Helly, Radon, and Carathdodory type theorems, in: Handbook of Convex Geometry (ed. by P. M. Gruber and J. M. Wills), Vol. A, pp. 389-448, North-Holland, Amsterdam, 1993, MR 94k:52010. [84] H. G. Eggleston: Notes on Minkowski geometry I: Relations between the circumradius, diameter, inradius and minimal width of a convex set, J. London Math. Soc. 33 (1958), 76-81. MR 20 #1281. [85] H. G. Eggleston: Sets of constant width in finite dimensional Banach spaces, Israel J. Math. 3 (1965), 163-172. MR 34 #583. [86] G. Ewald: Von KIassen konvexer KSrper erzeugte Hilbertr~iume, Math. Ann. 162 (1965/1966), 140-146, MR. 32 #8255. [87] G. Ewald, G. C. Shephard: Normed vector spaces consisting of classes of convex sets, Math. Z. 91 (1966), 1-19. MR 32 #4597. [88] E. de Castro Feitosa: Sets of constant width and inequalities in Minkowski spaces, Ph.D. Thesis, Univ. of California, Davis, 1983.

The Geometry of Minkowski Spaces - A Survey. Part II

135

[89] S. Fortune: Voronoi diagrams and Delaunay triangulations, Handbook of Discrete and Computational Geometry, Eds. J. E. Goodman and J. O'Rourke, Chapter 20, pp. 377-388, CRC Press, Boca Raton, FL, 1997. MR 2000j:52001. [90] C. Franchetti: Relationship between the Jung constant and a certain projection constant in Banach spaces, Ann. Univ. Ferrara Sez. VII (N.S.), 23 (1977), 39-44. MR 58 #12292. [91] M. Fr~chet: Ddfinitions de la somme et du produit par scalaire en termes de distance, Ann. Sci. ~.cole Norm. Sup. (3) 75 (1958), 223-255. MR 21 #4394. [92] R. W. Freese, E. Z. Andalafte: Criteria for unique lines, J. Geom. 24 (1985), 198-201. MR 86h:52002. [93] R. W. l~eese, C. R. Diminnie, E. Z. Andalafte: Angle bisectors in normed linear spaces, Math. Nachr. 131 (1987), 167-173, MR 89c:46032. [94] R. Freese, G. Murphy: The CMP and Banach spaces with unique metric lines, J. Geom. 14 (1980), 50-58. MR 81g:51008. [95] R. Freese, G. Murphy: Strictly convex spheres in V-spaces, Fund. Math. 117 (1983), 109-115. MR 84j:51027. [96] R. E. Fullerton: Integral distances in Banach spaces, Bull. Amer. Math. Soc. 55 (1949), 901-905. MR 11,369c. [97] P. Funk: Uber die Geometrien, bei denen die Geraden die kiirzesten Linien sind und die Aquidistanten zu einer Geraden wieder Gerade sind, Monatsh. Math. Phys. 37 (1930), 153-158. [98] R. J. Gardner: MR 96j:52006.

Geometric Tomography,

Cambridge University Press, Cambridge, 1995.

[99] R. Gariepy, W. D. Pepe: On the level sets of a distance function in a Minkowski space. Proc. Amer. Math. Soc. 31 (1972), 255-259. MR 44 #4646. [100] L. F. German, P. S. Soltan: The separation property of&convex sets (in Russian), Prikl. Mat. i Programmirovanie 12 (1974), 49-61. MR 52 #15246. [101] L. F. German, P. S. Soltan, V. P. Soltan: Some properties of d-convex sets (in Russian), Dokl. Akad. Nauk SSSR 212 (1973), 1276-1279. MR 48 #12296. English transl. Soviet Math. Dokl. 14 (1973), 1566-1570. [102] L. F. German, V. P. Soltan: Certain properties of d-convex sets (in Russian), Prikl. Mat. i Programmirovanie 10 (1973), 47-61. MR 48 #12320. [103] M. Ghandehari: Geometric inequalities in the Minkowski plane, Ph.D. Dissertation, University of California, Davis, 1983. [104] M. Ghandehari: Polar duals of convex bodies, Proc. Amer. Math. Soc. 113 (1991), 799-808. MR 92b:52015. [105] M. Ghandehari, E. J. O'Neilh Self-circumference of rotors, Aeta Math. Hungar. 79 (1998), 179190. MR 99c:52009. [106] D. P. Giesy: On a convexity condition in normed linear spaces, Trans. Amer. Math. Soc. 125 (1966), 114-146. MR 34 #4866. [107] V. V. Glogovskii: Bisectors on the Minkowski plane with norm (Izl p + [ylp) (in Ukrainian), Visnik Lviv. Politehn. Inst. 44 (1970), 192-198, 218. MR 45 #2597. [108] V. V. Glogovskii: Inversion of lines in the metric 0p = ~ Iz~lp (in Ukrainian, Russian summary), Visnik Lviv. Politehn. Inst. 87 (1974), 131-136, 162. MR 53 #6410. [109] S. Got~b, H. H~rlen: Minkowskisehe Geometric I und I1, Monatsh. Math. Phys. 38 (1931), 387398. [110] P. R. Goodey: Homothetic ellipsoids, Math. Proc. Cambridge Philos. Soc. 93 (1983), 25-34. MR 84e:52006.

136

H. Martini and K. J. Swanepoel

[111] P.R. Goodey, M. M. Woodcock: Intersections of convex bodies with their translates, The Geometric Vein, Springer, New York-Berlin 1981, pp. 289-296. MR 84e:52014. [112] It. Groemer: On complete convex bodies, Geom. Dedicata 20 (1986), 319-334. MR 87h:52008. [113] M. L. Gromov: Simplexes inscribed in a hypersurface (in Russian), Mat. Zametki 5 (1969), 81-89. MR 39 #6220. English transl. Math. Notes 5 (1969), 52-56. [114] J. de Groot: Some special metrics in general topology, Colloq. Math. 6 (1958), 283-286. MR 21 ~3828 [115] P. Gruber: Uber kennzeiehnende Eigenschaften yon euklidischen Riiumen und Ellipsoiden. I, J. Reine Angew. Math. 265 (1974), 61-83. MR 49 #3694. [116] P. Gruber: Uber kennzeichnende Eigenschaften yon euklidisehen Riiumen und Ellipsoiden. II, J. Reine Angew. Math. 270 (1974), 123-142. MR 54 #5974. [117] P. M. Gruber: Uber kennzeichnende Eigenschaftcn yon EUipsoiden und euklidischen R5umen. III, Monatsh. Math. 78 (1974), 311-340. MR 57 #7381. [118] P.M. Gruber: Fixpunktmengen yon Kontraktionen in endlich-dimensionalen normierten R~iumen, Geom. Dedicata 4 (1975), 179-198. MR 57 #1279. [119] P. M. Gruber: Planar Chebyshev sets, In: Mathematical Structures--Computational Mathematics--Mathematical Modelling, 2, Sofia, 1984. pp. 184-191. MR 86k:41032. [120] B. Griinbaum: Borsuk's partition conjecture in Minkowski planes, Bull. Res. Council Israel 7F (1957/1958), 25-30. MR 21 #2209. [121] B. Griinbaum: On a conjecture o]Hadwiger, Pacific J. Math. 11 (1961), 215-219. MR 25 ~1492. [122] B. Griinbanm: Borsuk's problem and related questions, In: Convexity, ed. V. Klee, Proc. Sympos. Pure Math., Vol. 7, Amer. Math. Soc., Providence, It. I.~ 1963, 271-282. MR 27 #4134. [123] B. Grfinbanm, L. M. Kelly: Metrically homogeneous sets, Israel J. Math. 6 (1968), 183-197. MR 39 #6180 (Corrigendum: Israel J. Math. 8 (1970), 93-95. MR 42 #3679). [124] H. Guggenheimer: Pseudo-Minkowski differential geometry, Ann. Mat. Pura Appl. (4) 70 (1965), 305-370. Mit 32 #8295. [125] H. Guggenheimer: Elementary geometry of the unsymmetric Minkowski plane, Rev. Uni6n Matem. Argentina 29 (1984), 270-281. [126] P. Guijarro, M. S. Tom~s: Perpendicular bisectors and orthogonality, Arch. Math. (Basel) 69 (1997), 491-496. MR 99a:39059. [127] P. C. Hammer: Convex curves of constant Minkowski breadth, Proc. Sympos. Pure Math., Vol. VII, Amer. Math. Soc., Providence, R. I., 1963, pp. 291-304. MR 27 #4136. [128] P. C. Hammer, T. J. Smith: Conditions equivalent to central symmetry of convex curves, Proc. Cambridge Philos. Soc. 60 (1964), 779-785. Mit 30 #506. [129] E. Hell: Versch~rfungen des Vierscheitelsatzes und ihre relativgeometrischen Verallgemeinerungen. Math. Nachr. 45 (1970), 227-241. MR 42 #5158. [130] E. Heil: Kleinste konvexe K~rper gegebener Dicke~ Preprint Nr. 453, Technische Hochschule Darmstadt, 1978. [131] E. Hell, H. Martini: Special convex bodies, In: Handbook of Convex Geometry (Eds. P. M. Gruber and J. M. Wills), North-Holland, Amsterdam, 1993, pp. 347-385. MR 94h:52001. [132] A. Heppes: On a characterization of curves o] constant width (in Hungarian; Russian and English summaries),, Mat. Lapok l0 (1959), 133-135. MR 22 #1846. [133] L. Hetzelt: On suns and eosuns in finite-dimensional normed real vector spaces, Acta Math. ttungar. 45 (1985), 53-68. MR 86h:41037. [134] H. Hirakawa: An extension of the vectorial domain of an oval for the relative geometry, Proc. Phys.-Math. Soc. Jap., III. s., 16 (1934), 73-75.

The Geometry of Minkowski Spaces - A Survey. Part II

137

[135] J. Hirakawa: The affine breadth and its relation to the relative breadth, Japan. J. Math. 12 (1935), 43-50. Zbl. 12,272. [136] J. R. Holub: Rotundity, orthogonality, and characterizations of inner product spaces, Bull. Amer. Math. Soc. 81 (1975), 1087-1089. MR 52 #1263. [137] .~. G. Horv~th: On bisectors in Minkowski normed spaces, Acta Math. Hungar. 89 (2000), 233-246. MR. 2003e:52007. [138] ~. G. Horv~th: Bisectors in Minkowski 3-space, Beitriige Algebra Geom., to appear. [139] D. Hug: Measure, curvatures and currents in convex geometry, Habilitationsschrift, University of Freiburg, 1999. [140] F. K. Hwang: An O(nlogn) algorithm for rectilinear minimum spanning trees, J. Assoc. Comput. Mach. 26 (1979), 177-182. MR 80c:68029. [141] C. Icking, L. Ma: A tight bound for the complexity of Voronoi diagrams under polyhedral convex distance functions in 319, Proc. 33d Ann. ACM Sympos. Theory Comput., STOC 2001, Crete, Greece, 2001. [142] C. Ieking, R. Klein, N.-M. L6, L. Ma: Convex distance functions in 3-space are different, Proc. 9th Annu. ACM Sympos. Comput. Geom. (1993), 116-123; Fund. Inform. 22 (1995), 331-352. MR. 96k:52013. [143] C. Icldng, R. Klein, N.-M. L6, L. Ma, F. Santos: On bisectors for convex distance functions in 3-space, Proe. l l t h Canadian Conf. Comp. Geom. Vancouver, BC, Canada, August 15-18, 1999, pp. 291-299. [144] C. Ieking, R. Klein, L. Ma, S. Nickel, A. Weigler: On bisectors for different distance functions, Proc. Fifteenth Annual ACM Sympos. Comput. Geom. (Miami Beach, FL, 1999), ACM, New York, 1999, pp. 291-299. MR 2001j:68128. [145] C. Icldng, R. Klein, L. Ma, S. Nickel, A. WeiBler: On bisectors for different distance functions, Discrete Appl. Math. 109 (2001), 139-161. MR 2001j:65027. [146] R. C. James: Innerproduets in normed linear spaces, Bull. Amer. Math. Soc. 53 (1947), 559-566. MR 9,42d. [147] L. Janos, H. Martin: Metric characterizations of dimension/or separable metric spaces, Proe. Amer. Math. Sou. 70 (1978), 209-212. MR 57 #13876. [148] G. K. Kalisch, E. G. Straus: On the determination of points in a Banaeh space by their distances from the points of a given set, An. Acad. Brasil Ci. 29 (1957), 501-519. [149] P. J. Kelly: On Minkowski bodies of constant width, Bull. Amer. Math. Soc. 55 (1949), 1147-1150. MR 11,387a. [150] Y. I. Kim, Y. D. Chai: Geometric properties of curves in the Minkowski plane, Honam Math. J. 19 (1997), 107-116. MR 98g:52003. [151] Y. I. Kim, Y. D. Chal: Inequalities for the area of constant relative breadth curves, Bull. Korean Math. Soc. 36 (1999), 15-23. MR 99k:52016. [152] V. Klee: Do infinite-dimensional Banach spaces admit nice tilings? Studia Sci. Math. Hungar. 21 (1986), 415-427. MR 89h:52015. [153] R. Klein: Concrete and Abstract Voronoi Diagrams. Lecture Notes in Computer Science 400, Springer-Verlag, Berlin, 1989. MR 92f:68180. [154] R. Klein: Abstract Voronoi diagrams and their applications (extended abstract), Proc. Intern. Workshop Comp. Geom. (CG '88), Wiirzburg, March 24-25, 1988, Lecture Notes in Computer Science 333, Springer-Verlag, New York, 1988, pp. 148-157. MR 90h:68006. [155] R. Klein, A. Lingas: Manhattonian proximity in a simple polygon, Internat. J. Comput. Geom. Appl. 5 (1995), 53-74. MR 96e:58134.

138

H. Martini and K. J. Swanepoel

[156] R. Klein, D. Wood: Voronoi diagrams based on general metrics, Proc. Fifth Ann. Symp. Theor. Aspects Comp. Sci. Bordeaux, February 11-13, 1988, Lecture Notes in Computer Science 294, Springer-Verlag, Berlin, 1988, pp. 281-291. MR 89b:68011 [157] R. Klein, K. Mehlhorn, S. Meiser: Randomized incremental construction of abstract Voronoi diagrams, Comput. Geom. 3 (1993), 157-184. MR 94j:68301. [158] H. Kramer, A. B. N@meth: Equally spaced points for families of compact sets in Minkowski spaces, Mathematica (Cluj) 15(38) (1973), 71-78. MR 50 #14504. [159] H. Kramer, A. B. N@meth: The application of Brouwer's fixed point theorem to the geometry of convex bodies (in Romanian). An. Univ. Timi~oara Ser. ~ti. Mat. 13 (1975), 33-39. MR 57 #7384. [160] E. F. Kranse: Taxicab Geometry: an adventure in non-Euclidean geometry, Dover, New York, 1987. Original edition: Addison-Wesley, 1975. [161] T. Kubota, D. Hemmi: Some problems of minima concerning the oval, J. Math. Soe. Japan 5 (1953), 372-389. MR 15,981j. [162] U. Kfihn: A randomized parallel algorithm for Voronoi diagrams based on symmetric convex distance functions, Discrete Appl. Math. 109 (2001), 177-196. MR 2002a:68137. [163] Y. S. Kupitz, H. Martini: On the weak circular intersection property, Studia Sci. Math. Hungar. 36 (20OO),371-385. MR 2001h:52001. [164] M. Lassak: The Helly dimension and the Carathdodory dimension for finite-dimensional normed spaces (in Russian), Mat. Issled. l0 (1975), 107-114. MR 53 #1427. [165] M. Lassak, The HeUy dimension for Cartesian products of metric spaces (in Russian), Mat. Issled. 10 (1975), 159-176. MR 53 #1425. [166] M. Lassmk: On metric B-convexity for which diameters of any set and its hull are equal, Bull. Acad. Polon. Sci. [email protected]. Math. Astronom. Phys. 25 (1977), 969-975. MR 57 #1271. [167] M. Lassak: The independence of points in a metric space (in Russian), Fund. Math. 96 (1977), 53-66. MR 57 #10613. [168] M. Lassak: Some properties of B-convexity in Minkowski-Banach spaces, Bull. Acad. Polon. Sci. S@r. Sci. Math. 27' (1979), 97-106. MR 81e:52002. [169] M. Lassak: Some connections between B-convexity and d-convexity, Demonstratio Math. 15 (1982), 261-270. MR 85a:52005. [170] M. Lassak: Families of convex sets closed under intersections, homotheties and uniting increasing sequences of sets, Fund. Math. 120 (1984), 15-40. MR 86e:52003a. (Errata: Fund. Math. 124 (1984), 287. MR 86e:52003b.) [171] M. Lassak: Terminal subsets of convex sets infinite-dimensional real normed spaces, Colloq. Math. 50 (1986), 249-255. MR 87k:52010. [172] M. Lassak: On five points in a plane convex body pairwise in at least unit relative distances. In: Intuitive Geometry (Szeged, 1991), Colloq. Math. SocJ~nos Bolyai 63, North-Holland, Amsterdam, 1994, pp. 245-247. MR 97a:52008. [173] M. Lassak, H. Martini: Reduced bodies in Minkowski spaces, Acta Math. Hungar., to appear. [174] M. Lassak, V. P. Soltan: A certain classification of metric spaces from the point of view of dconvexity (in Russian), Mat. Issled. 10 (1975), 90-106. MR 53 #1426. [175] N.-M. L~: On Voronoi diagrams in the Lp-metric in higher dimensions, Proc. l l t h Sympos. Theoret. Aspects Comput. Sci. (STACS 94) (Caen, 1994), Lecture Notes in Computer Science 775, Springer, Berlin, 1994, pp. 711-722. MR 95h:68186 [176] N.-M. L~: On Voronoi diagrams in the Lp-metric in R D, Discrete Comput. Geom. 16 (1996), 177-196. MR 98b:68191.

The Geometry of Minkowski Spaces - A Survey. Part II

139

[177] N.-M. L~: On non-smooth convex distance functions, Inform. Process. Lett. 63 (1997), 323-329. MR 98k:68168. [178] N.-M. L~: On general properties of strieay convex smooth distance functions in ~a Proc. 5th Canad. Conf. Comput. Geom. (Waterloo~ 1993), 375-380. [179] N.-M. L~: Randomized incremental construction of simple abstract Voronoi diagrams in 3-space, Proc. 10th Internat. Symp. Fund. Comp. Th. (Dresden, 1995), Lecture Notes Computer Science 965 Springer, Berlin, 1995, pp. 333-342; Comput. Geom. 8 (1997), 297-298. MR. 98j:52023. [180] D. T. Lee: Two-dimensional Voronoi diagrams in the Lp-metric, J. Assoc. Comput. Math. 27 (1980), 604-618. MR, 83e:68077. [181] D. T. Lee, C. K. Wong: Voronoi diagrams in L1 (L~) metrics with 2-dimensional storage applications, SIAM J. Comput. 9 (1980), 200-211. MR, 81d:68053. [182] A. Lelek, W. Nitka: MR, 23 #A2192

On convex metric spaces, L Fund. Math. 49 (1960/1961), 183-204.

[183] H. Lenz: Die Eilinien mit einer Sehar konjugierter Durchmesserpaare, Arch. Math. 9 (1958), 134-139. MR, 21 #2204. [184] D. Leven, M. Sharir: Planning a purely translational motion for a convex object in two-dimensional space using generalized Voronoi diagrams, Discrete Comput. Geom. 2 (1987), 9-31. MR, 88i:68092. [185] J. E. Lewis: A Banach space whose elements are classes of sets of constant width, Canad. Math. Bull. 18 (1975), 679-689. MR 58 #12289. [186] P. Loomis: Covering among constant relative width bodies in the plane, Ph.D. Dissertation, University of California, Davis, 1980. [187] L. Ma: Bisectors and Voronoi diagrams for convex distances functions, Dissertation, Fernuniversit~t Hagen, 1999. [188] H. Maehara: Convex bodies forming pairs of constant width, J. Geom. 22 (1984), 101-107. MR, 86a:52007. [189] E. Makai, Jr., H. Martini: A new characterization of convex plates of constant width, Geom. Dedicata 34 (1990), 199-209. MR, 91g:52001. [190] E. Makai, Jr., H. Martini: On the number of antipodal and strictly antipodal pairs of points in finite subsets of Rd, In: The Victor Klee Festschrift, eds. P. Gritzmann and B. Sturmfels, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 4, Amer. Math. Soc., Providence, R,I, 1991, pp. 457-470. MR, 92f:52020. [191] A. M. Makeev: The degree of a mapping in some problems of combinatorial geometry (in Russian), Ukrain. Geom. Sb. 30 (1987), 62-66, transl, in J. Soviet Math. 51 (1990), 2544-2546. MR, 88m:55001. [192] A. M. Makeev: Inscribed simplices of a convex body (in Russian), Ukraln. Geom. Sb. 35 (1992), 47-49, transl, in J. Math. Sci. 72 (1994), 3189-3190. MR 95d:52006. [193] P. Mani-Levitska: Characterizations of convex sets, In: Handbook of Convex Geometry, Eds. P. M. Gruber and J. M. Wills. North-Holland, Amsterdam, 1993, pp. 19-41. MR 94k:52001. [194] H. Mann: Untersuehungen iiber Wabenzelten bei allgemeiner Minkowskischer Metrik, Monatsh. Math. Phys. 42 (1935), 417-424. [195] H. Martini, P. Soltan: On convex partitions of polygonal regions, Discrete Math. 195 (1999), 167-180. MR 99j:52016. [196] H. Martini, K. J. Swanepoel, G. Weiss: The geometry of Minkowski spaces - a survey. Part I. Expo. Math. 19 (2001), 97-142. MR, 2002h:46015a. (Errata: Expo. Math. 19 (2001), p. 364. MR 2002h:46015b) [197] H. Martini, K. J. Swanepoel, G. Weiss: The Fermat-Torricelli problem in normed planes and spaces, J. Optim. Theory Appl. 115 (2002), 283-314.

140

H. Martini and K. J. Swanepoel

[198] A. E. Mayer: Eine fJberkonvexitiit, Math. Z. 39 (1934), 512-531. Zbl. 10,270. [199] M. L. Maz6n: Diagramas de Voronoi en ealeidoscopios, Ph.D. Thesis, Universidad de Cantahria, Santander, 1992. [200] M. L. Mazdn, T. Recio: Voronoi diagrams based on strictly convex distances in the plane, Manuscript, Departamento de Matem~ticas, Universidad de Cantabria, Santander, 1991. [201] S. Mazur: /.Iber schwache Konvergenz in den R~umen (LP), Studia Math. 4 (1933), 128-133. [202] S. Mazur: Quelques propertigs caraetdristiques des espaces euclideans, C. R. Acad. Sci. Paris 207 (1938), 761-764. [203] M. McAllister, D. Kirkpatrick, J. Snoeyink: A compact piecewise-linear Voronoi diagram for convex sites in the plane, Discrete Comput. Geom. 15 (1996), 73-105. MR 97c:68159. [204] E. Meissner: (J'berPunktmengen konstanter Breite. Vierteljahresschr. Naturforsch. Ges. Ziirich 56 (1911), 42-50. Jbuch. 42,91. [205] E. Melanchrinoudis, Z. Xanthopulos: A maximum Lp distance problem, J. Math. Anal. Appl. 217 (1998), 650-671. MR 99d:90042. [206] K. Menger: Untersuehungen iiber allgemeine Metrik, I, II, III, Math. Ann. 100 (1928), 75-163. [207] K. Menger: Metrisehe Untersuchungen. Ergebnisse eines mathematischen Kolloquiums (Wien), 1 (1931), 20-27. [208] L. Montejano: Cuerpos de aneho constante. UniversidadNacionalAut6nomade Mexico, Fondo de CulturaEeon6mica,Mexico, 1998. [209] W. Nitka: Remarks on sets convex in the sense of J. de Groot, Indag. Math. 21 (1959), 36-38. MR 21 #3829. [210] W. Nitka, L. Wiatrowska: Linearity in the Minkowski space with non-strictly convex spheres, Colloq. Math. 20 (1969), 113-115. MR 39 #2070. [211] D. Ohmann: Ex~remalprobleme flit konvexe Bereiehe der euklidischen Ebene, Math. Z. 55 (1952), 346-352. MR 14,76a. [212] A. Okabe, B. Boots, K. Sugihara, S. N. Chiu: Spatial tesselations: concepts and applications of Voronoi diagrams, 2nd ed., John Wiley & Sons, Chichester, 2000. [213] J. P£h Uber ein elementares Variationsproblem, Math.-fys. Medd., Danske Vid. Selsk. 3 (1920), no. 2, 35 pp. [214] B. B. Panda, O. P. Kapoor: On equidistant sets in normed linear spaces, Bull. Austral. Math. Soc. 11 (1974), 443-454. MR 50 #10763. [215] R. PayS., D. Yost: The two-ball property: transitivity and examples. Mathematika 35 (1988), 190197. MR 90a:46036. [216] C. M. Petty: On the geometry of the Minkowski plane, Riv. Math. Univ. Parma 6 (1955), 269-292. MR. 18,760e. [217] C. M. Petty: Isoperimetric problems, Proc. Conf. Convexity Combin. Geom. (Univ. of Oklahoma, Norman, Okla. 1971), Dept. Math., Univ. Oklahoma, Norman, Okla., 1971, pp. 26-41. MR 50 #14499. [218] C. M. Petty: Geominimal surface area, Geom. Dedicata 3 (1974), 77-97. MR 48 #12313. [219] C. M. Petty: Ellipsoids, In: Convexity and its Applications (Eds. P. M. Gruber and J. M. Wills), Birkh~iuser, Basel, 1983, pp. 264-276. MR 86a:52019. [220] C. M. Petty, J. M. Crotty: Characterizations of spherical neighbourhoods, Canad. J. Math. 22 (1970), 431-435. MR 41 #2538. [221] B. B. Phadke: Equidistant loci and the Minkowskian geometries, Canad. J. Math. 24 (1972), 312-327. MR 45 #5881.

The Geometry of Minkowski Spaces - A Survey. Part II

141

[222] B. B. Phadke: Conditions for a plane projective metric to be a norm, Bull. Austral. Math. Soc. 9 (1973), 49-54. MR 48 #1053. [223] B. B. Phadke: Flatness of bisectors and the symmetry of distance, J. Geom. 4 (1974), 35-51. MR 51 #11390. [224] B. B. Phadke: A triangular world with hexagonal circles, Geom. Dedicata 3 (1974/1975), 511-520. MR 51 #4061. [225] B. B. Phadke: The theorem of Desargues in planes with analogues to Euclidean angular bisectors, Math. Scand. 39 (1976), 191-194. MR 56 #3752. [226] R. R. Phelps: A representation theorem for bounded convex sets, Proc. Amer. Math. Soc. 11 (1960), 976-983. MR 23 #A501. [227] K. F. Prisakaru, P. S. Soltan: Partition of a planar domain into d-convex parts and its application (in Russian), Dokl. Akad. Nauk SSSR 262 (1982), 271-273. Transl. Soviet Math. Dokl. 25 (1982), 53-55. MR 84i:52006. [228] H. l~demacher, O. Toeplitz: The Enjoyment of Mathematics, Princeton Univ. Press, Princeton, N.J., 1957. (Tansl. of "Von Zahlen und Figuren", Springer, Berlin 1933). MR 18,454b. [229] A. M. Raigorodskii: Borsuk's problem and the chromatic numbers of some metric spaces (in Russian), Uspekhi Mat. Nauk 56 (2001), no. 1(337), 107-146. Transl. Russian Math. Surveys 56 (2001), 103-139. MR 2002m:54033. [230] C. Reda: Straight lines in metric spaces, Demonstratio Math. 6 (1973), 809-819. MR 52 #4244. [231] H. Reimann: Eine Absehiitzung hit den Fliieheninhalt yon Eiehbereichen Banaeh-Minkowskiseher Ebenen, Wiss. Z. P~dagog. Hochsch. Effurt/Miihlhansen Math.-Natur. Reihe 23 (1987), 124-132. MR 89d:52027. [232] F. Reuleaux: Lehrbuch der Kinematik, Teil I. Vieweg, Braunschweig, 1875 (translated: 1876; reprinted: Dover, New York, 1963). [233] F. Rhodes: A triangular duality for two metrics for the co-ordinate plane, Math. Gaz. 54 (1970), 19-23. [234] W. Rinow: Die innere Geometric der Metrischen R?iume, Grundlehren der Mathematischen Wissenschaften in Einzeldarstellungen, Vol. 105, Springer-Verlag, Berlin 1961. MR 23 #A1290 [235] A. Rodriguez Palacios: Infinite-dimensional sets of constant width and their applications, Extracta Math. 5 (1990), 41-52. [236] C.A. Rogers, G. C. Shephard, The difference body of a convex body, Arch. Math. 8 (1957), 220-233. MR 19,1073f. [237] G. T. Sallee: The maximal set of constant width in a lattice, Pacific J. Math. 28 (1969), 669-674. MR 39 #2069. [238] G. T. Sallee: Maximal areas o/Reuleauz polygons, Canad. Math. Bull. 13 (1970), 175-179. MR 42 #2368. [239] G. T. Sallee: Reuleauz polytopes, Mathematika 17 (1970), 315-323. MR 45 #5872. [240] G. T. Sallee: Sets of constant width, the spherical intersection property and circumscribed balls, Bull. Austral. Math. Soe. 33 (1986), 369-371. MR 87g:52010. [241] G. T. Sallee: Pairs of sets of constant relative width, J. Geom. 29 (1987), 1-11. MR 88e:52005. [242] G. T. Sallee: Preassigning the boundary of diametrically complete sets, Monatsh. Math. 105 (1988), 217-227. MR 89d:52010. [243] F. Santos: On Delaunay oriented matroids ]or convex distance functions, Discrete Comput. Geom. 16 (1996), 197-210. MR 97e:52019. [244] R. Schneider: Convex Bodies: The Brunn-Minkowski Theory, Encyclopedia of Mathematics and its Applications 44, Cambridge University Press, Cambridge 1993. MR 94d:52007.

142

H. Martini and K. J. Swanepoel

[245] J. T. Schwarz, M. Sharir: Algorithmic motion planning in robotics, Handbook of Theoretical Computer Science, Vol. A, Ed. J. van Leeuwen, Elsevier, Amsterdam 1990, pp. 391-430. MR 92d:68001. [246] P. R. Scott: Sets o/constant width and inequalities, Quart. J. Math. Oxford (2) 32 (1981), 345-348. MR 82k:52013. [247] A. V. Shaldenko: Some characteristic properties of the ellipsoid (in Russian), Sibirsk Mat. Zh. 21 (1980), 232-234, 240. MR 81h:53006. [248] M. Sharir: Almost tight upper bounds for lower envelopes in higher dimensions, Discrete Comput. Geom. 12 (1994), 327-345. MR 95k:52024. [249] G. C. Shephard: Reducible convex sets. Mathematika 13 (1966), 49-50. MR 33 #6504. [250] I. Singer, Abstract convex analysis, John Wiley & Sons, Inc., New York, 1997. MR 98k:49002 [251] S. Skyum: A sweepline algorithm for generalized Delaunay triangulations, Tech. Report DAIMI PB-373, CS Dept., Aarhus University, 1991. [252] M. F. Smiley: A comparison of algebraic, metric, and lattice betweenness, Bull. Amer. Math. Soc. 49 (1943), 246-252. MR 4,248b [253] E. Soetens: Convexity in Busemann spaces, Bull. Soc. Math. Belg. 19 (1967), 194-213. MR 37 #3493 [254] P. S. Soltan: Helly's theorem for d-convex sets (in Russian), Dokl. Akad. Nauk SSSR 205 (1972), 537-539. Transl. Soviet Math. Dokl. 13 (1972), 975-978. MR 46 #8047. [255] P. S, Soltan: Extremal problems on convex sets (in Russian), Izdat. Shtiinca, Kishinev, 1976. MR 58 #18164. [256] P. S. Soltan, K. F. Prisakaru: The Steiner problem on graphs. L (in Russian), Dokl. Akad. Nank SSSR 198 (1971), 46-49. Transl. Soviet Math. Dold. 12 (1971), 734-738. MR 46 #96. [257] P. S. Soltan, V. P. Soltan: A criterion for the normability in a class of linear metric spaces (in Russian), Mat. Issled. 10 (1975), 275-279. MR 53 #1428. [258] V. P. Soltan: The diameter of d-convex hulls (in Russian), Mat. Issled. 9 (1974), 96-109. MR 52 #9082. [259] V. P. Soltan: A certain property of a d-convex ball (in Russian), Mat. Issled. 10 (1975), 149-156. MR 53 #1409. [260] V. P. Soltan: A class of finite-dimensional normed spaces (in Russian), Mat. Issled. 42 (1976), 204-215. MR 58 #30075. [261] V. P. Soltan: A theorem on full sets (in Russian), Dokl. Akad. Nauk SSSR 234 (1977), 320-322. Transl. Soviet Math. Dokl. 18 (1977), 680-682. MR 58 #2607. [262] V. P. Soltan: The unit ball of the ~*-space I~~ (in Russian), Mat. Issled. 45 (1977), 169-178. MR 58 #24021. [263] V. P. Soltan: Bodies of constant width in finite-dimensional normed spaces (in Russian), Mat. Zametki 25 (1979), 283-291. Transl. Math. Notes 25 (1979), 147-150. MR 80d:52004. [264] V. P. Soltan: Star-shaped sets in the axiomatic theory of convexity (in Russian), Soob~e. Akad. Nank Gruzin. SSR 96 (1979), 45--48. MR 81k:52017. [265] V. P. Soltan: A theorem on d-starlike sets (in Russian), Mat. Issled. 53 (1979), 122-125. MR 81k:52018. [266] V. P. Soltan: Some properties of d-convex functions, I (in Russian), Izv. Akad. Nauk Moldav. SSR, Ser. Fiz.-Teldan. Mat. Nank (1980), 27-31. MR 83a:52004a. [267] V. P. Soltan: Metrically extremal and boundary points (in Russian). In: Modern geometry, Leningrad Univ., 1980, pp. 64-73. MR 82i:52003. [268] V. P. Soltan: Metrically extremal and boundary points of convex sets in a normed space (in Russian), Mat. Issled. 54 (1980), 155-163. MR 81k:46016.

The Geometry of Minkowski Spaces - A Survey. Part II

143

[269] V. P. Soltan: Some properties of d-convex f~nctions, H (in Russian), Ivz. Akad. Nauk Moldav. SSR, Set. Fiz.-Tekhn. Mat. Nauk (1981), 21-26. MR 83a:52004b. [270] V. P. Soltan: Introduction to the axiomatic theory of convexity (Russian, with English and French Summaries). Shtiinca, Kishinev, 1984. MR 87h:52004. [271] V. P. Soltan: Partition of a plane set into a finite number of d-convex parts (in Russian), Kibernetika (Kiev) 6 1984, 70-74. MR 87e:52008. [272] V. P. Soltan: Metric convexity in graphs, Studia Univ. Babe~-Bolyai Math., 36 (1991), 3-43. MR 95k:52002. [273] V. P. Soltan, P. S. Soltan: d-convex functions (in Russian), Dold. Akad. Nank SSSR 249 (1979), 555-558. Transl. Soviet Math. Dokl. 20 (1979), 1323-1326. MR 80j:52001. [274] V. P. Soltan, O. I. Topal~: Star sets in the Cartesian product of metric spaces (in Russian), In: Contemporary Questions of Applied Mathematics and Programming (in Russian), pp. 128-135, Shtiinca, Kishinev, 1979. MR 81k:52016. [275] V. A. Sorokin: Classes of convex sets as generalized metric spaces (in Russian), Mat. Zametki 4 (1968), 45-52. MR 38 #2670. [276] K. O. Sowell: Taxicab geometry - a new slant, Math. Mag. 62 (1989), 238-248. MR 91a:51003. [277] S. stirrer: Characterization of contour elements that generate abstract Voronoi diagrams, Comput. Geom. 7 (1997), 245-262. MR 98a:52024. [278] W. J. Stiles: On inversions in normed linear spaces, Proc. Amer. Math. Soc. 20 (1969), 505-508. MR 38 #3718. [279] D. Stoyan, W. S. Kendall, J. Mecke: Stochastic geometry and its applications, Wiley, Chichester, 1987. MR 88j:60034a. [280] W. Sfiss: Uber affine Geometric: Eifllichen konstanter Affinbreite, Math. Ann. 96 (1927), 251-260. [281] Gy. Sz6kefalvi-Nagy: Zentralsymmetrisierung konvexer KSrper, Publ. Math. Debrecen 1 (1949), 29-32. MR 11,386h. [282] B. Tagansky: The complexity of substructures in arrangements of surfaces, Ph.D. Thesis, Tel Aviv University, Tel Aviv 1996. [283] A. C. Thompson: MR 97f:52001.

Minkowski Geometry. Cambridge University Press, Cambridge 1996.

[284] O. I. Topal&: Local d-convexity and d-starlike sets (in Russian), Mat. Issled. 53 (1979), 126-135. MR 81d:52004. [285] O.I. Topal~.: Extremal points and d-star-shaped sets (in Russian), In: General Algebra and Discrete Geometry, pp. 108-110, Shtiinca, Kishinev, 1980. MR 83i:52007. [286] 0. I. Topal&: The intersection and union of star-shaped sets in a metric space (in Russian), In: General Algebra and Discrete Geometry, pp. 111-117, Shtiinca, Kishinev, 1980. MR 83i:52008. [287] 0. I. Topal~.: Finite unions of d-convex, d-starshaped and Ln-starshaped sets (in Russian), Investigations in Numerical Methods and Theoretical Cybernetics, pp. 103-110, Shtiinca, Kishinev, 1985. MR 87g:52017. [288] O. I. Topal~: Krasnosel'skii's theorem for points of local d-nonconvexity (in Russian), Proc. Sympos. Geom. (Cluj-Napoca and Tirgu Mure~, 1992), 183-195, Preprint 93-2, Babe~-Bolyai Univ., Cluj-Napoca, 1993. MR 96e:52012. [289] F. A. Toranzos: Immersion of convex metric spaces in E n (in Spanish), Math. Notae 21 (19661967), 29-53. MR 39 #870. [290] F. A. Toranzos: Metric bctwcenness in normed linear spaces, Colloq. Math. 23 (1971), 99-102. MR 46 #4171.

144

H. Martini and K. J. Swanepoel

[291] J. E. Valentine: Some implications of Euclid's Proposition 7, Math. Japonica 28 (1983), 421-425. MR 84m:46023. [292] G. Valette: On metric segments in finite-dimensional normed spaces, Bull. Soc. Math. Belg. S~r. A 42 (1990), 761-766. MR 96a:52004. [293] M. L. J. van de Vel, Theory of convex structures, North-Holland Mathematical Library, 50. NorthHolland Publishing Co., Amsterdam, 1993. MR 95a:52002 [294] E. R. Verheul: Multimedians in metric and normed spaces, CWI Tract 91, Stichting Mathematisch Centrum, Centrum voor Wiskunde en Informatica, Amsterdam 1993, 136 pp. MR 94i:54062. [295] P. Vincensini: Corps convexes, Series lingaires. Domaines veetoriels. Mem. des Sciences Math., fasc. XCIV, Paris 1938. Zbl. 21,356. [296] G. Voronoi: Nouvelles applications des param~tres continus ?~la th~orie des formes quadratiques, Premier M~moire: Sur quelques propridtds des formes quadratiques positives parfaites. J. Reine Angew. Math. 183 (1907), 97-178. [297] G. Voronoi: Nouvelles applications des param~tres continus d la thgorie des formes quadratiques, Deuxi~me M6moire: Recherches sur les parall6lo~dres primitifs. J. Reine Angew. Math. 134 (1908), 198-287. [298] S. Vredica: A note on sets of constant width, Publ. Inst. Math. (Beograd) (N.S.) 29 (1981), 289291. MR 83g:52006. [299] A. Weifller: General bisectors and their applications to planar location theory. Dissertation, Universiti~t Kaiserslantern, 1999. [300] B. Wernicke: Tciangles and Reuleauz triangles in Banach-Minkowski planes, In: Intuitive Geometry (Szeged, 1991), Colloq. Math. Soc. JLnos Bolyai 63, North-Holland, Amsterdam, 1994, pp. 505-511. MR 96m:51006. [301] P. Widmayer, Y. F Wu, C. K. Wong: On some distance problems in fixed orientations, SIAM J. Comput. 16 (1987), 728-746. MR 88g:68105. [302] A. C. Woods: A characterization of ellipsoids, Duke Math. J. 36 (1969), 1-6. MR 38 #6460. [303] K. WoSniak: Properties of 9eneralized segments and lines in normed spaces (in Polish), Zeszyty Nauk. Wyi. Szkoty Ped. w Opolu Mat. 24 (1986), 81-91. MR 88k:51036. [304] D. Yost: Irreducible convex sets, Mathematika 38 (1991), 134-155. MR 92h:52006.

Received: 12.05. 2003