{'fraction_non_alphanumeric': 0.04820791574656022, 'fraction_numerical': 0.008561236623067776, 'mean_word_length': 3.701485385721131, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 13, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A geometric characterisation of the quadratic min-power centre

For a given set of nodes in the plane the min-power centre is a point such that the cost of the star centred at this point and spanning all nodes is minimised. The cost of the star is defined as the sum of the costs of its nodes, where the cost of a node is an increasing function of the length of its longest incident edge. The min-power centre problem provides a model for optimally locating a cluster-head amongst a set of radio transmitters, however, the problem can also be formulated within a bicriteria location model involving the 1-centre and a generalized Fermat-Weber point, making it suitable for a variety of facility location problems. We use farthest point Voronoi diagrams and Delaunay triangulations to provide a complete geometric description of the min-power centre of a finite set of nodes in the Euclidean plane when cost is a quadratic function. This leads to a new linear-time algorithm for its construction when the convex hull of the nodes is given. We also provide an upper bound for the performance of the centroid as an approximation to the quadratic min-power centre. Finally, we briefly describe the relationship between solutions under quadratic cost and solutions under more general cost functions.

The range assignment problem is a type of disk covering problem, where the centres of the disks are given nodes, the radii (r i ) of the disks are transmission ranges, and the directed graph induced by the disks (see Figure 1, where bidirected edges are depicted without arrows) must satisfy a given connectivity constraint whilst minimising r α i . The exponent α is called the path loss exponent and most commonly takes a value between 2 and 4, with α = 2 corresponding to transmission in free-space. For any α > 1 the range assignment problem is NP-hard, even in the case when only 1connectivity is required of the resultant network [13]. During the design or maintenance of ad hoc radio networks it is often pertinent to introduce relays or cluster-heads for the processing of aggregated data and for the improved routing efficiency that takes place in such hierarchical structures (see [7,18,20]). Solving the range assignment problem whilst allowing for the introduction of a bounded number of additional nodes anywhere in the plane constitutes a very general and highly applicable geometric network problem, which has only been solved in certain restricted settings (see for instance [3,4]). Since the optimal locations of the cluster-heads must be found, as well as the optimal assignment of ranges on the complete set of nodes, this so called geometric range assignment problem is at least as difficult as the classical range assignment problem. This paper considers the problem of optimally locating a single cluster-head amongst a given set of transmitters, where each transmitter can send and receive data directly from the cluster-head. Not only is this an interesting and applicable model in it own right, but it is also a necessary first step in understanding the local structure of optimal networks with multiple cluster-heads. The graph induced by the assignment of ranges, in this case, contains an undirected star with the cluster head as its centre and the complete set of transmitters as its leaves; see for instance Figure 1(b), where edges between transmitters are depicted as broken lines since they do not contribute to the cost (power) of the star.
In more formal terms we denote the given finite set of transmitters by X ⊂ R 2 and the cluster-head by s ∈ R 2 . The power of any x ∈ X is P x = s − x α and the power of s is P s = max{ s − x α : x ∈ X}, where · is the Euclidean norm. The total power of the system is denoted by P (s) = P s + x∈X P x , and a min-power centre of X is a point s * which minimises P (s). Minimising only P s is clearly equivalent to the 1centre problem, i.e., the problem of finding the centre of a minimum spanning circle for X. Minimising only P x is a generalised Fermat-Weber problem [5], which becomes the classical Fermat-Weber problem when α = 1 and the problem of constructing the centroid when α = 2.
A related concept in facility location is the computation of the center-median (or cent-dian) of a finite set of points [6], which also has applications in wireless ad hoc networks for finding a so called core node [9]. In this problem the task is to find all Pareto-optimal solutions to the vector function Φ(s) = (P s , P x ), which is equivalent to finding the optimal value of λP s + (1 − λ) P x for every λ ∈ [0, 1] (see [8,12]). Clearly the min-power centre will be optimal for this problem when λ = 1/2. The vector minimisation problem has also been considered for α = 1 in the rectilinear plane [15] and for α = 2 in the Euclidean plane [17]. These types of bicriteria models have been described as seeking a balance between the antagonistic objectives of efficiency (i.e., the minisum component) and equity (i.e., the minimax component).
There are numerical methods, for instance the sub-gradient method, that optimally locate s * to within any finite precision. However, structural results for the minpower centre problem, of the type described in this paper, are necessary for optimally constructing more complex geometric range assignment networks (which is the overarching goal of our research). This fact is particularly manifest in the design of algorithmic pruning modules, where one develops strategies based on properties of locally optimal structures for eliminating suboptimal network topologies from the exponential set of possible topologies. The ultimate benefits of good pruning modules has been demonstrated a number of times for problems similar to the geometric range assignment problem [3,4,21].
In this paper we mostly focus on the quadratic case, α = 2. In terms of cluster-head placement this means that radio transmission takes place in free space, that is, in an ideal medium with zero resistance. Path loss exponents close to 2 frequently occur in real-world wireless radio network scenarios. This is true for transmission in mediums of low resistance, and in mediums of higher resistance when there is a degree of beam forming (constructive interference) [14]. The quadratic case also applies to certain classical facility location problems, including the location of emergency facilities such as hospitals and fire stations [12,17,19]. Furthermore, as demonstrated in the final section, it is anticipated that theoretical developments in the α = 2 case will lead to solutions and approximations for other α > 1.
In Section 2 we provide definitions and set up a Karush-Kuhn-Tucker formulation of the min-power centre problem and its dual for any α > 1. When α = 2 the geometric construction of the min-power centre becomes tractable, allowing us to provide a characterisation of the solution in terms of the farthest point Voronoi diagram on X, and its dual, the farthest point Delaunay triangulation. This characterisation is described in Section 3, where we also present a new linear-time algorithm for the construction of the optimal quadratic min-power centre. For α = 2, Section 4 explores the significance of the centroid and the 1-centre of a set of points for the min-power centre problem, and provides a characterisation of point sets for which the min-power centre and the 1-centre coincide. Section 4 also provides a bound for the performance of the centroid as an approximation to the min-power centre. The final section briefly explores the general α > 1 case.

Definitions and analytical properties
Let X = {x i : i ∈ J} be a given finite set of points in the Euclidean plane with indexset J, and let α > 1 be a given real number. For any point s ∈ R 2 let G = G(s, X) be the undirected star with centre s and leaf-set X. The power of G with respect to s is denoted by where · is the Euclidean norm. The first terms of of P (s) can be thought of as representing the total power required by the existing transmitters for communicating with the cluster-head, while the second term can be thought of as the power required by the cluster-head for communicating with the transmitters.
Definition: The Euclidean min-power centre problem on X is the problem of finding a point s * α ∈ arg min s P (s). We refer to s * = s * α as a min-power centre of X.
Lemma 1 For any X the function P (s) is strictly convex, and therefore s * is unique.
Proof. This follows since s − x i α is strictly convex when α > 1.
Although P (s) is not smooth, it can be expressed as the maximum of a set of smooth functions: for any j ∈ J let F j (s) = F α j (s, Then is continuous. Therefore F j is continuously differentiable and convex, since it is the sum of such functions.
Next we describe a useful non-linear programming formulation of the problem of finding s * . Consider the following non-linear optimization program.
Clearly Problem P1 is smooth and convex. It is easy to see that (s, v) is optimal for this problem if and only if s = s * and v = P (s * ).
Proof. Note that for all j such that P (s) = F j (s).
By the previous lemma and the resulting KKT conditions it follows that the point (s * , v * ) ∈ R 2 × R is optimal for Problem P1 if and only if there exist multipliers λ * j ≥ 0, j ∈ J such that ∇v + j∈J λ * j (∇F j (s * ), −1) = 0 and λ * j (F j (s * ) − v * ) = 0 for all j ∈ J. Observe that Therefore we can state equivalent KKT conditions as follows: s * is the min-power centre of X if and only if there exists λ * j ≥ 0 such that Let n = |J| and let λ = (λ 1 , ..., λ n ). The dual of Problem P1 can be written as Finally, we can convert the dual problem to a more familiar form as follows. For Therefore an equivalent formulation of Problem D1 is: If τ * is optimal for Problem D1 then s * = s(τ * ) is optimal for Problem P1 and λ * = (n + 1)τ * − 1 gives the multipliers satisfying Equations (1)-(3). This final formulation is recognisable in that it is almost identical to the dual of the problem which is the well-known minimum spanning circle problem (see [10] for a derivation). The only two differences in these duals are Inequality (5), which will be replaced by τ j ≥ 0 for the minimum spanning circle problem, and the extra coefficient n + 1 of the objective function. In general, the restriction on domain specified by Inequality 5 leads to a non-trivial variation on the minimum spanning circle problem, however, as shown in the next section, for α = 2 there exists an interesting and useful geometric relationship between the minimum spanning circle problem and the min-power centre problem.
3 The geometry of α = 2 In order to study the geometry of the case where α = 2 we first rewrite the KKT conditions in terms of the 2-centroids of X.
Definition: Recall that the centroid (or centre of mass) of X, which we denote as M , is defined by M = 1 n j∈J x j . We define the set of 2-centroids of X to be the set For any X ⊆ conv(X) we denote (with a slight abuse of notation) the image of X under the above affine transformation by AX , which is a subset of conv(M). We also similarly employ A −1 for the inverse transformation.
In the quadratic case (where α = 2) we now write This equation implies that for any j we have M j = arg min In the case α = 2 a simplified set of KKT conditions for Problem P1 in total is By Condition 8 we have: Conditions (8)-(10) can be interpreted by means of a dual pair of planar geometric graphs. Firstly let V = V(X) be the farthest point Voronoi diagram on X. This is a partition of R 2 into maximal regions {V (x j ) : j ∈ J} such that s ∈ V (x j ) if and only x j is a farthest node from s. It is well-known that V (x) is non-empty if and only if x is an extreme point (i.e., a "corner") of conv(X). As is common practice, we will (without confusion) treat V both as a graph specified by the boundary edges, or as a partition of the plane. It is well known that V is a tree.
Let D = D(X) be a farthest point Delaunay triangulation of X, which is defined as a triangulation of X such that the circumcircle of any triangle contains all points of X. The farthest point Delaunay triangulation is the dual graph of V [11]. If V contains a vertex of degree more than 3 then D is not unique; in this case we let D be any farthest point Delaunay triangulation on X. Figure 3 illustrates an example of both these graphs. Figure 3: A farthest point Voronoi diagram (solid lines) and its dual (broken lines) on a set of eight nodes (black-filled circles) Therefore a 0-face is a vertex, a 1-face is an edge, and a 2-face is a region of V or D. The dual relationship between D and V defines a natural mapping from each b-face of D to a (2 − b)-face of V. In Figure 3 the 0-face x of D maps to the 2-face V (x) of V, and the 2-face D of D maps to the 0-face V D of V. Observe that dual 1-faces are always perpendicular to each other. If the maximum degree of V is at most 3 then the mapping between faces is a bijection. In the case of vertices of degree more than 3 we still get a bijection if we consider every such vertex as consisting of a number of degree 3 vertices connected by zero-length edges, where the topology is uniquely determined by the choice of D. The unique pairs in the bijection will be referred to as dual faces. For any b-face D of D we denote by V D its dual face. Formally the bijection is defined as Observe in Figure 3 that there exists a Delaunay triangle D 1 that strictly contains its dual face in V, depicted by the unlabelled empty circle. As will become clear below, this dual relationship is unique and, in fact, the unlabelled empty circle is the centre of the minimum spanning circle (called the 1-centre) of X. We will show that something similar holds for the min-power centre problem.
Before proving the main theorem, we note that it is often the case when solving minimax non-linear programs that a complete solution can be arrived at by considering the various combinations of functions which are potentially active at the optimal solution. Hence we introduce the following lemma which allows us to restrict the number of combinations. From now on it is assumed that the KKT set associated with s * is {λ * j : j ∈ J} = Λ ∪ {λ * j : j ∈ J\J * }, where λ * j > 0 if and only if j ∈ J * , and Λ = {λ * j : j ∈ J * } is of minimal cardinality. From the above proof it follows that there may be more than one choice for this minimal set of multipliers. For consistency we assume that the multipliers are chosen so that there exists a Delaunay face D ∈ D such that {x j : j ∈ J * } is the set of extreme points of D.
Let int(·) denote the interior of a closed region (b-face). For ease of notation we assume that int({x}) = x for any point x.
Theorem 6 A point s is the optimal min-power centre for X if and only if s ∈ int(AD) and s ∈ V D for some face D of D.
Proof. Suppose that s = s * is optimal and let R be the face (node, edge, or triangle) defined by R = conv({M j : j ∈ J * }). By complementary slackness we have s * − x j = max i∈J { s * −x i } for every j ∈ J * . Therefore the disk centred at s * and containing the points {x j : j ∈ J * } on its boundary covers all points of X. By the definition of farthest point Delaunay triangulations, A −1 R = conv({x j : j ∈ J * }) is a face of D. Since J * has minimal cardinality and s * is a convex combination of the extreme points of R we must have s * ∈ int(R). Finally, note that s * ∈ j∈J * V (x j ), which implies that s * is also an element of the dual face of A −1 R. Letting D = A −1 R proves necessity.
To prove sufficiency we assume that s ∈ int(AD) and s ∈ V D for some face D of D. Let J D = {j : M j is an extreme point of AD} and let {u j : j ∈ J D } be a set of positive weights such that u j = 1 and s = u j M j . Let {λ j : j ∈ J} be a set of multipliers such that λ i = u i for all i ∈ J D , and all other λ i = 0. We only need to show still that complementary slackness holds with respect to s, λ. Let x k be any point of X. Since V D is the dual of D we have s ∈ j∈J D V (x j ). Therefore if k ∈ J D then s−x k −max{ s−x i : i ∈ J} = 0. Therefore λ j ( s−x j −max{ s−x i : i ∈ J}) = 0 for all j ∈ J, which implies that s is optimal.  M ∈ int(V (x i )). Therefore i = r. Finally, suppose that M j ∈ V (x j ) for some j ∈ J. Then, also by Theorem 6, M j = s * . Therefore |Λ| = 1.
Corollary 8 If s * ∈ int(V (x j )) for some j ∈ J, then s * = M r .
The convention of using x r to represent the node of X farthest from M will hold throughout the rest of this paper. Using Theorem 6 it is possible to design a fast geometric algorithm for finding s * .

Algorithm
Input: the set of coordinates X Output: the point s * Ohsawa's algorithm [17] for finding the efficient solutions to the vector minimisation problem v-min Φ(s), where Φ(s) = (max{ s − x j }, F (s)), can also find s * . There is no theoretical gain in the runtime of our algorithm over the algorithm of Ohsawa, but with modifications our algorithm should perform better in practice. We provide an intuitive reason for this as follows. As is well-known, for any set of n points X the expected number of points that are extreme points of conv(X) is O(log n). Therefore the expected complexity of the farthest point Voronoi diagram does not increase very quickly as n increases. Now both M and s * are in conv(M), but conv(M) becomes smaller the more we increase n (note that M is contained in a disk of radius 1 n+1 M − x r ). Therefore we suggest that if we modify our algorithm so that it begins by checking edges and vertices of V close to M , that the expected number of steps before s * is found will be small for large n. In contrast, for a fixed polygon representing a convex hull, and a fixed point in the polygon representing a centroid, the cardinality of a set X with this convex hull and centroid will not affect the practical runtime of Ohsawa's algorithm. Of course, Ohsawa's algorithm could also be modified to begin with points close to M , but his paper presents no theoretical justification for doing this. 4 The significance of the centroid and the 1-centre to the min-power centre problem It is clear from the results so far that the centroid M plays a central role in the min-power centre problem when α = 2. In particular, it is intuitive that M is always relatively close to the min-power centre, s * , since both lie in conv(M). This fact leads to a theorem at the end of this section which places an upper bound on the performance ratio of approximating the min-power centre by the centroid. The fact that M is a "special" point in the min-power centre problem was also observed in [17], where it is shown that any Parato optimal solution to the vector minimisation problem v-min Φ(s) lies on a simple path connecting M and the 1-centre of X (recall that Φ(s) = (P s , F (s)), where P s = max{ s − x 2 : x ∈ X} and F (s) = x∈X s − x 2 ).
Interestingly, this path is piecewise linear, consisting of one segment joining M to a point on an edge of V, and with the remainder of the path lying on the edges of V. Since the min-power centre is Pareto optimal for v-min Φ(s) it follows that s * is also on this path. This brings us to a second question: what role does the 1-centre play in the min-power centre problem? We will address this question next before returning to the discussion on M .
Denote the 1-centre of X by C and let M * = {M j : j ∈ J * }, where, as before, J * is minimal. Therefore s * ∈ int(conv(M * )). The next lemma is given without proof as it follows from an argument similar to the proof of Theorem 6. Proof. Clearly |J * | > 1, since if |J * | = 1 then s * = M r , but M r and M are always distinct. Let X * = A −1 M * . Since M ∈ conv(M * ) we have, by Lemma 3, the fact that conv(M * ) does not intersect the exterior of conv(X * ). Therefore, since s * ∈ int(conv(M * )) it follows that s * ∈ int(conv(X * )). By letting D = conv(X * ) it follows from Lemma 9 that s * = C as required.
The converse of this result does not appear to hold, but we do have an interesting corollary. Our final result on the role of C in the min-power centre problem relates to point sets X that are more or less evenly distributed (with respect to distance) about their centroid. The proof utilises the formulation of Problem D1 , which, as mentioned before, is almost exactly the dual of the minimum spanning circle problem except that the domain of the τ j is further restricted by Inequality (5). Note that when α = 2 we can write Equation (7) as s = τ j x j since τ j = 1. Therefore, for α = 2 we have: Problem D2 (dual of the minimum spanning circle problem).
Consider an optimal solution τ * to Problem D2. Therefore s(τ * ) = C. If τ * j ≥ 1 n+1 for all j ∈ J then τ * must also be optimal for Problem D1 . By complementary slackness the fact that τ * j ≥ 1 Hence all points of X are concyclic about C. To see what the domain restriction τ * j ≥ 1 n+1 means geometrically we first need a lemma.

Lemma 12
If there exists affine weights τ j ≥ 1 n+1 such that s = τ j x j then s ∈ conv(M).
Proof. If τ j ≥ 1 n+1 for all j ∈ J then s = 1 n+1 x j + u j x j where u j ≥ 0 and u j x j u j = (n + 1) u j x j ; note that y ∈ conv(X). Hence where y is on the boundary of conv(X) and M, y, y are collinear. The result now follows from Lemma 3.
The converse of this lemma is not true in general, however, by similar reasoning we have: Lemma 13 If s ∈ conv(M) and s is equidistant from all nodes of X then there exists affine weights τ j ≥ 1 n+1 such that s = τ j x j .
Therefore we have the following final result on C, which follows directly from the above discussion and lemma.

Proposition 14
Suppose that C is equidistant from all points of X. Then C is the min-power centre of X if and only if C ∈ conv(M).
In some sense it seems we cannot say anything about the location of s * without involving M . In fact, let Q be a polygon with at most n extreme points. For any point set X with convex hull Q, if there is no restriction on the location of M then there is no restriction on the location of s * (except, of course, that s * must lie in Q). We make this notion clear in the next proposition before closing the section with a proof that the centroid is a good approximation for the min-power centre.
Proposition 15 For any point w ∈ int(conv(X)), where w is on a vertex or edge of V, there exists a set of points X such that the extreme points of conv(X) and conv(X ) coincide and such that the min-power centre of X is w. We introduce points to the interior of conv(X ) to get the final X , which means that V(X) = V(X ) throughout. Suppose that e is a portion of V (x a ) ∩ V (x b ) for some a, b. Then w is the min-power centre of X if and only if w also lies on the segment M a M b -therefore suppose that this is not the case. Let u = 1 2 (M a + M b ) and let y ∈ int(conv(X)) be a point on the line intersecting u and w such that w is between y and u; see Figure 5. Let ε = y − w > 0.We introduce m > 0 new nodes at the point y and, for j = a, b, let M j = 1 n+m+1 x j + my + i∈J x i . Clearly M j is the centre of mass of M j and y (weighted n + 1 and m respectively), and therefore M j divides the segment yM a into the ratio M a − M a : M a − y = m : n + 1; in fact, the segments x b x a , M b M a and M b M a are all parallel. In order for w to be optimal for the resultant X the segment M a M b must intersect w, which is equivalent to requiring that ε = 1 m (n + 1) w − u . The integer m can therefore be selected to be large enough so that the point y resulting from the subsequent value of ε will be in the convex hull of X.
In the case when w from the previous proposition lies in the interior of a region of V, a similar process will produce an optimal point arbitrarily close to w. It is also relatively straightforward to extend the proposition to the case where no two nodes may coincide, and to the case where all nodes of X are required to lie on the boundary of the convex hull of X. Any other interesting general restrictions on the location of s * that do not involve M would therefore probably be for sets of nodes in convex position (i.e., where every node is an extreme point). We leave this as an open question.
The centroid is very easy to calculate -it can be done in constant time given the locations of the x j . Corollary 18 shows that M is an appropriate point for approximating s * , especially in applications with large n. For any set of points X let To place an upper bound on ρ we first need a lemma. Recall once again that x r is the farthest node from M .
Proof. Therefore Proof. Recall that for any point y we denote by F (y) the sum F (y) = j∈J y − x i 2 .
Let x p ∈ X be a farthest node from s * . By the triangle inequality We now have Since k ≥ 1 we conclude that ρ(X) ≤ 1 2 n + 1 n 2 + 1 2 for any X. The above approximation is "good" in the following sense. Let X n be any set of n points.

A brief look at general α > 1
The situation when α = 2 is complicated by the fact that the level curves of the F j are no longer circular. In particular, this implies that there are no easily constructed and useful fixed points directly analogous to the M j . Even though the farthest point Voronoi diagram still plays a crucial role for general α, there is no simple dual structure analogous to the Delaunay triangulation. We may consider arg min s s − x j α (the generalised Fermat-Weber point) as an analogue for M , however, a compass and straight-edge construction of this point is almost certainly impossible since even the classical Fermat-Weber point is not constructible in this way (see [2]).
This section will show, however, that not all insights gained for the α = 2 case are lost when α = 2. In fact, there are several important uses for the mathematical machinery developed in the preceding sections. Firstly, as discussed in the introduction, path loss exponents close to α = 2 often occur in real radio network scenarios. It seems evident that s * (and even M ) will serve as a good approximation points for min-power centres based on α close to 2.
Also, some of the the results from the previous section, especially those involving the 1-centre C, are directly applicable for any α > 1. The conceptual framework that we present for proving these results consists of transforming the set X into a new set X(s) such that the general α > 1 min-power centre problem on X is transformed into the quadratic min-power centre problem on X(s). Preliminary research indicates that this framework will also be useful for the development of bounds on the performance of s * or the centroid as approximation points for general α. We first state some notation and a lemma. Recall, from Section 2, that the power of the star G centred at s with leaf-set X and for a given α is denoted P α (s, X), and that P α (s, X) = max j∈J {F α j (s, X)}. We also similarly generalise the definition of F (s) to F α (s, X). The point minimising P α (s, X) is now denoted by s * α . Next we describe the construction of the set X(s). Essentially, each vector x i − s is transformed into a vector x i (s) − s such that x i − s α−1 = x i (s) − s . The convex hull of the resultant set of nodes will therefore contain the convex hull of X when α ≥ 2, with the inverse of this property holding when α < 2. In formal terms, for any point s let Let M (s) be the centre of mass of X(s), and let M j (s) be the j-th 2-centroid of X(s). Some of these concepts are illustrated in Figure 6 for the set X(s) with s = C and α < 2.
Lemma 19 Let s be any point. Then s = s minimises P 2 (s, X(s )) if and only if s = s * α .
The next proposition is a direct generalisation of Proposition 14 and follows from the previous lemma. An example is illustrated in Figure 6. Proof. Suppose that s * α = C. Then, since s * α minimises P 2 (s, X(s * α )), we must have C = s * α ∈ conv({M j (s * α )}) = conv({M j (C)}) by KKT Condition (8). Next suppose that C ∈ conv({M j (C)}). Note that C is also the 1-centre of X(C) since all points are equidistant from C. Therefore C minimises P 2 (s, X(C)) by Proposition 14, and therefore minimises P α (s, X) by Lemma 19. This proposition can be strengthened, as shown the following result.
Proposition 21 If s * 2 is equidistant from all point of X then s * α = s * 2 .
As a final observation note that as α tends to infinity the longest edge incident to s * α dominates F α (s, X). Therefore, since C minimises max{ s − x j α }, and P α (s, X) = max{ s − x j α } + F α (s, X), we have the following result.

Conclusion
In this paper we solve the quadratic min-power centre problem in the Euclidean plane. We provide a complete geometric description and method of construction for the optimal point by means of farthest point Voronoi diagrams. The solution leads to various structural results relating the min-power centre to the centroid and the 1-centre, and, in particular, allows us to construct an explicit bound on the performance of the centroid as an approximation point. We anticipate that the mathematical machinery developed in this paper will be applied to an important fundamental model for the physical design of wireless ad hoc networks -namely the geometric range assignment problem where a bounded number of new nodes may be introduced anywhere in the plane. Preliminary research has demonstrated that the framework we develop in this paper will also be useful for problems with cost functions that are not quadratic.