Averaging the k largest distances among n: k-centra in Banach spaces

ARTICLE IN PRESS UNCORRECTED PROOF S0022-247X(03)00845-X/FLA AID:9036 Vol.•••(•••) ELSGMLTM(YJMAA):m1 2003/11/25 Prn:27/11/2003; 13:15 yjmaa9036 P.1 (1-11) by:ML p. 1 J. Math. Anal. Appl. ••• (••••)•••–••• www.elsevier.com/locate/jmaa 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 Averaging the klargest distances among n: k-centra in Banach spaces Pier Luigi Papini1and Justo Puerto∗,2 Received 4 November 2002 Submitted by J.B. Conway Abstract Given a Banach space Xlet A⊂Xcontaining at least kpoints. In location theory, reliability analysis, and theoretical computer science, it is useful to minimize the sum of distances from the k furthest points of A: this problem has received some attention for Xa finite metric space (a network), see, e.g., [Discrete Appl. Math. 109 (2001) 293]; in the case X=En,k=2or3,andAcompact some results have been given in [Math. Notes 59 (1996) 507]; also, in the field of theoretical computer science it has been considered in [T. Tokuyama, Minimax parametric optimization problems in multidimensional parametric searching, in: Proc. 33rd Annu. ACM Symp. on Theory of Computing, 2001, pp. 75–84]. Here we study the above problem for a finite set A⊂X, generalizing—among others things—the results in [Math. Notes 59 (1996) 507]. 2003 Published by Elsevier Inc. 1. Introduction Let Xbe a Banach space; let A={a1,...,a n}⊂X,n⩾3, ai= ajfor i= j, a finite set whose cardinality will be denoted by #A. Also, we denote by δ(A) the diameter of A. Given x∈X,letσ(x) =(σ1(x), . . . , σn(x)) be an ordering of the elements of {1,2,...,n}such that x−aσ1(x)⩾x−aσ2(x)⩾···⩾x−aσn(x). Given an integer k,1⩽k⩽n,weset: rk(A, x) =1 k k  i=1 x−aσi(x)and rk(A) =inf x∈Xrk(A, x). *Corresponding author. E-mail address: [email protected] (J. Puerto). 1The research of the first author was partially supported by the Italian national group G.N.A.M.P.A. 2The author thanks Spanish ministry of Science and Technology through grant number BFM2001-2378. 0022-247X/$ – see front matter 2003 Published by Elsevier Inc. doi:10.1016/j.jmaa.2003.11.011 ARTICLE IN PRESS UNCORRECTED PROOF S0022-247X(03)00845-X/FLA AID:9036 Vol.•••(•••) ELSGMLTM(YJMAA):m1 2003/11/25 Prn:27/11/2003; 13:15 yjmaa9036 P.2 (1-11) by:ML p. 2 2P.L. Papini, J. Puerto / J. Math. Anal. Appl. ••• (••••)•••–••• 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 Clearly, r1(A) is the Chebyshev radius of A, that we shall also denote by r(A), while rn(A) is the minimum averageof distances from the points of A, usually denoted by µ(A). (We also use this notationwhen referringto others’ results.) A point x(when it exists) such that rk(A, x) =rk(A) will be called a k-centrum of A. In particular, a 1-centrum of Ais a (Chebyshev) center; an n-centrum of Ais a median (or Fermat point). The term k-centrum was coined in the early seventies[15] to refer to the minimization of the function rk(A, x) when Xis a finite metric space. The reader should notice that this term (k-centrum) differs from n-center as it is used in recent papers. In the latter, n-center means center or median for n-point sets or n-flat of a given finite set. In this paper, we study the functions rk(A, x) and the k-centra; these problems, apart from some results given in [23], have been also considered in [11,15,16] from an algorithmic point of view. The interested reader can also find different applications of these functions in different areas of applied mathematics as reliability: optimization of systems k-out-of-n[1]; location analysis [13] or in decision theory [22], among others. 2. Preliminary results We start with a simple remark;clearly, given a finite set A={a1,...,a n},foranyx∈X we have r1(A, x) ⩾r2(A, x) ⩾···⩾rn(A, x). From this we have the following remark. Remark 2.1. For any Awe have r(A) ⩾r2(A) ⩾···⩾rn−1(A) ⩾µ(A). (1) Remark 2.2. We can also give estimates in the “opposite” sense. Let 1 ⩽k⩽j⩽n. Given any A={a1,...,a n},foreveryx∈Xwe have krk(A, x) =k i=1x−aσi(x)⩽ j i=1x−aσi(x)=jrj(A, x);taking infimum on x, we obtain krk(A) ⩽jrj(A). (2) A better estimate is the following (whose proof is almost trivial) proposition. Proposition 2.1. Given A={a1,...,a n},letn⩾2hwith han integer 1⩽h⩽n/2.Ifi, j is a pair of indexes such that ai−aj=δ(A),setA1=A\{ai,aj};then let i1,j 1be indexes such that ai1,aj1∈A1and ai1−aj1=δ(A1);then define A2=A1\{ai1,aj1}. Proceeding in this way, we obtain 2hr2h(A) ⩾δ(A) +δ(A1)+δ(A2)+···+δ(Ah−1). (3) The next result gives us some structural properties of the rk(A, x) function. They are direct consequences of basic properties of the norm in Xand thus, its proof is left out. ARTICLE IN PRESS UNCORRECTED PROOF S0022-247X(03)00845-X/FLA AID:9036 Vol.•••(•••) ELSGMLTM(YJMAA):m1 2003/11/25 Prn:27/11/2003; 13:15 yjmaa9036 P.3 (1-11) by:ML p. 3 P.L. Papini, J. Puerto / J. Math. Anal. Appl. ••• (••••)•••–••• 3 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 Proposition 2.2. Let A={a1,...,a n}and let kbe an integer 1⩽k⩽n;then the function rk(A, x) (x∈X)is 1-Lipschitz continuous and convex. Moreover, if Xis strictly convex, rk(A, x) is strictly convex outside lines containing at least kpoints of A. Given A,letforε⩾0and1⩽k⩽n=#A, sk(A, ε) =x∈X:rk(A, x) ⩽rk(A) +ε.(4) According to Proposition 2.2, the sets sk(A, ε) are always closed and convex. Also, in a dual space, the functions x→x−aare weak∗-lower semicontinuous, so the sets sk(A, ε) are bounded, w∗-closed, and w∗-compact. Therefore, the (possibly empty) set sk(A) = ε>0 sk(A, ε) (5) is always closed, bounded, and convex, and its elements are the k-centra of A, i.e., the points xsuch that rk(A, x) =rk(A). By standard w∗-compactness arguments we obtain the following proposition. Proposition 2.3. If Xis a dual space (in particular, if Xis reflexive),thensk(A) =∅for any finite set Aand any kbetween 1and #A. Remark 2.3. The above result is true, for example, if X=l∞. Also, the same result holds if Xis norm-one complemented in X∗∗. The proof in the case of existence of norm-one projection is simple (and obtains following the line of proofs in [19]). General results of this type have been given in [19]. Next result shows that also other spaces have the same properties. Theorem2.1.If X=c0,thenforevery A={a1,...,a n}and1⩽k⩽nwehavesk(A) =∅. Proof. We may consider Aas a subset of l∞.Sincel∞is a dual space, there exists x= (x(1),x(2),...,x(n),...)∈l∞such that rk(A, x) =inf{rk(A, y):y∈l∞}.Since Ais in c0 there exists an index hsuch that |a(j) i|⩽x−aσk(x),forallj>hand i=1,...,n. Then, x0=(x(1),...,x(h),0,...,0,...)∈c0and x0−ai⩽supsupa(j) i:j>h ,supx(j) −a(j) i:j⩽h⩽x−aσk(x), for i=1,...,n. Hence, rk(A, x0)⩽x−aσk(x)⩽rk(A, x) =rk(A) and so rk(A, x0)= rk(A).✷ Remark 2.4. There are spaces where for some finite sets, centers and/or medians do not always exist; one of these spaces is a hyperplane of c0considered in [12]. (This does not contradict Theorem 2.1.) Examples of four-point sets with a center but without median, or with a median but without a center are indicated in [12,20]. Examples of three-point sets without k-centra for any kare shown at the end of this paper. ARTICLE IN PRESS UNCORRECTED PROOF S0022-247X(03)00845-X/FLA AID:9036 Vol.•••(•••) ELSGMLTM(YJMAA):m1 2003/11/25 Prn:27/11/2003; 13:15 yjmaa9036 P.4 (1-11) by:ML p. 4 4P.L. Papini, J. Puerto / J. Math. Anal. Appl. ••• (••••)•••–••• 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 Remark 2.5. Let A⊂F,Acontaining at least kpoints, Ffinite. Then rk(A, x) ⩽rk(F, x) for all x∈X,andsork(A) ⩽rk(F ) (1⩽k⩽#A). Also, if rk(A) =rk(F ),thensk(A) ⊂ sk(F ). Remark 2.6. If mk∈sk(A) and cis a center of F, then we have the almost trivial estimate mk−c⩽d(A,mk)+r(A), (6) where d(A,mk)=infx∈Ax−mkdenotes the distance of mkfrom the set A.Infact,if mk−ai=d(A,mk),thenwehave mk−c⩽mk−ai+ai−c⩽d(A,mk)+r(A). Remark 2.7. It is clear that x∈sn(A) and x−ai=constant i=1,2,...,n, implies x∈s1(A). (See, for example, [3] for results of this type.) More generally, if ck∈sk(A) and the kfarthest points to ckin Aare at the same distance rkfrom ck,thenwehave r(A) ⩽r(A,ck)=rk(A);sofori=1,...,k,ri(A) =rk(A),andthenck∈si(A). 3. General results on k-centra We start with a general result concerning k-centra, which generalizes results contained in [23], well-known for k=#A. Theorem 3.1. Let Xbe a strictly convex space and A⊂X;if kis odd, then sk(A) (1 ⩽ k⩽n)contains at most one point;if kis even and sk(A) contains xand x,x= x,then there exist (at least)kpoints of Aon the line passing through xand x. Proof. Given A={a1,...,a n}and k,1⩽k⩽n,ifx,x belong to sk(A), then according to the convexity of sk(A) also x=(x+x)/2 belongs to sk(A).Leta1,...,a kbe the k points of Afurthest away to xand x,sothatk i=1x−ai=krk(A). Then, we have krk(A) = k  i=1    x+x 2−ai    ⩽ k  i=1x−ai 2+x −ai 2 ⩽krk(A, x) 2+krk(A, x) 2=krk(A), so all these inequalities are equalities. This means two facts: (1) a1,...,a kare also the k points in Afurthest to x;and(2)x−ai=λi(x −ai)for some non-negative λi,i=1, ...,k; therefore x,x,a1,...,a kare all collinear. This is impossible for kodd because in this case the unique median of A={a1,...,a k}is the only point of Aleaving (k −1)/2 points of a1,...,a kto each side (“centralpoint”); for keven, all points letting k/2 on each side are medians of A.✷ Remark 3.1. The proof of the above theorem shows that if Xis a strictly convex space and A⊂X,if#Ais odd, or #Ais even and does not contain kcollinear points, then sk(A) (1⩽k⩽n) contains at most one point. (The last result follows also from Proposition 2.2.) ARTICLE IN PRESS UNCORRECTED PROOF S0022-247X(03)00845-X/FLA AID:9036 Vol.•••(•••) ELSGMLTM(YJMAA):m1 2003/11/25 Prn:27/11/2003; 13:15 yjmaa9036 P.5 (1-11) by:ML p. 5 P.L. Papini, J. Puerto / J. Math. Anal. Appl. ••• (••••)•••–••• 5 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 When k=2 we have no uniqueness result. (See Remark 3.3 below.) Theorem 3.2. For any A⊂Xwe have r(A)=r2(A). Proof. Assume by contradiction, that r2(A) < r(A) for some A={a1,...,a n}.Take x∈Xsuch that r2(A, x) =r(A) −σfor some σ>0; we have r(A,x) ⩾r(A) (by definition) so there exists ai∈Asuch that x−ai⩾r(A). For any aj∈A,j= i,wehave x−ai+x−aj 2⩽r2(A, x) =r(A)−σ, so x−aj⩽2r(A)−2σ−x−ai⩽2r(A)−2σ−r(A) =r(A)−2σ. If xλ=λai+(1−λ)x,0⩽λ⩽1, then we have xλ−x=λai−x; 1 2ai−xλ+xλ−aj⩽1 2ai−x−x−xλ+xλ−x+x−aj ⩽r(A)−σfor all j= i. Choose λ∈(0,1)so that xλ−ai=r(A)−σ; we obtain, for all j= i xλ−aj⩽2r(A)−σ−ai−xλ=2r(A)−2σ−r(A)−σ=r(A)−σ; therefore r(A,xλ)⩽r(A)−σ, a contradiction. ✷ Remark 3.2. In general, in any space, we have r3(A) < r2(A) for some A: for example, also in the Euclidean plane E2, there are three-point sets where the center and the median do not coincide. We have proved(Theorem 3.2)that r1(A) =r2(A) always. On the contrary,the equality rk(A) =rk+1(A) for k⩾2 does not happen frequently and it has some strong implications. We shall discuss now this fact, giving a converse of Remark 2.7. Theorem 3.3. Let rk(A) =rk+1(A) for some k⩾1and A={a1,...,a n};n>k.Then sk(A) ⊂sk+1(A).(In particular, by Theorem 3.2,ifcis a center of A,thenc∈s2(A).) Moreover, if ck∈sk(A),then(at least)the k+1points of Awhich are farthest to ckhave the same distance rk(A) from it;in addition, for i=1,...,k,ri(A) =rk(A);ck∈si(A); si(A) ⊂si+1(A).(Note that if Xis strictly convex, then sk+1(A) is a singleton for k⩾2 since the k+1points farthest to ckare not collinear.) Proof. Let rk(A) =rk+1(A);ck∈sk(A). Order the elements of Aso that ck−a1⩾ ck−a2⩾···⩾ck−an;wehave rk(A) =1 k k  i=1 ck−ai⩾1 k+1 k+1  i=1 ck−ai=rk+1(A, ck)⩾rk+1(A). ARTICLE IN PRESS UNCORRECTED PROOF S0022-247X(03)00845-X/FLA AID:9036 Vol.•••(•••) ELSGMLTM(YJMAA):m1 2003/11/25 Prn:27/11/2003; 13:15 yjmaa9036 P.6 (1-11) by:ML p. 6 6P.L. Papini, J. Puerto / J. Math. Anal. Appl. ••• (••••)•••–••• 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 Therefore, our assumption implies that ck∈sk+1(A); moreover, 1 k+1k  i=1 ck−ai+ck−ak+1=1 k k  i=1 ck−ai implies ck−ak+1 k+1=1 k−1 k+1k  i=1 ck−ai= rk k+1, so ck−ak+1=rk(A); but then, since ck−ak+1⩽min 1⩽i⩽kck−ai⩽1 k k  i=1 ck−ai=rk(A), ck−a1=···=ck−ak=ck−ak+1. By recalling Remark 2.7, we obtain the conclusion. ✷ Remark 3.3. In general, also if Xis the Euclidean plane, a 2-centrum of Ais not a center: for example, if A={(0,1);(0,−1);(ε, 0)},0⩽ε⩽1, then the unique center of Ais the origin, while all points (0,α);|α|⩽(1−ε2)/2, are 2-centra. Remark 3.4. If Ahas at most one (k +1)-centrum and rk(A) =rk+1(A),thenx∈ sk+1(A) ⇒sk(A) ⊆{x}. Without the assumption of uniqueness on sk+1(A) this is not true, as the following example shows. Let Xbe the plane with the max norm, and A={(−9 10,0);(11 10,1);(−9 10,−1)};wehaver2(A) =r3(A) =1; P=(1 10,0)belongs to s2(A) ⊂s3(A); the origin belongs to s3(A) but not to s2(A). Our next result, whose proof follows from the definition of rk(A), extends [3, Proposition 2.7]. Theorem 3.4. Let mk∈sk(A),mj∈sj(A),max{k,j}⩽n=#A. Then we have mk−mj⩽rk(A) +rj(A). (7) In particular, if j=kand {mk,m  k}⊂sk(A),then  mk−m k ⩽2rk(A). (8) Remark 3.5. The estimates (7) and (8) are sharp.(See [3, Example 2.9].) But if we assume that Xis strictly convex, then we have better estimates. In fact, according to Remark 3.1, in this case (for k= 2) we have uniqueness of solutions in many cases. But for k= jwe cannot give better inequalities (see [4, §4]) apart from the fact that strict inequality holds in both (7) and (8). Now assume that we have equality in (7). Looking at the proof of Theorem 3.4, we obtain subsequently; for the jfarthest points to mj,ai,i=1,2,...,j,wehave mj−ai+ai−mk=mj−mk;thejfarthest points to mk, all have distance rk(A, mk)from it; therefore, if j>kthen rk(A) =rj(A) and both mkand mjbelong ARTICLE IN PRESS UNCORRECTED PROOF S0022-247X(03)00845-X/FLA AID:9036 Vol.•••(•••) ELSGMLTM(YJMAA):m1 2003/11/25 Prn:27/11/2003; 13:15 yjmaa9036 P.7 (1-11) by:ML p. 7 P.L. Papini, J. Puerto / J. Math. Anal. Appl. ••• (••••)•••–••• 7 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 to sj(A).Ifj=k, then the kfarthest points to mj[mk] are on the sphere of radius rk centered at mj[respectively at mk]; moreover the distance between the centers of the two balls is twice the radius rk. In the following we consider a localization property of the k-centra with respect to co(A), the convex hull of the set A. Theorem 3.5. If Xis a two-dimensional space, or if Xis a Hilbert space, then for any A and any k(1 ⩽k⩽#A), it holds sk(A) ∩co(A) =∅. Moreover, if Xis a Hilbert space, or if dim(X) =2and Xis strictly convex, then sk(A) ⊂co(A). Proof. The assumptions imply that sk(A) =∅.Ifdim(X) =2then(see[21]) for every x∈Xthere exists x∗∈co(A) such that x∗−a⩽x−afor any a∈A;i.e.,x∗−ai⩽ x−aifor i=1,...,n=#A,sork(A, x∗)⩽rk(A, x):ifwetakex∈sk(A), this shows that there also exists x∗∈sk(A) ∩co(A). Now let Xbe Hilbert or if dim(X) =2, Xstrictly convex; if x/∈co(A),letx∗be the best approximation to xfrom co(A):wehavex∗−ai<x−aifor i=1,...,n,so rk(A, x∗)<r k(A, x), thus an element of sk(A) must belong to co(A).✷ Corollary 3.1. Let Xbe Hilbert or if dim(X) =2,Xstrictly convex;given A⊂Xwith no subset of kpoints being collinear, if mk∈sk(A) and c∈s1(A),thenmk−c=r(A) implies that mk∈A. Proof. Follow the line of the proof of [4, Proposition 5.1]. ✷ Anotherinterestingpropertyof k-centraof aset Aisthat they allow to characterize inner product spaces in terms of their intersection with the convex hull of A. Characterizations of this type are known from the sixties. (See [8,9].) The same propertyconcerning medians was considered in the nineties by Durier [7], where partial answers were given. It has been proved only recently for medians of three-point sets, this result can be found in [6]. Theorem 3.6. If dim(X) ⩾3and the norm of Xis not hilbertian, then there exists a threepoint set Asuch that s3(A) ∩co(A) =∅. By using such theorem, it is not difficult to obtain the following proposition. Proposition 3.1. If dim(X) ⩾3and the norm of Xis not hilbertian, then for every n⩾3 there exists an n-point set Fsuch that s3(F ) ∩co(F ) =∅. Proof. We prove the result for n=4, the extension to n⩾4 being similar. Under the assumptions done,according to Proposition 2.2, infx∈co(A) r3(A, x) is always attained; now take A={a1,a2,a3}as given by Theorem 3.6: for some σ>0wehave inf x∈co(A) r3(A, x) =r3(A) +4σ>r 3(A). ARTICLE IN PRESS UNCORRECTED PROOF S0022-247X(03)00845-X/FLA AID:9036 Vol.•••(•••) ELSGMLTM(YJMAA):m1 2003/11/25 Prn:27/11/2003; 13:15 yjmaa9036 P.8 (1-11) by:ML p. 8 8P.L. Papini, J. Puerto / J. Math. Anal. Appl. ••• (••••)•••–••• 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 Take ¯x∈Xsuch that r3(A, ¯x) < r3(A)+σ; it is not a restriction to assume that ¯x−a3⩽ min{ ¯x−a1,¯x−a2}.Nowtakea4/∈Asuch that a3−a4⩽σand let F=A∪{a4}. We have r3(F, ¯x) ⩽r3(A, ¯x) +σ⩽r3(A) +2σ.Nowtakey∈co(F ):thereisx∈co(A) such that x−y⩽σ; therefore |r3(F, y) −r3(F, x)|⩽σ,sor3(F, y) ⩾r3(F, x) −σ⩾ r3(A, x) −σ⩾r3(A) +3σ; thus inf y∈co(F ) r3(F, y) ⩾r3(A) +3σ⩾r3(F, ¯x) +σ⩾r3(F ) +σ, this proves the thesis. ✷ Given a set Awith npoints and k<n, we can divide the space Xinto n kregionsRj,so that when xis taken in one of these regions, the same kpoints of Aare the farthest to x;of course, inside each of these regions there are k!different possible orderings σ1,...,σ k.It is possible to have Ri∩Rj=∅(the values of the kth distance can be equal to the (k +1)th one); also, if Rjis determined by a1,...,a kthen ai/∈Rjfor i=1,...,k. Also in general the medians of a1,...,a k(if they exist) do not belong to Rj. Note that these regions are not in general convex: for example, if Xif the plane with the max norm, given a1=(1,0) and a2=(−1,0),thesetx−a1⩾x−a2is notconvex.But the same is true, for some pair, in any space with a non-hilbertian norm. If Xis a Hilbert space, then the regions Rjare convex:in fact, consider, e.g., the region Rdetermined by the points a1,...,a k,k<#A:then R= k  i=1x∈X:x−ah⩽x−aifor h=k+1,...,n . Ris the intersection of k(n −k)-convex regions, therefore it is convex. A detailed analysis of these sets can be found in [13]. (Not only for Hilbert spaces.) Also in the particular case of two-dimensional spaces some geometrical properties as well as the complexity analysis are given in [14]. Minimizing rk(A) is equivalent to solve n kconstrained Fermat problems; then looking for the minimum of the values obtained: for each Rj, determined by kgiven points, say {a1,...,a k}, look for a median of these points, restricted to the “feasible region” Rj.Algorithms for the solution of this kind of problems in two-dimensional spaces can be found in [14]; also, in networks (finite metric spaces) algorithms are given in [10,16]. Given X, consider for k∈Nthe parameter Jk(X) =sup2rk(A) δ(A) :A⊂Xfinite, max{2,k}⩽#A.(9) For k=1, the number J1(X) =J(X) is called the finite Jung constant and has been studied intensively; in general, 1 ⩽J(X)⩽2, while the value of J(X) gives information on the structure of X. As shown partially in [5] and later completely in [18], we always have J(X)=sup2µ(A) δ(A) :A⊂Xfinite, 2 ⩽n=#A. Since µ(A) ⩽rk(A) ⩽r(A) always (see (1)), we obtain the following result. ARTICLE IN PRESS UNCORRECTED PROOF S0022-247X(03)00845-X/FLA AID:9036 Vol.•••(•••) ELSGMLTM(YJMAA):m1 2003/11/25 Prn:27/11/2003; 13:15 yjmaa9036 P.9 (1-11) by:ML p. 9 P.L. Papini, J. Puerto / J. Math. Anal. Appl. ••• (••••)•••–••• 9 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 Theorem 3.7. In every space X, for every positive integer k, we have Jk(X) =J(X). (10) Our last result in this section was already known for medians (see [4]) but it can be extended to general k-centra. Proposition 3.2. Let mk∈sk(A) for some set A. Assume that Ak⊂A,#Ak=kand rk(A) =1 ka∈Akmk−a.Ifmk−1 ka∈Aka=rk(A) then Xis not strictly convex. Proof. By the triangular inequality we have rk(A) =    mk−1 k a∈Ak a    ⩽1 k a∈Ak mk−a=rk(A). Thus, mkis also a center of Akand rk(A) =r(Ak). Now, we apply first claim in [4, Proposition 3.1]tothesetAkto get the result. ✷ 4. Concluding remarks To conclude our analysis of k-centra, we study several properties of these points regarding equilateral sets. Recall that Ais called equilateral if ai−aj=constant for i= j,1⩽i, j ⩽n=#A. Also, recall that the centroid of a finite set Aisgivenbythe point 1 #Aa∈Aa. For equilateral sets there are several nice properties connecting centers, medians and centroids (see [2]). Some of them can be extended further to k-centra. Proposition 4.1. Let Abe an equilateral set in an inner product space Xand let k⩾3; then the centroid of Abelongs to sk(A). Proof. Assume that 0 is the center of A;thenai,aj=constant for i= j,1⩽i, j ⩽ n=#A.Lety=n j=1λjaj; then the function f(λ 1,...,λ n)=k i=1y−aiis symmetric. In Hilbert spaces it always exists mk∈sk(A) ∩co(A). Moreover, under the hypothesis of the proposition sk(A) is a singleton, then mkis the unique minimizer of fand λ1= λ2=···=λn=1/n; thus mkis the centroid of A.✷ Remark 4.1. Let A={a1,...,a n}be an equilateral set with ai−aj=d,∀i= j;then it is easy to see that rk(A, x) ⩾d 2for any x∈X. Indeed, for any x∈X,krk(A, x) is attained as a sum of distances from xto kpoints of A. Let us denote by Ak(x) the subset of Acontaining the points that define rk(A, x).Ak(x) itself is an equilateral set with ai−aj=d,∀i= j,ai,aj∈Ak(x);then krk(A, x) = a∈Ak(x) a−x⩾kd 2,