On farthest Voronoi cells M. A. Goberna 1 Dep. of Mathematics, Universidad de Alicante, San Vicente del Raspeig, 03080, Spain; email: mgoberna@ua.es J. E. Martnez-Legaz Dep. of Economics and Economic History, Universitat Autnoma de Barcelona, and BGSMath, Spain; email: JuanEnrique.Martinez.Legaz@uab.cat M. I. Todorov Dep. of Physics and Mathematics, UDLAP, Puebla, MX. On leave from IMI-BAS, Sofia, Bulgaria;. email: maxim.todorov@udlap.mx Abstract Given an arbitrary set T in the Euclidean space Rn , whose elements are called sites, and a particular site s, the farthest Voronoi cell of s, denoted by FT (s) , consists of all points which are farther from s than from any other site. In this paper we study farthest Voronoi cells and diagrams corresponding to arbitrary (possibly infinite) sets. More in particular, we characterize, for a given arbitrary set T, those s ∈ T such that FT (s) is nonempty and study the geometrical properties of FT (s) in that case. We also characterize those sets T whose farthest Voronoi diagrams are tesselations of the Euclidean space, and those sets that can be written as FT (s) for some T ⊂ Rn and some s ∈ T. Key words: Farthest Voronoi cells. Linear inequality systems. Boundedly exposed points. Mathematics Subject Classification 2010 : 15A39, 51M20, 52C22. 1 Introduction Let T ⊂ Rn , with n ≥ 1, be a set whose elements are called Voronoi sites. The Voronoi cell of s ∈ T, denoted by VT (s) , consists of all points closer to 1 Corresponding author. Preprint submitted to Elsevier 2 September 2019 s than to any other site, i.e., VT (s) := {x ∈ Rn : d (x, s) ≤ d (x, t) , ∀t ∈ T } , where d denotes the Euclidean distance on Rn . Analogously, the farthest Voronoi cell of s, denoted by FT (s) , is formed by those points which are farther from s than from any other site, i.e., FT (s) := {x ∈ Rn : d (x, s) ≥ d (x, t) , ∀t ∈ T } . The families of sets {VT (s) , s ∈ T } and {FT (s) , s ∈ T } are called Voronoi diagram and farthest Voronoi diagram of T, respectively. If T is a singleton, both diagrams trivially coincide with {Rn } . So, we can assume that T is not a singleton. According to Michael Shamos’ memories [21], the nearest Voronoi diagrams were rediscovered in 1974 by his collaborator Dan Hoey, a Yale undergradu- ate in Computer Science, who called them proximal polygons. Shamos found that they had been already discovered by Voronoi in 1908, and rediscovered independently many times since, so they decided to change their name to the above one. They also introduced the concept of farthest Voronoi diagram, obtaining algorithms for the construction of both types of diagrams that ap- peared in 1978, at Shamos Ph.D. Thesis [20], which was completed the next year with the proof of Shamos’ conjecture that there is no real difference, from the computational point of view, between near and far. Shamos Ph.D. Thesis provided the starting stuff for the first published textbook on computational geometry [18]. There exists a vast literature on Voronoi cells and diagrams of finite sets due to their many applications in computational geometry, operations research, data compression, economics, marketing, etc. Farthest Voronoi cells and diagrams are not so popular, but they also have applications to computational geometry (see, e.g., [8] and [18]) and operations research, where they have been used to solve the so-called central path problem [27], to compute the min-power centre of a finite set of nodes in the Euclidean plane when cost is a quadratic function [4], or to solve the weighted one-center location problem (consisting in finding the minimum covering ball of a finite set of points in Rn , with a positive weight corresponding to each point) [9]. Both types of cells and diagrams have been extended in several directions, for instance, replacing the Euclidean distance with another distance or pseudo distance (as the so-called travel time distance in [3]), and replacing in the definition of cells the given point site s with segments (as in [1] and [2]) or with polygons (as in [6] and [7]), in which case the cells are no longer connected sets. Another extension can be obtained by relaxing the finiteness assumption 2 on the set of sites T. This was already done by Delauney in the 1930s, who considered Voronoi cells and diagrams of infinite discrete sets (i.e., sets without accumulation points) in a work oriented towards crystallography [10]. More recently, [25] studied Voronoi cells of discrete sets by exploiting the linear representation of VT (s) , while [14] and [15] extended this study to Voronoi cells of arbitrary infinite sets. To the best of our knowledge, no previous work has considered farthest Voronoi cells and diagrams of infinite sets; this is the objective of the present paper, where we also use the linear algebra approach through the linear representation of FT (s). Our study reveals that the main difference between Voronoi cells and farthest Voronoi cells has to do with their nonemptiness and boundedness. In fact, VT (s) is always nonempty and may be bounded or not, while FT (s) is almost always empty (e.g., whenever T is unbounded or when it is bounded but s is not an extreme point of conv T ) and, when it is nonempty, it is necessarily unbounded. This is the reason why the paper is mostly focused on the conditions guaranteeing that FT (s) 6= ∅. Since any discrete infinite set is unbounded, in contrast with [15] (on Voronoi cells of infinite sets), we do not consider in this paper farthest Voronoi cells of discrete sets. The paper is organized as follows. Section 2 introduces the notation to be used along the paper and provides immediate consequences of three different representations of FT (s) . Section 3 analyzes the relationships between FT (s) and the normal cone to the convex hull of T at s, from which we obtain useful geometric information on the farthest Voronoi cells. Section 4 characterizes, for a given set T, those sites s whose corresponding farthest Voronoi cells FT (s) are nonempty and those sets T whose farthest Voronoi diagram is a tesselation of Rn . Finally, Section 5 characterizes those subsets of Rn that are the farthest Voronoi cell FT (s) for some compact convex set T and some s ∈ T, providing the farthest counterpart for the inverse problem solved in [14] for Voronoi cells. 2 Basic results We first introduce the notation to be used along the paper. The sets of non- negative and nonpositive real numbers are denoted by R+ and R− , respec- tively. The zero vector in Rn is denoted by 0n and the closed ball centered at x ∈ Rn and radius r ∈ [0, +∞] by B (x, r) (notice that we allow r to be 0, in which case the ”closed ball” B (x, r) obviously degenerates to the singleton of its center, or +∞, in which case B (x, r) = Rn ). Given X ⊂ Rn , we denote by conv X, cone X, aff X, int X, and cl X the convex hull of X, the convex conical hull of X, the affine hull of X, the interior of X, and the closure of X, respectively. Given a nonempty convex set X ⊂ Rn , its dimension and its 3 recession cone are denoted by dim X and 0+ X, respectively. The normal cone to a convex set X ⊂ Rn at x ∈ X is NX (x) := {y ∈ Rn : hx − x, yi ≤ 0, ∀x ∈ X} . ∗ The support function of a nonempty set X ⊂ Rn is δX : Rn → R∪ {+∞}, de- ∗ ∗ fined by δX (x) := supy∈X hy, xi . It is known that δX is a lower semicontinuous ∗ positively homogeneous convex function. Moreover, δX is finite-valued (and so n continuous on R ) whenever X is bounded. We now express the farthest Voronoi cells in tree different ways from which we obtain some immediate consequences. For each point s of a given set T ⊂ Rn , called the set of sites, we can express the farthest Voronoi cell as FT (s) = {x ∈ Rn : kx − sk ≥ kx − tk , ∀t ∈ T } . (1) Equivalently, one has FT (s) = {x ∈ Rn : T ⊂ B (x, ks − xk)} (2) and, observing that the inequality in (1) can be replaced by kx − sk2 ≥ kx − tk2 , simple algebraic calculus yields n o FT (s) = x ∈ Rn : 2 ht − s, xi ≥ ktk2 − ksk2 , ∀t ∈ T . (3) Our first results are direct consequences of (1). Proposition 1 If T, T 0 ⊂ Rn and s ∈ T ∩ T 0 , one has FT (s) ∩ FT 0 (s) = FT ∪T 0 (s). Corollary 2 If T ⊂ T 0 ⊂ Rn and s ∈ T, then one has FT 0 (s) ⊂ FT (s). Proposition 3 For T ⊂ Rn and s ∈ T, one has FT (s) = s + FT −s (0n ). Proof. Denoting y := x − s and u := t − s, FT (s) = {y + s ∈ Rn : kyk ≥ ky − uk , ∀u + s ∈ T } = s + FT −s (0n ).  From (2), one easily obtains the following results. Proposition 4 For T ⊂ Rn and s ∈ T, one has: (i) If FT (s) 6= ∅ then T is bounded. (ii) FT (s) = Fcl conv T (s). 4 Proof. (i) Picking an arbitrary x ∈ FT (s), (2) shows that T is contained in a ball centered at x. (ii) It follows from (2), as T ⊂ B (x, ks − xk) ⇐⇒ cl conv T ⊂ B (x, ks − xk) .  Definition [ 5 A nonempty set T ⊂ Rn is said to have the covering property if FT (s) = Rn . s∈T Proposition 6 For any nonempty set T ⊂ Rn , one has: (i) If T is compact, then it has the covering property. (ii) If T has the covering property, then it is bounded. Proof. (i) Let x ∈ Rn . Since the maximum distance from x to the points of T is attained at some s, this is a farthest site to x in T and, so, x ∈ FT (s) . Statement (ii) follows from Proposition 4(i).  As a consequence of Proposition 11(ii) below, all farthest Voronoi cells of open balls are empty. Thus, the compactness assumption in Proposition 6 cannot be replaced by the weaker one that T is bounded. Proposition 7 If T ⊂ T 0 ⊂ Rn , with T and T 0 being compact, then the following equivalence holds: FT (s) = FT 0 (s) ∀s ∈ T ⇔ T 0 ⊂ conv T. Proof. To prove [⇒], let B (x, r) be a closed ball containing T. By the covering property, there exists s ∈ T such that x ∈ FT (s). Clearly, ks − xk ≤ r and, by the equality FT (s) = FT 0 (s), we have x ∈ FT 0 (s). We thus obtain T 0 ⊂ B (x, ks − xk) ⊂ B (x, r) , which shows that T 0 is contained in the intersection of all those closed balls that contain T. According to the Mazur intersection property ([16], [17]) that intersection coincides with conv T. The converse implication is an immediate consequence of Proposition 4(ii) combined with Corollary 2.  We now consider the partial ordering 4 defined on the class of compact subsets of Rn as follows: T 4 T 0 ⇔ T ⊂ T 0 and FT (s) = FT 0 (s) ∀s ∈ T. 5 Corollary 8 If T ⊂ Rn is compact, then conv T is the largest compact set T 0 , for 4, such that T 4 T 0 . Proof. It immediately follows from Propositions 4(ii) and 7.  Corollary 9 A compact set T ⊂ Rn is a maximal element for 4 if and only if it is convex. Proof. It is an easy consequence of Corollary 8.  The next consequence of (3) implies that one can replace the covering property of T in Proposition 6 by the stronger condition that the farthest Voronoi dia- gram of T is a tesselation of Rn , that is, the union of the family {FT (s) , s ∈ T } is the whole of Rn and its corresponding family of topological interiors, {int FT (s) , s ∈ T } , is formed by pairwise disjoint sets. Proposition 10 For T ⊂ Rn and s1 , s2 ∈ T such that s1 6= s2 , one has int FT (s1 ) ∩ int FT (s2 ) = ∅. Proof. Let x ∈ FT (s1 )∩FT (s2 ) . By (3), one has 2 hs2 − s1 , xi ≥ ks2 k2 −ks1 k2 and n 2 hs1 − s2 , xi ≥ ks1 k2 − ks2 k2 , so that o x belongs to the hyperplane H := n 2 2 x ∈ R : 2 hs2 − s1 , xi = ks2 k − ks1 k . Thus int FT (s1 ) ∩ int FT (s2 ) ⊂ FT (s1 ) ∩ FT (s2 ) ⊂ H, which implies int FT (s1 ) ∩ int FT (s2 ) = ∅.  We also get a geometric interpretation of FT (s) from its linear representation (3). Given t ∈ T  {s} , the hyperplane of equation 2 ht − s, xi = ktk2 − ksk2 is orthogonal to the segment [s, t] at its mid point t+s 2 , and determines two halfspaces, one containing s, n o Ht∈ (s) := x ∈ Rn : 2 ht − s, xi ≤ ktk2 − ksk2 , and another one which does not contain it, n o Ht∈/ (s) := x ∈ Rn : 2 ht − s, xi ≥ ktk2 − ksk2 . Then, Ht∈/ (s), \ FT (s) = (4) t∈T {s} while the Voronoi cell of s is VT (s) := {x ∈ Rn : kx − sk ≤ kx − tk , ∀ t ∈ T } = Ht∈ (s) 3 s. \ t∈T {s} Obviously, VT (s) 6= ∅ for all s ∈ T while FT (s) may be empty. 6 Proposition 11 For T ⊂ Rn and s ∈ T, one has FT (s) 6= ∅ if and only if       0n    2 (t − s)     ∈ / cl cone   ,t  ∈T . 2  ktk − ksk 2 1    Proof. It follows from the generalized Gale’s Theorem [13, Corollary 3.1.1] applied to the linear system in (3).  Example 12 Let T = [−1, 1]2 and let T 0 := {−1, 1}2 (the set of extreme points of T ). According to Proposition 4(ii), FT (s) = FT 0 (s) for all s ∈ T 0 . Then, by (4), applied to T 0 , ∈/ ∈/ ∈/ FT (1, 1) = H(−1,1) (1, 1) ∩ H(1,−1) (1, 1) ∩ H(−1,−1) (1, 1) = {x ∈ R2 : x1 ≤ 0, x2 ≤ 0, x1 + x2 ≤ 0} = R2− . Analogously, FT (−1, 1) = R+ × R− , FT (−1, −1) = R2+ , and FT (1, −1) = R− × R+ , while FT (s) = ∅ for all s ∈ T T 0 . So, the farthest Voronoi diagram of T is formed by the four quadrants of the plane (a tesselation of R2 ) together with an infinite number of copies of the empty set. Example 13 Let T = B (02 , 1) . One can easily see that n FT (s) = ∅ for all o s ∈ / such that ksk < 1. Let s ∈ T be such that ksk = 1. Then, Ht (s) : t ∈ T  {s} is the family of all halfplanes not containing s whose boundary contains 0n . So, FT (s) = {−λs : λ ≥ 0} (a ray, that is, a closed halfline emanating from 02 ) and the farthest Voronoi diagram constitutes a tesselation of R2 . 3 Farthest Voronoi cells and normal cones We will use the following result (also valid for locally convex spaces) to get a fourth characterization of the elements of FT (s). Lemma 14 (cf. [22, Theorem 3.1]) Let f be a continuous convex function on Rn and T be a bounded subset of Rn satisfying inf f (Rn ) < sup f (T ). For an element t0 ∈ T one has f (t0 ) = sup f (T ) if and only if there exists a linear function Φ0 6= 0 such that Φ0 (t0 ) = sup {Φ0 (z) : z ∈ Rn , f (z) ≤ sup f (T )} . 7 Proposition 15 For T ⊂ Rn , s ∈ T and x ∈ Rn , the following equivalence holds: x ∈ FT (s) ⇔ ∃ y ∈ Rn such that kyk = 1 and hs, yi = δB∗ (x,sup ) (y) . t∈T kt−xk (5) Proof. If T is unbounded, then equivalence (5) holds vacuously true in view of Proposition 4(i) and the equality supt∈T kt − xk = +∞. We will assume that T is not a singleton, since otherwise it is obvious that equivalence (5) holds true. Let x ∈ Rn and f := k· − xk . If x ∈ FT (s), recalling (1), max f (T ) = f (s) = kx − sk > 0 = inf f (Rn ). Then, by Lemma 14, with t0 = s, and (2), there exists y ∈ Rn such that kyk = 1 and ∗ hy, si = sup {hy, zi : z ∈ Rn , kz − xk ≤ max f (T )} = δB(x,max f (T )) (y) . The argument is reversible.  The following results describe the relationship between FT (s) and Nconv T (s). Proposition 16 For T ⊂ Rn and s ∈ T, one has FT (s) ⊂ s − Nconv T (s). (6) Proof. If T is unbounded, then FT (s) = ∅ by Proposition 4(i). We can assume that FT (s) 6= ∅. Let x ∈ FT (s), and take y as in (5). We have     ks − xk = max kt − xk = x + max kt − xk y, y − hx, yi t∈T t∈T ∗ ≤ δB(x,max t∈T kt−xk) (y) − hx, yi = hs − x, yi ≤ ks − xk , hence ∗ hs − x, yi = δB(x,maxt∈T kt−xk) (y) − hx, yi = ks − xk , which implies that s − x = ks − xk y. Therefore, for t ∈ conv T, in view of (2) and (5) we have ht − s, x − si = − kx − sk ht − s, yi   ∗ ≥ − kx − sk δB(x,max t∈T kt−xk) (y) − hs, yi = 0. This implies that x − s ∈ −Nconv T (s), whereby x ∈ s − Nconv T (s).  The inclusions (6) are also strict in Example 13. 8 Proposition 17 If T ⊂ Rn and s ∈ T are such that FT (s) 6= ∅, then 0+ FT (s) = −Nconv T (s) (7) and dim FT (s) = dim Nconv T (s). (8) Proof. The inclusion [⊂] in (7) is an immediate consequence of (6). To prove the opposite inclusion, let d ∈ Nconv T (s) and x ∈ FT (s). For every t ∈ T, one has kx − d − tk2 = kx − tk2 + kdk2 − 2 hx − t, di ≤ kx − sk2 + kdk2 − 2 hx − t, di = kx − d − sk2 + 2 ht − s, di ≤ kx − d − sk2 , which shows that x − d ∈ FT (s); hence −d ∈ 0+ FT (s), as we wanted to prove. In order to prove (8), pick x ∈ FT (s). By (7) and (6), we have x − Nconv T (s) ⊂ FT (s) − Nconv T (s) = FT (s) + 0+ FT (s) = FT (s) ⊂ s − Nconv T (s), from which the equation (8) readily follows.  The next concept helps to understand the nature of the farthest Voronoi cells. Definition 18 (cf. [26]) Let X ⊂ Rn and x ∈ Rn . One says that X is cora- diant with respect to x if its complement is starshaped with respect to x; in other words, if whenever y ∈ X and λ ≥ 1 then (1 − λ) x + λy ∈ X. It is very easy to see that, for a closed convex set X and x ∈ Rn \ X, the following equivalence holds true [26, Proposition 2.5, (a) ⇔ (b)]: X is coradiant with respect to x ⇔ X − x ⊂ 0+ X. (9) When x := 0n , one simply says that X is coradiant. The following equivalence is immediate too: X is coradiant with respect to x ⇔ X − x is coradiant. (10) Since FT −s (0n ) ⊂ −Nconv T (s) = 0+ FT −s (0n ), FT −s (0n ) and −Nconv T (s) are coradiant. From Propositions 16 and 17 we next obtain inner and outer approximations to Nconv T (s) in terms of FT (s). The outer approximation involves the concept 9 of outer kernel of a set X ⊂ Rn (cf. [26, Definition 3.2]), that is, the set oker X := {x ∈ Rn : x + t (y − x) ∈ / X, ∀y ∈ Rn \ X, ∀t ∈ (0, 1]} . Observe that, defining the kernel of a set Y ⊂ Rn as ker Y := {y ∈ Rn : y + t(x − y) ∈ Y, ∀x ∈ Y, ∀t ∈ (0, 1]} , oker X turns out to be the kernel of its complement, i.e., oker X = ker (Rn \ X) . From the definition of outer kernel, oker X = {x ∈ Rn : x + λ (z − x) ∈ X, ∀z ∈ X, ∀λ ≥ 1} , in other words, for every x ∈ Rn \ X one has x ∈ oker X ⇔ X is coradiant with respect to x. (11) Theorem 19 (Farthest Voronoi cells and normal cones) For T ⊂ Rn and s ∈ T, one has s − FT (s) ⊂ Nconv T (s) ⊂ oker FT (s) − s. (12) Proof. If T is unbounded, by Proposition 4(i) the inclusions in (12) read ∅ ⊂ Nconv T (s) ⊂ Rn . If it is a singleton, then (12) reads Rn ⊂ Rn ⊂ Rn . We can thus assume that T is bounded and different from {s} . Since the empty set is trivially coradiant with respect to every point, we assume that FT (s) 6= ∅. Let x ∈ s + Nconv T (s). Since s is the closest point to s in conv T and T is not a singleton, we have x ∈ / FT (s). On the other hand, by Propositions 4(i), 16 and 17, we have FT (s) − x ⊂ FT (s) − s − Nconv T (s) ⊂ −Nconv T (s) − Nconv T (s) = −Nconv T (s) = 0+ FT (s). Hence, according to the equivalence (9), the set FT (s) is coradiant with respect to x, which, in view of (11), means that x ∈ oker FT (s). Thus, s + Nconv T (s) ⊂ oker FT (s). (13) Combining (6) and (13) one gets (12).  In Example 12, (12) becomes the following double strict inclusion: [1, +∞[2 R2+ [−1, +∞[2 . 10 4 Nonemptiness of the farthest Voronoi cells Definition 20 Let T ⊂ Rn be convex. A point s ∈ T is said to be a boundedly exposed point of T if there exists ε > 0 such that FT ∩B(s,ε) (s) 6= ∅. In Definition 20 we borrow the term ”boundedly exposed” from Edelstein [11] because, as we will see below, in the case when T is bounded our notion coincides with the one introduced by this author with the same name in the context of metric spaces. Proposition 21 Every boundedly exposed point of a convex set T ⊂ Rn is an exposed point of T. Proof. Since the result is obvious when T is a singleton, we will assume that it is not. Let s be a boundedly exposed point of T and ε > 0 be such that FT ∩B(s,ε) (s) 6= ∅. Take y ∈ FT ∩B(s,ε) (s) . Since T is convex but not a singleton, T ∩ B (s, ε) is not a singleton either, which clearly implies that y 6= s. Consider the halfspace H + := {x ∈ Rn : hs − y, x − si ≥ 0} . We will prove that T ∩ H + = {s} . The inclusion [⊃] is obvious. To prove the opposite inclusion, let x ∈ T ∩H + and take λ ∈ ]0, 1] such that (1 − λ) s+λx ∈ B (s, ε) ; since (1 − λ) s + λx ∈ T ∩ B (s, ε) and y ∈ FT ∩B(s,ε) (s) , we have ky − sk2 ≥ ky − ((1 − λ) s + λx)k2 = ky − s + λ (s − x)k2 = ky − sk2 + 2λ hy − s, s − xi + λ2 ks − xk2 , which, as x ∈ H + , implies that x = s. We have thus proved the equality T ∩ H + = {s} , which shows that s is an exposed point of T.  The relevance of boundedly exposed points regarding farthest Voronoi cells stems from the following theorem. Theorem 22 (Nonemptiness of the farthest Voronoi cells) For T ⊂ Rn and s ∈ T, the following equivalence holds: FT (s) 6= ∅ ⇐⇒ T is bounded and s is a boundedly exposed point of cl conv T. Proof. The implication [=⇒] follows from Proposition 4(i) and the equalities F(cl conv T )∩B(x,r) (s) = Fcl conv T (s) = FT (s) (see Proposition 4(ii)), with r denoting a positive number large enough for the inclusion T ⊂ B (x, r) to hold. Conversely, assume that T is bounded and s is a boundedly exposed point of 11 cl conv T, and take ε such that F(cl conv T )∩B(x,ε) (s) 6= ∅. Pick x ∈ F(cl conv T )∩B(s,ε) (s) . We claim that the family of open sets {int (B (s + λ (x − s) , λ ks − xk))}λ>0 covers the set (cl conv T )\{s} , and a fortiori the set (cl conv T )\int (B (s, ε)) . Indeed, for y ∈ (cl conv T ) \ {s} and small enough t > 0 we have, by (2), (1 − t) s + ty ∈ (cl conv T ) ∩ B (s, ε) ⊂ B (x, ks − xk) , hence hy − s, x − si > 0. Then it is easy to check that ky − sk2 y ∈ int B (s + λ (x − s) , λ ks − xk) , ∀λ > , hy − s, x − si which proves the claim. Therefore, since (cl conv T ) \ int B (s, ε) is compact and the sets int B (s + λ (x − s) , λ ks − xk) depend increasingly (in the sense of inclusion) on λ, for some λ0 > 0 we have (cl conv T ) \ int B (s, ε) ⊂ int B (s + λ0 (x − s) , λ0 ks − xk) , which, in view of (2), implies that s + λ0 (x − s) ∈ Fcl conv T \int B(s,ε) (s) . (14) On the other hand, using Proposition 17 we obtain s − x ∈ NB(x,ks−xk) (s) ⊂ N(cl conv T )∩B(s,ε) (s) ⊂ −0+ F(cl conv T )∩B(s,ε) (s) ; hence s + λ0 (x − s) ∈ F(cl conv T )∩(B(s,ε)) (s) . (15) Finally, by (14), (15) and Propositions 1 and 4(ii), we get s + λ0 (x − s) ∈ F(cl conv T )\int B(s,ε) (s) ∩ F(cl conv T )∩(B(s,ε)) (s) = Fcl conv T (s) = FT (s), which shows that FT (s) 6= ∅.  As a first corollary of Theorem 22, we obtain that, for bounded sets, our notion of boundedly exposed point coincides with that of Edelstein [11]. Corollary 23 For any bounded set T ⊂ Rn and s ∈ T, the following equiva- lence holds: s is a boundedly exposed point of cl conv T m ∃x ∈ Rn such that T \ {s} ⊂ int B (x, ks − xk) . 12 Proof. The proof of [⇑] is immediate: from T \ {s} ⊂ int B (x, ks − xk) we easily deduce that cl conv T ⊂ B (x, ks − xk) , which, by (2) and Corol- lary 2, implies that x ∈ Fcl conv T (s) ⊂ F(cl conv T )∩B(s,1) (s) , thus showing that F(cl conv T )∩B(s,1) (s) 6= ∅ and hence that s is a boundedly exposed point of cl conv T. Conversely, if s is a boundedly exposed point of cl conv T then, by Theorem 22, we have FT (s) 6= ∅. Taking y ∈ FT (s) , from (2) we deduce that T ⊂ B (y, ks − yk) , which implies that T \ {s} ⊂ B (y, ks − yk) \ {s} ⊂ int B (x, ks − xk) for x := 2y − s.  The next corollary is the farthest Voronoi counterpart of the known fact that the Voronoi diagram of T is a tesselation of Rn if and only if T is closed [15, Proposition 1]. Corollary 24 The farthest Voronoi diagram of T is a tesselation of Rn if and only if T is bounded and contains all boundedly exposed points of cl conv T . Proof. Assume that the farthest Voronoi diagram of T is a tesselation of Rn . Then, T is bounded by Proposition 6(ii). We now prove that T contains all boundedly exposed points of cl conv T by contradiction. Let s be a bound- edly exposed point of cl conv T such that s ∈ / T. By Corollary 23, applied to cl conv T, there exists x ∈ Rn such that (cl conv T )  {s} ⊂ int B (x, kx − sk) . Let s0 ∈ T be such that x ∈ FT (s0 ) . Then kx − s0 k < kx − sk , as s0 ∈ (cl conv T )  {s} , while kx − sk ≤ kx − s0 k by (1), also applied [ to cl conv T, and Proposition 4(ii). This contradiction shows that x ∈ / FT (s0 ) and, so, s0 ∈T T does not enjoy the covering property. Conversely, if T is bounded, by Theorem 22, the nonempty elements of the family {FT (s) , s ∈ T } are those farthest Voronoi cells FT (s) such that s ∈ T is a boundedly exposed point of cl conv T, for which FT (s) = Fcl conv T (s) , again by Proposition 4(ii). Hence, the nonempty elements of the farthest Voronoi diagrams of T and cl conv T are the same, with cl conv T satisfying the covering property by Proposition 6(i). The proof is complete recalling that the interiors of different farthest Voronoi cells are disjoint (Proposition 10).  Corollary 25 Every compact convex set in Rn is the closed convex hull of its boundedly exposed points. Proof. This is an immediate consequence of Theorem 22 combined with a theorem due to Edelstein [12], according to which every closed and bounded subset T of a uniformly Banach space with the Mazur intersection property is the closed convex hull of its farthest points (i.e., points s such that FT (s) 6= ∅).  In Examples 12 and 13, where cl conv T = T, any extreme point s satisfies the 13 characterization of the boundedly exposed points in Corollary 23 by taking x = −s. The following example shows that an exposed point need not be boundedly exposed. Example 26 Consider the compact convex set n o T := (x, y) ∈ R2 : x4 ≤ y ≤ 1 . Clearly, the origin (0, 0) is an exposed point of T. To prove that it is not boundedly exposed, we will prove that FT (0, 0) = ∅; the conclusion will then follow from Theorem 22. Assume, to the contrary, that FT (0, 0) 6= ∅, and take √ (x, y) ∈ FT (0, 0). By (2), one has T ⊂ B (x, y) , x2 + y 2 . Hence, for every 2 t ∈ [−1, 1] , from (t, t4 ) ∈ T we deduce that (t − x)2 + (t4 − y) ≤ x2 + y 2 , that is, t2 − 2tx + t8 − 2t4 y ≤ 0. Dividing this inequality by |t| , with t 6= 0, and setting successively t → 0+ and t → 0− , one easily obtains that x = 0, and hence 1 + t6 − 2t2 y ≤ 0 for t ∈ [−1, 1] \ {0} , which, setting t → 0, yields an absurd conclusion. Therefore FT (0, 0) = ∅. The celebrated Straszewicz’s Theorem ([23], [19, Theorem 18.6]) asserts that the set of exposed points of a closed convex set T ⊂ Rn is dense in the set of extreme points of T. We next prove that this theorem remains true when exposed points are replaced by boundedly exposed points. Theorem 27 (Density of the boundedly exposed points) For any closed convex set T ⊂ Rn , the set of boundedly exposed points of T is dense in the set of extreme points of T. Proof. In view of Straszewicz’s Theorem, it will be enough to prove that the set of boundedly exposed points of T is dense in the set of exposed points of T. Let x be an exposed point of T. We assume, without loss of generality, that T is compact (we can replace, if necessary, T with the intersection of a closed ball centered at x, since the exposed points of that intersection that are close enough to x are necessarily exposed points of T, as one can easily see). Let ε > 0. We have to prove the existence of a boundedly exposed point of T in int B (x, ε) . Take a supporting hyperplane H of T such that T ∩ H = {x} , and let p be the corresponding unit exterior normal vector to T at x, i.e., p ∈ NT (x) and orthogonal to H. We now use an argument similar, though simpler, to one we have employed in the proof of Theorem 22. We claim that the family of open sets {int (B (x − λp, λ))}λ>0 covers the set T \ {x} , and hence T \ int B (x, ε) . Indeed, by the definition of p we have hp, y − xi < 0 for all y ∈ T \ {x} . Then it is easy to check that y ∈ int (B (x − λp, λ)) for ky−xk2 every λ > 2hp,y−xi , which proves the claim. Therefore, since T \ int B (x, ε) is compact and the sets int (B (x − λp, λ)) depend increasingly (in the sense of 14 inclusion) on λ, for some λ0 > 0 we have T \ int B (x, ε) ⊂ int (B (x − λ0 p, λ0 )) . (16) By Proposition 6(i), we have x−λ0 p ∈ FT (s) for some s ∈ T. Then kx − λ0 p − sk ≥ kx − λ0 p − xk = λ0 , hence s ∈/ int B (x − λ0 p, λ0 ) , which, by (16), implies that s ∈ int B (x, ε) . To finish the proof, we just have to apply Theorem 22, as it tells us that s is a boundedly exposed point of T.  5 Characterization of the farthest Voronoi cells We next aim at characterizing farthest Voronoi cells. In view of Proposition 3, one just needs to consider the case when s := 0n , in which case (3) reduces to ktk2 ( ) n FT (0n ) = x ∈ R : ht, xi ≥ , ∀t ∈ T \ {0n } . (17) 2 This representation shows that FT (0n ) is closed, convex and coradiant; more- over, 0n ∈/ FT (0n ) unless T = {0n } . In order to prove that these properties characterize the farthest Voronoi cells of 0n we need a known result that in- volves the concept of reverse polar of a set, which results of inverting the inequality hx, yi ≤ 1 in the definition of positive polar. Indeed, the reverse polar set X 0 of a nonempty set X ⊂ Rn is X 0 := {y ∈ Rn : hx, yi ≥ 1, ∀x ∈ X} . Lemma 28 (cf. [26, Proposition 2.5, (a) ⇔ (e)]) A set C ⊂ Rn is convex, closed, coradiant and does not contain 0n if and only if there exists a nonempty set U ⊂ Rn \ {0n } such that C = U 0. (18) Proof. The equivalence obviously holds if C = ∅ (take, e.g., U := {p, −p} , with p ∈ Rn \ {0n }), so we are going to assume that C 6= ∅. The ”only if” statement being trivial, we will only prove its converse. Since C is convex and closed, there exists Q ⊂ (Rn \ {0n }) × R such that C = {x ∈ Rn : ha, xi ≥ b, ∀ (a, b) ∈ Q} . Since C is coradiant, for every x ∈ Rn and (a, b) ∈ Q we have ha, xi ≥ 0, and hence there is no loss of generality in assuming that b ≥ 0. We can rewrite C as follows: C = {x ∈ Rn : ha, xi ≥ 1 ∀a ∈ A+ , and ha, xi ≥ 0 ∀a ∈ A0 } ; n o here A+ := 1b a : (a, b) ∈ Q, b > 0 and A0 := {a ∈ Rn : (a, 0) ∈ Q} . Since / C, we have A+ 6= ∅. Pick a ∈ A+ , and for each a ∈ A0 replace the 0n ∈ 15 inequality ha, xi ≥ 0 with the following equivalent infinite collection of in- equalities: ha + εa, xi ≥ ε, ∀ε > 0. n o 1 Thus, (18) holds with U := A+ ∪ ε a + a : a ∈ A0 , ε > 0 .  Theorem 29 (Characterization of the farthest Voronoi cells) For any nonempty set C Rn , one has C = FT (s) for some T ⊂ Rn containing s if and only if it is convex, closed, coradiant with respect to s and does not contain s. Proof. In view of Proposition 3 and (10), we may assume, without loss of generality, that s := 0n . Then, as we have already observed, the ”only if” statement is an immediate consequence n of (17). To o prove the converse, use the 2 representation (18) and define T := kuk2 u : u ∈ U ∪ {0n } . Since U 6= ∅, the set T is not a singleton. Using (17), it is easy to check that FT (0n ) = C.  Example 30 Let C := {(x, y) ∈ R2 : x > 0, xy ≥ 1} . This set is convex, closed, coradiant and does not contain the origin. From the representation n o C = (x, y) ∈ R2 : x + t2 y ≥ 2t, t > 0 , n   o 1 1 one easily sees that (18) holds with U := ,t : t > 0 . Hence, according n 2 t 3  o 4t to the proof of Theorem 29, for T = , 4t : t 1+t4 1+t4 > 0 ∪ {02 } one has FT (02 ) = C. Corollary 31 For any s ∈ Rn , the mapping T 7→ FT (s) is a bijection from the set of all compact convex subsets of Rn that contain s as a boundedly exposed point onto the the set of all nonempty closed convex subsets of Rn that are coradiant with respect to s and do not contain s. Proof. It is an easy consequence of Theorems 22 and 29 together with Propo- sition 7.  Acknowledgments. The authors wish to thank an anonymous referee for her/his valuable com- ments and criticisms which helped us improve the manuscript. We are also grateful to Alberto Zaffaroni for helpful discussions on coradiant sets; in par- ticular, for providing us with reference [26]. The first and second author were supported by Ministry of Science, Innova- tion and Universities of Spain and the European Regional Development Fund (ERDF) of the European Commission, Grants PGC2018-097960-B-C22 and PGC2018-097960-B-C21, respectively. The second author was also supported 16 by the Severo Ochoa Programme for Centres of Excellence in R&D [SEV- 2015-0563]. He is affiliated to MOVE (Markets, Organizations and Votes in Economics). References [1] S.W. Bae, Tight bound for farthest-color Voronoi diagrams of line segments, in: WALCOM: Algorithms and Computation, 40–51, Lecture Notes in Comput. Sci., 7157, Springer, Heidelberg, 2012. [2] S.W. Bae, Tight bound and improved algorithm for farthest-color Voronoi diagrams of line segments, Comput. Geom. 47 (2014) 779-788. [3] S.W. Bae, K.-Y. Chwa, Farthest Voronoi diagrams under travel time metrics (extended abstract). WALCOM: Algorithms and Computation, 28–39, Lecture Notes in Comput. Sci., 7157, Springer, Heidelberg, 2012. [4] M. Brazil, C.J. Ras, D.A. Thomas, A geometric characterisation of the quadratic min-power centre, European J. Oper. Res. 233 (2014) 34-42. [5] K.Q. Brown, Geometric Transformations for Fast Geometric Algorithms, Ph.D. Thesis, Department of Computer Science, Carnegie Mellon University, 1979. [6] O. Cheong, H. Everett, M. Glisse, J. Gudmundsson, S. Hornus, S. Lazard, M. Lee, H.-S. Na, Farthest-polygon Voronoi diagrams, Comput. Geom. 44 (2011) 234-247. [7] Y.K. Cheung, O. Daescu, M. Zivanic, Kinetic red-blue minimum separating circle, in: Combinatorial Optimization and Applications, 448-463, Lecture Notes in Comput. Sci., 6831, Springer, Heidelberg, 2011. [8] M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf, Computational Geometry: Algorithms and Applications, Springer, New York-Secaucus, NJ, 1997. [9] P.M. Dearing, P. Belotti, A.M. Smith, A primal algorithm for the weighted minimum covering ball problem in Rn , TOP 24 (2016) 466-492. [10] B. Delaunay, Sur la sphère vide: À la mémoire de Georges Voronoi (French), Izv. Akad. Nauk SSSR, Otdelenie Matematicheskih i Estestvennyh Nauk 7 (1934) 793-800. [11] M. Edelstein, On some special types of exposed points of closed and bounded sets in Banach spaces. I, Indag. Math. 28 (1966) 360-363. [12] M. Edelstein, Farthest points of sets in uniformly convex Banach spaces. Israel J. Math. 4 (1966) 171-176. [13] M.A. Goberna, M.A. López, Linear Semi-Infinite Optimization, Wiley, Chichester, 1998. 17 [14] M.A. Goberna, J.-E. Martı́nez-Legaz, V.N. Vera de Serio, The Voronoi inverse mapping, Linear Algebra Appl. 504 (2016) 248-271. [15] M.A. Goberna, M.M.L. Rodrı́guez, V.N. Vera de Serio, Voronoi cells via linear inequality systems, Linear Algebra Appl. 436 (2012) 2169-2186. [16] S. Mazur, Über schwache Konvergenz in den Räumen (Lp ) (German), Studia Math. 4 (1933) 128-133. [17] R.R. Phelps, A representation theorem for bounded convex sets, Proc. Am. Math. Soc. 11 (1960) 976-983. [18] F.P. Preparata, M.I. Shamos, Computational Geometry: An Introduction, Springer, New York, 1985. [19] R.T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, N.J., 1970. [20] M. Shamos, Computational Geometry, Ph.D. Thesis, Department of Computer Science, Yale University, 1978. Available from University Microfilms, Ann Arbor, MI. [21] M. Shamos, The Early Years of Computational Geometry – A Personal Memoir, Advances in Discrete and Computational Geometry (B. Chazelle, J. E. Goodman, and R. Pollack, eds.), Contemporary Mathematics, pp. 313-333, Amer. Math. Soc., Providence, 1998. [22] I. Singer, Maximization of lower semi-continuous convex functionals on bounded subsets of locally convex spaces. I: Hyperplane theorems, Appl. Math. Optimiz. 5 (1979) 349-362. [23] S. Straszewicz, Über exponierte Punkte abgeschlossener Punktmengen (German), Fundamenta Math. 24 (1935) 139-143. [24] J. Tind, Blocking and antiblocking sets, Math. Program. 6 (1974) 157–166. [25] I. Voigt, S. Weis, Polyhedral Voronoi cells, Beiträge Algebra Geom. 51 (2010) 587-598. [26] A. Zaffaroni, Convex coradiant sets with a continuous concave cogauge, J. Convex Anal. 15 (2008) 325-343. [27] Y. Zhu, J. Xu, On the central path problem, Theoret. Comput. Sci. 507 (2013) 83-99. 18