On the Structure of Higher Order Voronoi Cells Juan Enrique Martı́nez-Legaz∗, Vera Roshchina†, Maxim Todorov‡ arXiv:1811.10257v4 [math.MG] 13 Jun 2019 June 14, 2019 Abstract The classic Voronoi cells can be generalized to a higher-order ver- sion by considering the cells of points for which a given k-element subset of the set of sites consists of the k closest sites. We study the structure of the k-order Voronoi cells and illustrate our theoretical findings with a case study of two-dimensional higher-order Voronoi cells for four points. 1 Introduction The classic Voronoi cells partition the Euclidean space into polyhedral regions that consist of points nearest to one of the sites from a given finite set. We consider higher order (or multipoint) Voronoi cells that correspond to the subsets of points nearest to k several sites (see an illustration in Fig. 1). To our best knowledge, the earliest mention of k-point Voronoi cells ap- pears in [1], where a tessellation of the plane by such cells was called the Voronoi diagram of order k; that paper also provides bounds on the number of nonempty cells in a plane and complexity estimates for the construction of such diagrams; in [2] the complexity of constructing the higher-order dia- grams for line segments was studied. ∗ Departament d’Economia i d’Història Econòmica, Universitat Autònoma de Barcelona, and BGSMath, Spain, JuanEnrique.Martinez.Legaz@uab.cat † School of Mathematics and Statistics, UNSW Sydney, Australia, v.roshchina@unsw.edu.au ‡ Department of Physics and Mathematics, UDLAP, Puebla, Mexico. On leave from In- stitute of Mathematics and Informatics, BAS, Sofia, Bulgaria, maxim.todorov@udlap.mx 1 AB A AC BC B AE C CE BF CD BD E DE D F DF EF Figure 1: The classic and order two Voronoi diagrams on six sites (shown in dashed lines and shaded regions, respectively). Notice that some two-point combinations generate empty cells. The multipoint or k-order Voronoi diagrams discussed in this paper are one possible way to generalize the classic construction. Some notable gener- alizations are the cells of more general sets [2, 3], the use of non-Euclidean metrics [4, 5, 6] and the abstract cells that are defined via manifold partitions of the space rather than distance relations [7]. Much of the recent work mentioned above is focussed on the algorithmic complexity of constructing planar Voronoi diagrams of various types. In this paper we rather focus on the structure of multipoint Voronoi cells, and in particular obtain constructive characterizations of cells with nonempty interior, also of bounded and empty cells. We use these results for a case study of multipoint cells defined on at most four sites. We prove that— perhaps counterintuitively—some convex polygons, including triangles and cyclic quadrilaterals, can not be such cells, and provide explicit algorithms for the construction of sites for a given cell in other cases. Finally, we would like to mention a wealth of emerging application of higher order Voronoi cells, predominantly driven by the recent advancements in big data and mobile sensor technology. For instance, in [8] such cells are utilized in a numerical technique for smoothing point clouds from experimen- tal data; in [9] k-order cells are used for detecting and rectifying coverage problems in wireless sensor networks; in [10] the k-order diagrams are used to analyze coalitions in the US supreme court voting decisions. A well-known application of the higher order Voronoi cells is in a k-nearest neighbor prob- 2 lem in spatial networks [11], however, the practical implementations are lim- ited due to the complexity of higher order diagrams and the lack of readily available software. Our work is organized as follows. In Section 2 we study the structure of higher order Voronoi cells, and in particular prove the conditions for the cell to be bounded and nonempty. In Section 3 we study the special case of higher order cells on no more than four sites. We will refer to the higher order cells as multipoint cells, to highlight the discrete nature of our construction. 2 High Order Voronoi Cells in Rn Let T ⊂ Rn be finite and nonempty. For a nonempty proper subset S ⊂ T we define the multipoint Voronoi cell as the set of points that are not farther from each point of S than from each point of T \ S,   n VT (S) := x ∈ R : max dist(s, x) ≤ min dist(t, x) , s∈S t∈T \S where dist(x, y) is the Euclidean distance function. When S is a singleton, i.e. S = {s}, the set VT (S) is a classic Voronoi cell. We abuse the notation slightly and write VT (s) := VT ({s}). It is evident that \ VT (S) = V{s}∪(T \S) (s). (1) s∈S It is not difficult to observe that each multipoint Voronoi cell is a convex polyhedron, i.e. the intersection of finitely many closed halfspaces, since each cell is defined by finitely many linear inequalities. Explicitly, we have the following representation. Proposition 2.1. Let T be a finite subset of Rn , and let S be a nonempty and proper subset of T . Then VT (S) is the intersection of |S|(|T | − |S|) closed halfspaces: \  1  n 2 2  VT (S) = x ∈ R : ht − s, xi ≤ ktk − ksk . (2) s∈S 2 t∈T \S 3 Proof. Observe that, from the definition,   n VT (S) = x ∈ R : max dist(x, s) ≤ min dist(x, t) s∈S t∈T \S \  n = x ∈ R : dist(x, s) ≤ min dist(x, t) t∈T \S s∈S \ \ = {x ∈ Rn : dist(x, s) ≤ dist(x, t)} . s∈S t∈T \S Explicitly for the Euclidean distance function we have dist(x, s) ≤ dist(x, t) ⇔ kxk2 −2hs, xi+ksk2 ≤ kxk2 −2ht, xi+ktk2 , (3) from where the desired representation follows. As a consequence of a well known necessary and sufficient condition for the inconsistency of an arbitrary system of linear inequalities [12, Theorem 4.4(i)], from (2) we obtain the following characterization of empty Voronoi cells. Theorem 2.1. Let T be a finite subset of Rn , and let S be a nonempty and proper subset of T . Then VT (S) = ∅ iff      0n t−s ∈ cone , s ∈ S, t ∈ T \ S . (4) −1 ktk2 − ksk2 We use the characterization in Theorem 2.1 to obtain two well known statements about the classic Voronoi cells. Corollary 2.1. Let T be a finite subset of Rn with |T | ≥ 2. Then VT (T \ {t}) 6= ∅ iff t is an extreme point (vertex) of conv T . Proof. Suppose that there exists s ∈ T such that VT (s) = ∅. Then (4) holds for S = {s}, and therefore there exist λt ≥ 0 for t ∈ T \ {s} such that X X λt ktk2 − ksk2 = −1,  λt (t − s) = 0n and t∈T \{s} t∈T \{s} 4 whereby X X λt λ0 := λt > 0 and s = t. λ0 t∈T \{s} t∈T \{s} Since the the square of the Euclidean norm k.k2 is a strictly convex function, we have X X X λt λt ktk2 + 1 = λr ksk2 = λ0 ksk2 < λ0 ktk2 λ0 t∈T \{s} r∈T \{s} t∈T \{s} X 2 = λt ktk , t∈T \{s} which is a contradiction. Now, suppose that VT (T \ {t}) = ∅. Denote S := T \ {t}. From Theorem 2.1, there exist λs ≥ 0 for s ∈ S such that X X λs ktk2 − ksk2 = −1,  λs (t − s) = 0n and s∈S s∈S whereby X X λs λs > 0 and t = P s. s∈S s∈S r∈S λr Hence, t is not an extremeP point. If t is not an extreme point, then there exist λs ≥ 0, s ∈ S with s∈S λs = 1 and t = s∈S λs s. Since k.k2 is a P strictly convex function, X ktk2 < λs ksk2 ; s∈S λs therefore, setting µs := P λr krk2 −ktk2 for s ∈ S, we have µs ≥ 0, r∈S X X µs ktk2 − ksk2 = −1,  µs (t − s) = 0n and s∈S s∈S showing that (4) holds, which, in view of Theorem 2.1, proves the corollary. The following result generalizes the “if” statement in the last part of Corollary 2.1. Corollary 2.2. Let T be a finite subset of Rn , and let S be a nonempty and proper subset of T . If (conv S) ∩ (T \ S) 6= ∅, then VT (S) = ∅. 5 Proof. Taking t ∈ (conv S)∩(T \S), since t is not an extreme point of conv S, by Corollary 2.1 we have VT (S) ⊆ VS∪{t} (S) = ∅. In fact we can prove a more general geometric statement which yields the preceding corollary. Theorem 2.2. Let T be a finite subset of Rn , and let S be a nonempty and proper subset of T . Then VT (S) 6= ∅ iff there exists a closed Euclidean ball B ⊃ S such that int B ∩ (T \ S) = ∅. Proof. First assume that VT (S) 6= ∅. Then there exists c ∈ VT (S). Let R := max dist(c, s), s∈S and let B be the closed Euclidean ball of radius R centered at c, clearly S ⊂ B. Evidently, int B ∩ (T \ S) = ∅, otherwise we would have dist(c, t) < dist(c, s) for some t ∈ T \ S and s ∈ S, hence, c ∈ / VT (S), which contradicts our choice of c. Now assume that there exists some closed Euclidean ball B such that S ⊂ B and int B ∩ (T \ S) = ∅. The centre of the ball B is contained in VT (S), hence, VT (S) 6= ∅. We give an explicit example of an empty cell with |S| = 2 and |T | = 3. Example 2.1. Let s1 = (−1, 0), s2 = (1, 0), t = (0, 0). It is not difficult to observe that (2) becomes   1 1 VT (S) = (x1 , x2 ) : x1 ≤ − , x1 ≥ = ∅. 2 2 This configuration is shown in Fig. 2. Figure 2: Minimal configuration for an empty cell 6 Notice that we can likewise construct an empty cell with |T | > |S| ≥ 2 by making sure that (T \ S) ∩ conv S 6= ∅ (using Corollary 2.2). Theorem 2.3. Let T be a finite subset of Rn , and let S be a nonempty and proper subset of T . Then VT (S) is bounded iff cone {t − s, s ∈ S, t ∈ T \ S} = Rn . Proof. It suffices to observe that from the linear representation (2) we obtain that the first moment cone of VT (S) is cone {t − s, s ∈ S, t ∈ T \ S}. Remark 2.1. It follows from Theorem 2.3 that if n ≥ 2 and |T | ≤ 3 all nonempty cells are unbounded. We can strengthen the result in the preceding remark as follows. Theorem 2.4. Let T be a finite subset of Rn . If √ |T | < 2 n + 1, (5) then for any S ⊂ T the cell VT (S) is either empty or unbounded. Proof. Assume that VT (S) = ∅. The proof is based on the observation that a nonempty bounded polyhedron in Rn must be defined by at least n + 1 inequalities. Let p := |T |, k := |S|. Then the number of inequalities that feature in the representation (2) is φ(k) = k(p − k). Observe that φ attains its maximum at p2 for even p and at p−12 for odd p. Hence for even p p  p2  2 p p k(p − k) ≤ p− = = , 2 2 4 4 and for odd p p2 − 1    2 p−1 p−1 p k(p − k) ≤ p− = = , 2 2 4 4 hence, ensuring (5) yields at most n inequalities that define each cell, and so all nonempty cells are unbounded. Proposition 2.2. Let S ⊂ T ⊂ Rn , with |S| = 3 and |T | = 4. Then VT (S) is either empty or unbounded. Proof. Put T \ S = {t} . In case t ∈ conv S, then Corollary 2.1 gives that VT (S) = ∅. If t ∈ / conv S, then t can be separated from S, and by Theorem 2.3 the cell has to be unbounded. 7 The following statement will be useful later for a discussion on planar quadrilateral cells. Proposition 2.3. Let S ⊂ T ⊂ R2 , with S = {s1 , s2 } and T \ S = {t1 , t2 }. Then VT (S) is bounded iff (s1 , s2 ) ∩ (t1 , t2 ) is a singleton. Proof. The configuration of the points of T in Fig. 3 means that if we take Figure 3: Configuration for a bounded cell the line through s1 and s2 , then t1 and t2 belong to the two opposite open halfspaces defined by this line. The same holds true if we interchange s1 and s2 with t1 and t2 . From the linear representation (2) we obtain that the first moment cone M of VT (S) is equal to cone {ti − sj , i, j = 1, 2} . Let us consider that the configuration of the points of T is like in Fig. 3. Then, we are going to prove that M = R2 , which, by Theorem 2.3, implies that VT {S} is bounded. What we are actually going to prove is the equivalent assertion that the polar cone M ◦ reduces to {02 } . To this aim, let p ∈ M ◦ and assume, w.l.o.g., that (s1 , s2 ) ∩ (t1 , t2 ) = {02 } . Then there exist λ, µ > 0 such that s2 = −λs1 and t2 = −µt1 . Since hp, t1 − s1 i ≤ 0 and hp, t1 + λs1 i = hp, t1 − s2 i ≤ 0, we have hp, t1 i ≤ 0. This inequality combined with hp, −µt1 − s1 i = hp, t2 − s1 i ≤ 0 yields hp, s1 i ≥ 0; hence, in view of hp, −µt1 + λs1 i = hp, t2 − s2 i ≤ 0, it turns out that hp, t1 i = 0 = hp, s1 i . Since s1 and t1 are linearly independent because of the assumption (s1 , s2 ) ∩ (t1 , t2 ) = {02 }, we conclude that p = 0, as was to be proved. Second, let the Voronoi cell VT {s1 , s2 } be bounded. Then, by Theorem 2.3, the first moment cone cone {ti − sj , i, j = 1, 2} is the whole of R2 . This implies that t1 and t2 are not on a common closed halfplane out of the two determined by the straight line through s1 and s2 , as otherwise that cone would be contained in the translate of that half-space with the boundary line passing through the origin, and the same assertion holds true when we interchange t1 and t2 with s1 and s2 . This rules out the possibility that conv {s1 , s2 , t1 , t2 } be a segment, a triangle, or a quadrilateral having s1 and s2 as adjacent vertices. Therefore 8 s1 and s2 are opposite vertices of the quadrilateral conv {s1 , s2 , t1 , t2 } , which clearly implies that (s1 , s2 )∩(t1 , t2 ) is a singleton. The proof is completed. Theorem 2.5. Let T be a finite subset of Rn , and let S be a nonempty and proper subset of T . Then int VT (S) 6= ∅ iff    t−s 0n+1 ∈ / conv , s ∈ S, t ∈ T \ S . ktk2 − ksk2 Proof. The proof comes from the well known characterization of the Slater condition for a linear system of inequalities [13, Theorem 3.1]. Example 2.2. Consider a system T of four points in the plane, T = {(0, 0) , (1, 1) , (1, 0) , (0, 1)}, S = {(0, 0) , (1, 1)}. This is illustrated in Fig. 4. Using Theorems 2.1, 2.3 and 2.5, it is easy to Figure 4: A singleton cell (the intersection of the two shaded regions). check that  is nonempty and bounded, but int VT (S) = ∅. Indeed,  VT (S) VT (S) = 21 , 12 . The next statement is a specific characterization for a three-point system, which we will use in what follows. Proposition 2.4. Let T, T 0 ⊂ Rn be such that |T | = |T 0 | = 3 and T and T 0 differ by exactly one point (i.e. |T ∩ T 0 | = 2). Let s ∈ T \ T 0 and s0 ∈ T 0 \ T . If VT (s) ⊆ VT 0 (s0 ), then all points in the set T 0 ∪ T belong to the same straight line. 9 Proof. For notational convenience we will prove the result for T = {t1 , t2 , 0} and T 0 = {t1 , t2 , s}, where the points t1 , t2 , s are all nonzero and pairwise distinct. Let   n 1 2 F := VT (0) = x ∈ R : htj , xi ≤ ktj k , j = 1, 2 , 2   0 n 1 2 2  F := VT 0 (s) = x ∈ R : htj − s, xi ≤ ktj k − ksk , j = 1, 2 . 2 The two inequalities defining F 0 are consequence relations of the inequalities defining F . Therefore there exist λij ≥ 0, i, j = 1, 2 such that 2 X ti − s = λij tj , i = 1, 2 and (6) j=1 2 X 2 2 kti k − ksk ≥ λij ktj k2 , i = 1, 2. j=1 Hence s = (1 − λii ) ti − λi(3−i) t3−i , i = 1, 2 and (7) ksk2 ≤ (1 − λii ) kti k2 − λi(3−i) kt3−i k2 , i = 1, 2. (8) We can subtract the two representations (7) of s to obtain (1 − λ11 + λ21 ) t1 + (−1 − λ12 + λ22 ) t2 = 0n . If tj , j = 1, 2 are linearly independent, we have 1 = λ11 − λ21 and 1 = λ22 − λ12 . Together with (8) this yields 0 ≤ ksk2 ≤ (1 − λ11 ) kt1 k2 − λ12 kt2 k2 = −λ21 kt1 k2 − λ12 kt2 k2 ≤ 0, which contradicts the condition s 6= 0. Therefore tj , j = 1, 2 are linearly dependent. Together with (6) this finishes the proof. Remark 2.2. This proposition means that it is impossible to enlarge a Voronoi cell of a single point in a three-point affinely independent system by moving this point. Proposition 2.5. Let T be a finite subset of Rn , and let S be a nonempty proper subset of T . If |S| ≥ 2, then [  VT (S) = VT \{s} (S \ {s}) ∩ VS (s) . (9) s∈S 10 Proof. Denote As := VT \{s} (S \ {s}) ∩ VS (s). Observe that for any s̄ ∈ S we have As̄ = {x ∈ Rn : dist(x, s̄) ≤ dist(x, s) ≤ dist(x, t) ∀s ∈ S, t ∈ T \ S}. S Evidently, As ⊆ VT (S) for every s ∈ S, hence, As ⊆ VT (S). To prove the s∈S reverse inclusion, assume that x ∈ VT (S). Let s̄ be a closest point to x in S. It is evident that x ∈ VS (s̄). At the same time, it is not difficult to observe that VT (S) ⊆ VT \{s̄} (S \ {s̄}). Hence x ∈ VT \{s̄} (S \ {s̄}) ∩ VS (s̄) = As̄ , S and therefore VT (S) ⊆ As . s∈S Proposition 2.6. Let T be a finite subset of Rn , and let S be a nonempty and proper subset of T . If there exist s1 , s2 ∈ S and t1 , t2 ∈ T \ S such that the inequalities ks1 − xk ≤ kt1 − xk and ks2 − xk ≤ kt2 − xk (10) define the same halfspace, then these inequalities are nonessential for VT (S), i.e. they can be dropped from the system (2). Proof. It is evident from the equivalence (3) that these inequalities can be written as 1 1 kt1 k2 − ks1 k2 , ht2 − s2 , xi ≤ kt2 k2 − ks2 k2 . (11)   ht1 − s1 , xi ≤ 2 2 If both inequalities in (10) define the same halfspace, then it follows from (11) that there exists α > 0 such that 1 1 kt2 k2 − ks2 k2 = α kt1 k2 − ks1 k2 . (12)   t2 − s2 = α(t1 − s1 ) and 2 2 Every point x ∈ VT (S) also satisfies the system 1 1 kt1 k2 − ks2 k2 , ht2 − s1 , xi ≤ kt2 k2 − ks1 k2 . (13)   ht1 − s2 , xi ≤ 2 2 Adding these inequalities together we obtain 1 kt1 k2 − ks2 k2 + kt2 k2 − ks1 k2 ,  ht1 − s2 + t2 − s1 , xi ≤ 2 and using (12) we have a consequence of (13), 1 (1 + α)ht1 − s1 , xi ≤ (1 + α) kt1 k2 − ks1 k2 ,  2 which defines the same halfspace as (11). 11 Theorem 2.6. Let T ⊂ Rn be a finite set, let S := {s1 , s2 } ⊂ T be a two-point set, and let H := {x ∈ Rn : kx − s1 k = kx − s2 k} 1 = {x ∈ Rn : hs1 − s2 , xi = (ks1 k2 − ks2 k2 )}. 2 If int VT (S) 6= ∅, then H ∩ ri F = ∅ for every facet F of VT (S). Proof. Let F be the facet of VT (S) defined by the linear equation correspond- ing to some point t0 ∈ T and, say, s1 , that is, ht0 − s1 , xi = 21 (kt0 k2 − ks1 k2 ) , and assume, towards a cotradiction, that H ∩ ri F 6= ∅. Take x ∈ H ∩ ri F. We then have 1 ht0 − s1 , xi = (kt0 k2 − ks1 k2 ). 2 Adding the equality 1 hs1 − s2 , xi = (ks1 k2 − ks2 k2 ), 2 which follows from the fact that x ∈ H, to the preceding one, we get 1 ht0 − s2 , xi = (kt0 k2 − ks2 k2 ). 2 Since int VT (S) 6= ∅ and x ∈ ri F , there is exactly one halfspace among those defined by the inequalities (2) such that x belongs to its boundary hyperplane (and hence to the interior of the remaining halfspaces). Hence the linear equalities 1 ht0 − s1 , xi = (kt0 k2 − ks1 k2 ) (14) 2 and 1 ht0 − s2 , xi = (kt0 k2 − ks2 k2 ) (15) 2 define the same hyperplane, which implies the existence of a real number λ such that t0 − s2 = λ (t0 − s1 ) , so that the points t0 , s1 , s2 are colinear. Substituting x := t0 +s 2 1 , which is a solution of (14), into (15) we have, after elementary algebraic manipulation, ht0 − s2 , s1 − s2 i = 0, meaning that s1 − s2 must be orthogonal to t0 − s2 . This, together with the colinearity of t0 , s1 and s2 and the fact that these three points ar distinct, yields a contradiction. 12 3 Case Study In this section we study the special case of higher order cells on no more than four sites. With the exception of subsections 3.5-3.7, our study will be developed for sets in R2 . For every set F ⊂ R2 defined by four linear inequalities, we will determine whether or not there exist sets S ⊂ T ⊂ R2 , with |S| = 2 and |T | = 4, such that VT (S) = F. In the cases when the answer will be affirmative, we will construct the (possibly non necessarity unique) sets S and T explicitly. 3.1 Singletons A singleton (zero-dimensional) cell {c} can be obtained by placing the pairs of points (s1 , s2 ) and (t1 , t2 ) in the opposite corners of a square centred at c. This was already discussed in Example 2.2. Note that this is a minimal representation, since we need at least three inequalities to obtain a bounded cell (cf. Theorem 2.4), and hence |T | ≥ 4. In fact the square can be replaced by a rectangle or a general cyclic quadrilateral (we recall that a quadrilateral is said to be cyclic if all of its vertices are on a single circle, which is equivalent to the fact that the sum of opposite angles equals π). Proposition 3.1. Let S ⊂ T ⊂ R2 , with |S| = 2 and |T | = 4. The following statements are equivalent: a) VT (S) is nonempty and at most one-dimensional. b) The points of T are the vertices of a cyclic quadrilateral, with the two sites of S located opposite to each other (across a diagonal). c) VT (S) is a singleton. Proof. Throughout the proof, we use the explicit notation S := {s1 , s2 } and T := {s1 , s2 , t1 , t2 }. a) ⇒ b). Without loss of generality assume that 0 ∈ VT (S) while int VT (S) = ∅. By Theorem 2.5 we have X X 0= λij (tj − si ), 0= λij (ktj k2 − ksi k2 ), (16) i,j∈{1,2} i,j∈{1,2} where λij are convex combination coefficients. Since 0 ∈ VT (S), we have from (2) that ktj k ≥ ksi k ∀i, j ∈ {1, 2}. Without loss of generality assume that ks2 k ≤ ks1 k ≤ kt1 k ≤ kt2 k. 13 If ks1 k < kt1 k, then ksi k < ktj k for all i, j ∈ {1, 2} , which implies that the second equality in (16) is impossible. Hence, ks1 k = kt1 k. If ks1 k > ks2 k, then kti k > ks2 k for all i ∈ {1, 2} ; therefore, from (16), we get λ21 = λ22 = 0 and s1 = λ11 t1 + λ12 t2 , so s1 ∈ [t1 , t2 ] and ks1 k2 = λ11 kt1 k2 + λ12 kt2 k2 , which holds only when t1 = t2 = s1 by the strict convexity of the squared norm. This is impossible. Likewise, when kt1 k < kt2 k we have λ12 = λ22 = 0, then t1 ∈ [s1 , s2 ], which by Corollary 2.2 yields VT (S) = ∅, again a contradiction. We have proved that ks2 k = ks1 k = kt1 k = kt2 k, and hence our sites are the vertices of a cyclic quadrilateral. It is now easy to observe that s1 , s2 are located opposite to each other because, by the first equality in (16), we have [s1 , s2 ] ∩ [t1 , t2 ] 6= ∅. b) ⇒ c) Since the points of T lie on some circle, without loss of generality we may assume that the centre of this circle is the origin, and then kt1 k = kt2 k = ks1 k = ks2 k. In this case the right-hand side of system (2) is zero, and we have, for every point x ∈ VT (S), htj − si , xi ≤ 0 ∀i, j ∈ {1, 2}. (17) It is evident that x = 0 is a solution of this system; hence, VT (S) 6= ∅. On the other hand, from (17) it follows that VT (S) is a cone. From these facts, using Proposition 2.3 we immediately deduce that VT (S) = {0} . The implication c) ⇒ a) is obvious. Note that for the case |S| = 2 and |T | = 3 it is impossible to have a nonempty bounded cell due to Remark 2.1. This means that we do not need to consider this configuration when discussing the subsequent cases of bounded polygons. Furthermore, in the case |S| = 3 and |T | = 4 it is impossible to have a bounded cell, as was shown in Proposition 2.2. Since we have determined that we can not have a nonempty bounded cell for |T | = |S| + 1, the only possibility to have a singleton cell is for |S| = 2 and |T | = 4. Furthermore, we can focus on the latter case when studying other bounded cells. 3.2 One-Dimensional Cells It follows from the preceding discussion that it is impossible to obtain line segments as multipoint Voronoi cells in our setting. Corollary 3.1. Let S ⊂ T ⊂ R2 , with |S| = 2 and |T | = 4. Then VT (S) is not one-dimensional. 14 Proof. Follows directly from Proposition 3.1. It follows from Corollary 3.1 that it is impossible to have a one-dimensional cell for |T | = 4, |S| = 2, so both rays and lines are impossible in this config- uration. Now consider the case |T | = |S| + 1. If VT (S) 6= ∅, by Corollary 2.2 we must have for {t} = T \ S that t ∈ / conv S. By the separation theorem this yields the existence of some d, kdk = 1 such that ht − s, di < 0 ∀s ∈ S, which yields the existence of a sufficiently small ball Bε (d) centred at d such that ht − s, yi < 0 ∀s ∈ S, ∀y ∈ Bε (d). Then for any x0 ∈ VT (S) and any y ∈ Bε (d) we have ht − s, x0 + yi = ht − s, x0 i + ht − s, yi < ht − s, x0 i. It is hence clear from the representation in Proposition 2.1 that x0 + Bε (y) ⊂ VT (S), which gives that VT (S) is one-dimensional. Thus we have proved the following statement. Proposition 3.2. Let S ⊂ T ⊂ Rn , with |T | = |S| + 1. Then VT (S) is not one-dimensional. 3.3 Triangles A somewhat surprising result is that a second order Voronoi cell cannot be a triangle. As discussed previously, we only need to prove this for the case |S| = 2 and |T | = 4. Proposition 3.3. Let S ⊂ T ⊂ R2 , with |S| = 2 and |T | = 4. Then VT (S) is not a triangle. Proof. Suppose that VT (S) is a triangle. Denote T = {s1 , s2 , t1 , t2 }, S = {s1 , s2 }. The cell VT (S) is the solution set of the linear system of inequalities hcij , xi ≤ αij (i, j = 1, 2) , (18) with cij := ti − sj and αij := 21 kti k2 − ksj k2 . Notice that          c22 c11 c12 c21 =− + + . (19) α22 α11 α12 α21 15 Without loss of generality, we will assume that 0 ∈ int VT (S), that is, αij > 0 (i, j = 1, 2) . Since (18) defines a triangle, one of its inequalities, say the one corresponding to i = 2 = j is redundant, so that the triangle is actually the solution set of thesystem consisting  ofthe other three. We claim that the c11 c12 c21 vectors , and are linearly independent. Indeed, α11 α12 α21 assume the existence of (β11 , β12 , β21 ) ∈ R3 \ {(0, 0, 0)} such that         c11 c12 c21 02 β11 + β12 + β21 = , (20) α11 α12 α21 0 and let x be the vertex of VT (S) defined by hc12 , xi = α12 and hc21 , xi = α21 . (21) Then, from (20) and (21) we easily deduce that β11 (hc11 , xi − α11 ) = 0. Since hc11 , xi < α11 , as the three sides of VT (S) don’t have a common point, it follows that β11 = 0. By using the same argument with the other two vertices  of VT (S),  we  deduce that β12 = 0 = β21 , thus proving our claim c11 c12 c21 that , and are linearly independent. Since the α11 α12 α21 inequality corresponding to i = 2 = j is redundant, by Farkas’ lemma there exist λij ≥ 0 (i, j = 1, 2) such that c22 = λ11 c11 + λ12 c12 + λ21 c21 and α22 ≥ λ11 α11 + λ12 α12 + λ21 α21 . (22) Considering again the vertex x, from (19) we obtain that α22 = −α11 + α12 + α21 ≤ − hc11 , xi + hc12 , xi + hc21 , xi = h−c11 + c12 + c21 , xi = hc22 , xi ≤ α22 ; hence, by (22), we deduce that hc22 , xi = α22 ≥ λ11 α11 + λ12 α12 + λ21 α21 ≥ λ11 hc11 , xi + λ12 hc12 , xi + λ21 hc21 , xi = hλ11 c11 + λ12 c12 + λ21 c21 , xi = hc22 , xi . Therefore λ11 α11 + λ12 α12 + λ21 α21 = α22 , that is,         c22 c11 c12 c21 = λ11 + λ12 + λ12 . α22 α11 α12 α21 Comparing    this equality  with (19)  and taking into account that the vectors c11 c12 c21 , and are linearly independent, we deduce that α11 α12 α21 λ11 = −1, a contradiction. 16 3.4 Bounded Quadrilaterals We next show that any non-cyclic bounded convex quadrilateral is a second order Voronoi cell with |T | = 4. We also prove that it is impossible for a cyclic quadrilateral to be a Voronoi cell of 2 points (when |T | = 4). Proposition 3.4. Let F ⊂ R2 be a non-cyclic bounded convex quadrilateral. Then there exist S ⊂ T ⊂ R2 , with |S| = 2 and |T | = 4, such that VT (S) = F . Proof. First, looking at Fig. 5, where F is depicted as the quadrilateral ACBD, we would like to mention that ^CAD = α > 0 and ^CBD = β > 0 Figure 5: Bounded quadrilateral. and, w.l.o.g., π > α+β. We draw the lines through A (B) that make an angle equal to α (resp., β) with the segment AB. In this way, we get the points t1 and t2 as the two other vertices of the quadrilateral having those lines as their sides. We take s1 and s2 as the symmetric points of t1 with respect to the lines CA and CB, respectively, and we set S := {s1 , s2 } and T := {s1 , s2 , t1 , t2 }. The only thing that we have to prove is that t2 s1 ⊥AD and t2 s2 ⊥BD. The point B is the center of the circle passing through the points t1 , t2 and s2 . Therefore, ^t1 s2 t2 = π − β, which, looking at the quadrilateral C2 s2 D2 B, implies that t2 s2 ⊥BD. The point A is the center of the circle passing through the points t1 , t2 and s1 . Therefore, ^t1 s1 t2 = π − α, which, looking at the quadrilateral C1 s1 D1 A, implies t2 s1 ⊥AD. Observe that the algorithm does not work if π ≤ α + β. However it is not difficult to observe that for a non-cyclic convex quadrilateral it is always 17 possible to choose the corners to ensure α + β < π. We have the following negative result. Proposition 3.5. Let S ⊂ T ⊂ R2 , with |S| = 2 and |T | = 4. Then VT (S) is not a cyclic quadrilateral. Proof. Assume that the Voronoi cell VT (S) of some set S := {s1 , s2 }, with T := {s1 , s2 , t1 , t2 }, is a cyclic quadrilateral. Then each side of this quadri- lateral is defined by the bisector between si and tj for i, j ∈ {1, 2}. First, we will show that any two sides defined by the bisectors of disjoint pairs, say, {s1 , t1 } and {s2 , t2 }, cannot be adjoint. Assume the contrary: then without loss of generality the intersection u of the two bisectors is a vertex of VT (S). We have, by using the representation (2), 1 1 ht1 − s2 , ui ≤ (kt1 k2 − ks2 k2 ), ht2 − s1 , ui ≤ (kt2 k2 − ks1 k2 ), (23) 2 2 and since u is the intersection of the two bisectors, 1 1 ht1 − s1 , ui = (kt1 k2 − ks1 k2 ), ht2 − s2 , ui = (kt2 k2 − ks2 k2 ). (24) 2 2 Adding the two equalities in (24) and rearranging, we obtain 1 1 ht1 − s2 , ui + ht2 − s1 , ui = (kt1 k2 − ks2 k2 ) + (kt2 k2 − ks1 k2 ). 2 2 Together with (23) this yields equalities in (23), and hence the four lines that define the sides of the quadrilateral must intersect at u. This is impossible, hence, the assumption is wrong. Now, let us consider the quadrilateral with vertices s1 , s2 , t1 and t2 . Looking at Fig. 6, it is easy to see that the angles at t1 and C are equal, and so they are the angles at t2 and A. This means that this quadrilateral is cyclic too, that is, s1 , s2 , t1 and t2 lie on a circle. It follows from Proposition 3.1 that the Voronoi cell VT (S) is a singleton, which contradicts our assumption. 3.5 Halfspaces A halfspace cell can be obtained by putting the two points of S on a line perpendicular to the boundary line of the halfspace making sure that S is in the interior of the halfspace. An additional point t is placed on the same line on the opposite side of the hyperplane at the same distance from the hyperplane as the distance to the hyperplane from the farthest point in S (see Fig. 7). We hence conclude that a halfspace can be constructed using |S| = 2 and |T | = 3. Observe that it is also possible to do the same construction for |S| ∈ {2, 3} and |T | = 4. We prove this explicitly in the next statement. 18 Figure 6: An illustration to the proof of Proposition 3.5. Figure 7: The intersection of the two halfspaces is VT (s1 , s2 ). Proposition 3.6. Let F ⊂ Rn be a halfspace. Then for any two integers τ > σ ≥ 1 there exist S ⊂ T ⊂ Rn , with |S| = σ and |T | = τ , such that VT (S) = F . Proof. Note that any halfspace F can be represented as F = {x ∈ Rn | hd, xi ≤ γ} for some d, kdk = 1, and γ ∈ R. Choose any x0 such that hd, x0 i = γ, and let S := {s0 , . . . , sm } and T := {t0 , . . . , tp } ∪ S, where m = σ − 1, p = τ − σ − 1, s0 := x0 − d, t0 := x0 + d, si = x0 −αi d, 0 < αi < 1 ∀i ∈ {1, . . . , m}, tj := x0 +βj d, βj > 1 ∀j ∈ {1, . . . , p}, (25) and the constants αi and βj are all different (to ensure that the sites do not coincide). We will next show that VT (S) = {x ∈ R2 | hd, xi ≤ γ}. 19 We have, from the representation in Proposition 2.1,   \ 1 2 2  VT (S) = x : htj − si , xi ≤ ktj k − ksi k . 2 i∈{0,1,...,m} j∈{0,1,...,p} By (25), the inequalities in the latter expression can be rewritten as 1 ∀i ∈ {0, . . . , m}, (βj +αi )hd, xi ≤ ((βj − αi )(βj + αi ) + (βj + αi )hd, x0 i) , 2 ∀j ∈ {0, . . . , p}, where α0 = β0 = 1. Dividing by the factor βj + αi > 0, we have βj − αi hd, xi − hd, x0 i ≤ ; 2 hence,   1 VT (S) = x : hd, xi − γ ≤ · min(βj − αi ) = {x : hd, xi ≤ γ}. 2 i,j The latter set is precisely the halfspace that we were aiming for. 3.6 Intersections of Parallel Halfspaces We consider a set F ⊂ Rn represented by the inequalities α ≤ hd, xi ≤ β, with kdk = 1 and α < β. One can easily check that F = VT (S) for T := {s1 , s2 , t1 , t2 } and S := {s1 , s2 } with, for instance, s1 := 3α+β 4 d, s2 := α+β 2 d, 3α−β 7β−3α t1 := 2 d and t2 := 4 d. We have shown the following result. Proposition 3.7. Let F ⊂ Rn be an intersection of two parallel halfspaces with opposite normals, such that F has a nonempty interior. Then there exist S ⊂ T ⊂ Rn , with |S| = 2 and |T | = 4, such that VT (S) = F . Note that it is impossible to produce a strip with |T | − |S| = 1: indeed, it is clear from the fact that all constraints are defined by parallel lines that all vectors s − t, s ∈ S, t ∈ T should be colinear, lying on some line orthogonal to the inequalities. Now, if for the unique t ∈ T \ S we have t ∈ conv S, then the cell is empty by Corollary 2.2. However if t ∈ / conv S, then the cell has to be a halfspace. Hence the only possibility is |T | = 4, |S| = 2. 20 Figure 8: Construction of the set of sites for a wedge 3.7 Wedges Now, let us have a wedge F := {x ∈ Rn : hci , xi ≤ αi , i = 1, 2} , with c1 and c2 being linearly independent. Let us take an arbitrary point from t ∈ int F − := {x ∈ Rn : hci , xi ≥ αi , i = 1, 2} and construct the two symmet- ric points s1 and s2 with respect to both hyperplanes defining F. If T := {s1 , s2 , t} and S := {s1 , s2 } , then VT (S) = FT (t) = F. It is possible to add any number of more sites s to S in such a way that the halfspaces ks − xk ≤ kt − xk include the original wedge. Proposition 3.8. Let F := {x ∈ Rn | hvi , xi ≤ bi , i = 1, 2} , with v1, v2 ∈ Rn linearly independent unit vectors and b1 , b2 ∈ R. Then there exist S ⊂ T ⊂ Rn , with |S| = 2 and |T | = 4, such that VT (S) = F . Proof. Without loss of generality, we assume that bi = 0 (i = 1, 2) . Set β := hv1 , v2 i , i0 := 3 − i for i = 1, 2, and define si := −vi − 2vi0 (i = 1, 2) . Let ti be the point symmetric to si with respect to the hyperplane defined by hx, vi0 i = 0, that is, ti := −vi + 2 (1 + β) vi0 (i = 1, 2) , 21 and define S := {s1 , s2 } and T := {s1 , s2 , t1, t2 } . We have |T | = 4, since β > −1. Given that kti k2 = 5 + 4β = ksi k2 (i = 1, 2) , one has VT (S) = {x ∈ Rn | hti − si , xi ≤ 0, hti − si0 , xi ≤ 0, i = 1, 2} . (26) Hence, to prove that VT (S) = F, it will suffice to show that, for i = 1, 2, the inequality hx, ti − si i ≤ 0 is equivalent to hx, vi0 i ≤ 0 and that the remaining two inequalities in (26) are redundant. The first assertion is obvious, since ti − si = 2 (2 + β) vi0 and β > −1. Let us now prove that the inequalities hti − si0 , xi ≤ 0 are redundant, that is, that they are consequences of the system hvi , xi ≤ 0 (i = 1, 2) . But this is also immediate, since ti − si0 = vi + (3 + 2β) vi0 and β > −1. 3.8 Unbounded Polygons with Three Sides Our next construction is for an unbounded polygon like the shadowed one in Fig. 9, with three sides, which is unbouned and has non-parallel sides. Figure 9: Unbounded polygon with three sides Proposition 3.9. Let F be an unbounded convex polygon with non-parallel sides and two vertices. Then there exist S ⊂ T ⊂ R2 , with |S| = 2 and |T | = 4, such that VT (S) = F . Proof. In the notation of Fig. 9, where F is depicted as the shaded region, we would like to mention that 0 < α < π, 0 < β < π, α + β > π and β ≥ α. If we consider the triangle ABC, the angle at C is α + β − π. Now, we draw 22 a line through the point A, which makes an angle α + β − π with the line BA. On this line we consider an arbitrary point t1 , sufficiently close to A. Let us take the symmetric points s1 and s2 of t1 with respect to AB and AC, respectively. We shall prove that the line through the points s1 , s2 is perpendicular to BC. For this purpose, we would like to mention that the point A is the center of the circle passing through the points s1 , s2 and t1 . This means that ^s1 s2 t1 = α + β − π. If we consider the quadrilateral formed by the lines BC, AC, s1 s2 and t1 s2 , we get the desired fact. At the end we construct the site t2 as the symmetric point of s1 with respect to the line BC and set S := {s1 , s2 } and T := {s1 , s2 , t1 , t2 }. Proposition 3.10. Let S ⊂ T ⊂ R2 , with |S| = 2 and |T | = 4. Then VT (S) is not an unbounded polygon with parallel sides and just two vertices. Proof. Similarly to the proof of Proposition 3.3, suppose that VT (S) is an unbounded convex polygon with parallel sides and just two vertices, denote S = {s1 , s2 } and T = {s1 , s2 , t1 , t2 }, and suppose further, w.l.o.g., that the redundant inequality in the linear system 1 kti k2 − ksj k2  hti − sj , xi ≤ (i, j = 1, 2) (27) 2 (which has VT (S) as its solution set) is the one corresponding to i = 2 = j. Then, by Farkas’ Lemma, there exist γ11 , γ12 , γ21 ≥ 0 such that t2 − s2 = γ11 (t1 − s1 ) + γ12 (t1 − s2 ) + γ21 (t2 − s1 ) (28) and α22 ≥ γ11 α11 + γ12 α12 + γ21 α21 , (29) 1 2 2 where αij := 2 kti k − ksj k . From (28) we obtain that t2 − s2 belongs to K1 := cone {t1 − s1 , t1 − s2 , t2 − s1 } . On the other hand, two of the three vectors t1 − s1 , t1 − s2 and t2 − s1 are exterior normals to the parallel sides, and hence they make an angle of π. Those two vectors cannot be t1 − s1 and t1 − s2 , because with such a configuration VT (S) would be empty. We will consider the two remaining cases. We start with the case when the two vectors are t1 − s1 and t2 − s1 , say t1 −s1 = −µ (t2 − s1 ) , with µ > 0. Since in this case s2 does not belong to the straight line determined by s1 , t1 and t2 (because the side of VT (S) contained in the line ht1 − s2 , xi = 21 kt1 k2 − ks2 k2 is not parallel to the other two  sides), there is a circle containing s2 , t1 and t2 , and we may assume, w.l.o.g., 23 that the center of this circle is 02 . Then α11 = α21 > 0 and α12 = α22 = 0, thus, in view of (29), we have γ11 = 0 = γ12 and then, by (28), γ12 (t1 − s2 ) = t2 −s2 = − (t1 − s1 )+t1 −s2 +t2 −s1 = t1 −s2 +(1 + µ) (t2 − s1 ) , which yields γ12 − 1 t2 − s1 = (t1 − s2 ) . 1+µ This is impossible because the vectors t1 − s1 , t1 − s2 and t2 − s1 are not all colinear. It only remains to consider the case when t1 − s2 and t2 − s1 are the vectors that make an angle of π. Since t1 − s1 is not colinear with these two vectors, we have that the cones K1 and K2 := cone {− (t1 − s1 ) , t1 − s2 , t2 − s1 } are opposite halfplanes defined by the line containing the vectors t1 − s2 and t2 − s1 . The fact that t2 − s2 ∈ K1 ∩ int K2 provides a contradiction. We note here that it is possible to have an unbounded polygon with three sides for the case |S| = 3 and |T | = 4 if and only if the unbounded sides are non-parallel. Indeed, in this case we can first build a wedge that defines the two unbounded sides (see Subsection 3.7), and then add an extra site to define the extra inequality. For the case of unbounded parallel sides, it is clear that the point t should at the same time lie outside of each of these parallel sides, which is impossible. 3.9 Unbounded Polygons with Four Sides In the next proposition we shall consider the case of an unbounded quadri- lateral in R2 with two parallel sides, shown in Fig. 10. Proposition 3.11. Let F ⊂ R2 be an unbounded convex quadrilateral with two parallel sides. Then there exist S ⊂ T ⊂ R2 , with |S| = 2 and |T | = 4, such that VT (S) = F . Proof. In the notation of Fig. 10, where F is depicted as the unboubed convex polygon with vertices A, B and C, we have l1 k l2 and 0 < α < π, and the point A belongs to the interior of the parallel band. First, we move, parallel to the line l1 , the point A to an arbitrary point M . Through M we draw a line perpendicular to l1 . Take a point S1 on the same line, with the same distance to l2 as M is to l1 . Now, we consider the symmetrical point T1 and T2 of S1 with respect to l2 and l1 , respectively. In this way M is the midpoint of 24 Figure 10: Unbounded polygon with parallel sides the segment T1 T2 . Next we translate the line through the points T1 and T2 in such a way that, defining t1 , t2 , m and s1 as the orthogonal projections of T1 , T2 , M and S1 onto the resulting translated line, one has ^ t1 At2 = 2π − 2α and ^ mAt2 = π −α. For the last site, we take s2 as the symmetric point of t2 with respect to the line through the points A and B. We shall prove that the line through the points t1 , s2 is perpendicular to AC. For this purpose, we observe that the point A is the center of the circle passing through the points t1 , t2 and s2 . This means that ^t2 s2 t1 = π−α. If we consider the quadrilateral formed by the lines BA, AC, t1 s2 and t2 s2 , we get the desired fact. At the end, after having found the desired sets S := {s1 , s2 } and T := {s1 , s2 , t1 , t2 }, we would like to mention that this construction is impossible if α = π. We next consider the case of an arbitrary unbounded convex quadrilateral with nonparallel sides, presented in Fig. 11. Proposition 3.12. Let F be an unbounded convex quadrilateral with no sides parallel. Then there exist S ⊂ T ⊂ R2 , with |S| = 2 and |T | = 4, such that VT (S) = F . Proof. First, looking at Fig. 11, where F is depicted as the shaded region, we obtain the point B as the intersection of the unbounded sides of the convex quadrilateral with vertices CAD. We denote ^CAD = α and ^CBD = β and observe that π > α > β > 0. We next draw the lines that make angles π − α with AB at the point A and those that make angles β with the same segment at B. We then get the points t1 and t2 as the two other vertices of the quadrilateral determined by these four lines. We take s1 and s2 as the symmetric points of t1 with respect to CA and CB, respectively. To see that 25 Figure 11: Configuration for a general unbounded quadrilateral VT (S) = F for S := {s1 , s2 } and T := {s1 , s2 , t1 , t2 } , the only thing that we have to prove is that t2 s1 ⊥AD and t2 s2 ⊥BD. The pòint B is the center of the circle passing through the points t1 , t2 and s2 . Therefore, ^t1 s2 t2 = π − β, which, looking at the quadrilateral C2 s2 D2 B, implies that t2 s2 ⊥BD. The point A is the center of the circle passing through the points t1 , t2 and s1 . Therefore, ^t1 s1 t2 = π − α, which, looking at the quadrilateral C1 s1 D1 A, implies t2 s1 ⊥AD. 4 Conclusions We have obtained constructive characterizations of properties pertaining to higher-order Voronoi cells, and applied these characterizations to a case study of cells of order at least two in the system of four sites. In particular, the results obtained in the preceding subsections show that for S ⊂ T ⊂ R2 , with |S| = 2 and |T | = 4, the resulting cell VT (S) can be any of the following sets: the empty set, a singleton, a non-cyclic bounded convex quadrilateral, a halfplane, an intersection of parallel halfplanes with opposite normals and a nonempty interior, an angle, an unbounded polygon with non- parallel sides and just two vertices, or an unbounded convex quadrilateral. All the remaining possibilities for sets in R2 de ned by four linear inequalities, namely, a singleton, a one-dimensional set, a triangle, a cyclic quadrilateral, and an unbounded quadrilateral with parallel sides and just two vertices are 26 unfeasible. The restrictions on the possible shapes of higher-order cells discovered in our case study are consistent with the challenges encountered in the design of numerical methods for constructing higher-order cells (cf. [14]), where the key assumption of general position ensures the absence of cyclic quadrilateral configurations). Thus a natural direction for the future study is to obtain general structural results on the shapes of higher-order cells, which will in turn inform the design of algorithms. For instance, we would like to know whether the convex hull of affinely independent points can be represented as a higher-order Voronoi cell (generalizing our result on the impossibility of a triangular cell), what higher-dimensional configurations produce cells with empty interiors, and what are the possible dimensions of higher-order Voronoi cells in Rn . 5 Acknowledgments We are grateful to the two JOTA referees for their thoughtful and thorough corrections and suggestions, including the proof of Proposition 3.10. These corrections have greatly improved the quality of our paper. The first author was supported by the MINECO of Spain, Grant MTM2014- 59179-C2-2-P, and the Severo Ochoa Programme for Centres of Excellence in R&D [SEV-2015-0563]. He is affiliated to MOVE (Markets, Organiza- tions and Votes in Economics). He thanks The School of Mathematics and Statistics of UNSW Sydney for sponsoring a visit to Sidney to complete this work. The second author is grateful to the Australian Research Council for con- tinuous financial support via grants DE150100240 and DP180100602, which in particular sponsored a trip to Barcelona that initiated this collaboration. The third author was partially supported by MINECO of Spain and ERDF of EU, Grant MTM2014-59179-C2-1-P, and Sistema Nacional de In- vestigadores, Mexico. References [1] Shamos, M., Hoey, D.: Closest-point problems. 16th Annual Symposium on Foundations of Computer Science (sfcs 1975) pp. 730–743 (1975) [2] Papadopoulou, E., Zavershynskyi, M.: On higher order Voronoi dia- grams of line segments. In: Algorithms and computation, Lecture Notes in Comput. Sci., vol. 7676, pp. 177–186. Springer, Heidelberg (2012) 27 [3] Goberna, M.A., Martı́nez-Legaz, J.E., Vera de Serio, V.N.: The Voronoi inverse mapping. Linear Algebra Appl. 504, 248–271 (2016) [4] Mallozzi, L., Puerto, J.: The geometry of optimal partitions in location problems. Optim. Lett. 12(1), 203–220 (2018) [5] Gemsa, A., Lee, D.T., Liu, C.H., Wagner, D.: Higher order city Voronoi diagrams. In: Algorithm theory—SWAT 2012, Lecture Notes in Comput. Sci., vol. 7357, pp. 59–70. Springer, Heidelberg (2012) [6] Kaplan, H., Mulzer, W., Roditty, L., Seiferth, P., Sharir, M.: Dynamic planar Voronoi diagrams for general distance functions and their al- gorithmic applications. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2495–2504. SIAM, Philadelphia, PA (2017) [7] Klein, R.: Abstract Voronoı̆ diagrams and their applications (extended abstract). In: Computational geometry and its applications (Würzburg, 1988), Lecture Notes in Comput. Sci., vol. 333, pp. 148–157. Springer, New York (1988) [8] O’Neil, P., Wanner, T.: Analyzing the squared distance-to-measure gra- dient flow system with k-order voronoi diagrams. Discrete & Computa- tional Geometry (2018) [9] Qiu, C., Shen, H., Chen, K.: An energy-efficient and distributed co- operation mechanism fork-coverage hole detection and healing in wsns. IEEE Transactions on Mobile Computing 17(6), 1247–1259 (2018) [10] Giansiracusa, N., Ricciardi, C.: Spatial analysis of U.S. Supreme Court 5-to-4 decisions (2018) [11] Kolahdouzan, M., Shahabi, C.: Voronoi-based k nearest neighbor search for spatial network databases. In: Proceedings of the Thirtieth Interna- tional Conference on Very Large Data Bases - Volume 30, VLDB ’04, pp. 840–851. VLDB Endowment (2004) [12] Goberna, M.A., López, M.A.: Linear semi-infinite optimization, Wiley Series in Mathematical Methods in Practice, vol. 2. John Wiley & Sons, Ltd., Chichester (1998) [13] Goberna, M.A., Lopez, M.A., Todorov, M.: Stability theory for linear inequality systems. SIAM J. Matrix Anal. Appl. 17(4), 730–743 (1996) 28 [14] Zavershynskyi, M., Papadopoulou, E.: A sweepline algorithm for higher order Voronoi diagrams. In: 2013 10th International Symposium on Voronoi Diagrams in Science and Engineering, pp. 16–22 (2013). DOI 10.1109/ISVD.2013.17 29