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 P n:27/11/2003; 13:15 yjmaa9036 P.1 (1-11) by:ML p. 1 J. Ma h. Anal. Appl. ••• (••••)•••–••• www.else ie .com/loca e/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 A e aging he kla ges dis ances among n: k-cen a in Banach spaces Pie Luigi Papini1and Jus o Pue o∗,2 Recei ed 4 No embe 2002 Submi ed by J.B. Conway Abs ac Gi en a Banach space Xle A⊂Xcon aining a leas kpoin s. In loca ion heo y, eliabili y analysis, and heo e ical compu e science, i is use ul o minimize he sum o dis ances om he k u hes poin s o A: his p oblem has ecei ed some a en ion o Xa ini e me ic space (a ne wo k), see, e.g., [Disc e e Appl. Ma h. 109 (2001) 293]; in he case X=En,k=2o 3,andAcompac some esul s ha e been gi en in [Ma h. No es 59 (1996) 507]; also, in he ield o heo e ical compu e science i has been conside ed in [T. Tokuyama, Minimax pa ame ic op imiza ion p oblems in mul i- dimensional pa ame ic sea ching, in: P oc. 33 d Annu. ACM Symp. on Theo y o Compu ing, 2001, pp. 75–84]. He e we s udy he abo e p oblem o a ini e se A⊂X, gene alizing—among o he s hings— he esul s in [Ma h. No es 59 (1996) 507]. 2003 Published by Else ie Inc. 1. In oduc ion Le Xbe a Banach space; le A={a1,...,a n}⊂X,n⩾3, ai= aj o i= j, a ini e se whose ca dinali y will be deno ed by #A. Also, we deno e by δ(A) he diame e o A. Gi en x∈X,le σ(x) =(σ1(x), . . . , σn(x)) be an o de ing o he elemen s o {1,2,...,n}such ha x−aσ1(x)⩾x−aσ2(x)⩾···⩾x−aσn(x). Gi en an in ege k,1⩽k⩽n,wese : k(A, x) =1 k k  i=1 x−aσi(x)and k(A) =in x∈X k(A, x). *Co esponding au ho . E-mail add ess: pue [email protected] (J. Pue o). 1The esea ch o he i s au ho was pa ially suppo ed by he I alian na ional g oup G.N.A.M.P.A. 2The au ho hanks Spanish minis y o Science and Technology h ough g an numbe BFM2001-2378. 0022-247X/$ – see on ma e 2003 Published by Else ie 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 P n:27/11/2003; 13:15 yjmaa9036 P.2 (1-11) by:ML p. 2 2P.L. Papini, J. Pue o / J. Ma h. 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 Clea ly, 1(A) is he Chebyshe adius o A, ha we shall also deno e by (A), while n(A) is he minimum a e ageo dis ances om he poin s o A, usually deno ed by µ(A). (We also use his no a ionwhen e e ing o o he s’ esul s.) A poin x(when i exis s) such ha k(A, x) = k(A) will be called a k-cen um o A. In pa icula , a 1-cen um o Ais a (Chebyshe ) cen e ; an n-cen um o Ais a median (o Fe ma poin ). The e m k-cen um was coined in he ea ly se en ies[15] o e e o he minimiza ion o he unc ion k(A, x) when Xis a ini e me ic space. The eade should no ice ha his e m (k-cen um) di e s om n-cen e as i is used in ecen pape s. In he la e , n-cen e means cen e o median o n-poin se s o n- la o a gi en ini e se . In his pape , we s udy he unc ions k(A, x) and he k-cen a; hese p oblems, apa om some esul s gi en in [23], ha e been also conside ed in [11,15,16] om an algo- i hmic poin o iew. The in e es ed eade can also ind di e en applica ions o hese unc ions in di e en a eas o applied ma hema ics as eliabili y: op imiza ion o sys ems k-ou -o -n[1]; loca ion analysis [13] o in decision heo y [22], among o he s. 2. P elimina y esul s We s a wi h a simple ema k;clea ly, gi en a ini e se A={a1,...,a n}, o anyx∈X we ha e 1(A, x) ⩾ 2(A, x) ⩾···⩾ n(A, x). F om his we ha e he ollowing ema k. Rema k 2.1. Fo any Awe ha e (A) ⩾ 2(A) ⩾···⩾ n−1(A) ⩾µ(A). (1) Rema k 2.2. We can also gi e es ima es in he “opposi e” sense. Le 1 ⩽k⩽j⩽n. Gi en any A={a1,...,a n}, o e e yx∈Xwe ha e k k(A, x) =k i=1x−aσi(x)⩽ j i=1x−aσi(x)=j j(A, x); aking in imum on x, we ob ain k k(A) ⩽j j(A). (2) A be e es ima e is he ollowing (whose p oo is almos i ial) p oposi ion. P oposi ion 2.1. Gi en A={a1,...,a n},le n⩾2hwi h han in ege 1⩽h⩽n/2.I i, j is a pai o indexes such ha ai−aj=δ(A),se A1=A {ai,aj}; hen le i1,j 1be indexes such ha ai1,aj1∈A1and ai1−aj1=δ(A1); hen de ine A2=A1 {ai1,aj1}. P oceeding in his way, we ob ain 2h 2h(A) ⩾δ(A) +δ(A1)+δ(A2)+···+δ(Ah−1). (3) The nex esul gi es us some s uc u al p ope ies o he k(A, x) unc ion. They a e di ec consequences o basic p ope ies o he no m in Xand hus, i s p oo is le ou . ARTICLE IN PRESS UNCORRECTED PROOF S0022-247X(03)00845-X/FLA AID:9036 Vol.•••(•••) ELSGMLTM(YJMAA):m1 2003/11/25 P n:27/11/2003; 13:15 yjmaa9036 P.3 (1-11) by:ML p. 3 P.L. Papini, J. Pue o / J. Ma h. 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 P oposi ion 2.2. Le A={a1,...,a n}and le kbe an in ege 1⩽k⩽n; hen he unc ion k(A, x) (x∈X)is 1-Lipschi z con inuous and con ex. Mo eo e , i Xis s ic ly con ex, k(A, x) is s ic ly con ex ou side lines con aining a leas kpoin s o A. Gi en A,le o ε⩾0and1⩽k⩽n=#A, sk(A, ε) =x∈X: k(A, x) ⩽ k(A) +ε.(4) Acco ding o P oposi ion 2.2, he se s sk(A, ε) a e always closed and con ex. Also, in a dual space, he unc ions x→x−aa e weak∗-lowe semicon inuous, so he se s sk(A, ε) a e bounded, w∗-closed, and w∗-compac . The e o e, he (possibly emp y) se sk(A) = ε>0 sk(A, ε) (5) is always closed, bounded, and con ex, and i s elemen s a e he k-cen a o A, i.e., he poin s xsuch ha k(A, x) = k(A). By s anda d w∗-compac ness a gumen s we ob ain he ollowing p oposi ion. P oposi ion 2.3. I Xis a dual space (in pa icula , i Xis e lexi e), hensk(A) =∅ o any ini e se Aand any kbe ween 1and #A. Rema k 2.3. The abo e esul is ue, o example, i X=l∞. Also, he same esul holds i Xis no m-one complemen ed in X∗∗. The p oo in he case o exis ence o no m-one p ojec ion is simple (and ob ains ollowing he line o p oo s in [19]). Gene al esul s o his ype ha e been gi en in [19]. Nex esul shows ha also o he spaces ha e he same p ope ies. Theo em2.1.I X=c0, hen o e e y A={a1,...,a n}and1⩽k⩽nweha esk(A) =∅. P oo . We may conside Aas a subse o l∞.Sincel∞is a dual space, he e exis s x= (x(1),x(2),...,x(n),...)∈l∞such ha k(A, x) =in { k(A, y):y∈l∞}.Since Ais in c0 he e exis s an index hsuch ha |a(j) i|⩽x−aσk(x), o allj>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), o i=1,...,n. Hence, k(A, x0)⩽x−aσk(x)⩽ k(A, x) = k(A) and so k(A, x0)= k(A).✷ Rema k 2.4. The e a e spaces whe e o some ini e se s, cen e s and/o medians do no always exis ; one o hese spaces is a hype plane o c0conside ed in [12]. (This does no con adic Theo em 2.1.) Examples o ou -poin se s wi h a cen e bu wi hou median, o wi h a median bu wi hou a cen e a e indica ed in [12,20]. Examples o h ee-poin se s wi hou k-cen a o any ka e shown a he end o his pape . ARTICLE IN PRESS UNCORRECTED PROOF S0022-247X(03)00845-X/FLA AID:9036 Vol.•••(•••) ELSGMLTM(YJMAA):m1 2003/11/25 P n:27/11/2003; 13:15 yjmaa9036 P.4 (1-11) by:ML p. 4 4P.L. Papini, J. Pue o / J. Ma h. 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 Rema k 2.5. Le A⊂F,Acon aining a leas kpoin s, F ini e. Then k(A, x) ⩽ k(F, x) o all x∈X,andso k(A) ⩽ k(F ) (1⩽k⩽#A). Also, i k(A) = k(F ), hensk(A) ⊂ sk(F ). Rema k 2.6. I mk∈sk(A) and cis a cen e o F, hen we ha e he almos i ial es ima e mk−c⩽d(A,mk)+ (A), (6) whe e d(A,mk)=in x∈Ax−mkdeno es he dis ance o mk om he se A.In ac ,i mk−ai=d(A,mk), henweha e mk−c⩽mk−ai+ai−c⩽d(A,mk)+ (A). Rema k 2.7. I is clea ha x∈sn(A) and x−ai=cons an i=1,2,...,n, implies x∈s1(A). (See, o example, [3] o esul s o his ype.) Mo e gene ally, i ck∈sk(A) and he k a hes poin s o ckin Aa e a he same dis ance k om ck, henweha e (A) ⩽ (A,ck)= k(A);so o i=1,...,k, i(A) = k(A),and henck∈si(A). 3. Gene al esul s on k-cen a We s a wi h a gene al esul conce ning k-cen a, which gene alizes esul s con ained in [23], well-known o k=#A. Theo em 3.1. Le Xbe a s ic ly con ex space and A⊂X;i kis odd, hen sk(A) (1 ⩽ k⩽n)con ains a mos one poin ;i kis e en and sk(A) con ains xand x,x= x, hen he e exis (a leas )kpoin s o Aon he line passing h ough xand x. P oo . Gi en A={a1,...,a n}and k,1⩽k⩽n,i x,x belong o sk(A), hen acco ding o he con exi y o sk(A) also x=(x+x)/2 belongs o sk(A).Le a1,...,a kbe he k poin s o A u hes away o xand x,so ha k i=1x−ai=k k(A). Then, we ha e k k(A) = k  i=1    x+x 2−ai    ⩽ k  i=1x−ai 2+x −ai 2 ⩽k k(A, x) 2+k k(A, x) 2=k k(A), so all hese inequali ies a e equali ies. This means wo ac s: (1) a1,...,a ka e also he k poin s in A u hes o x;and(2)x−ai=λi(x −ai) o some non-nega i e λi,i=1, ...,k; he e o e x,x,a1,...,a ka e all collinea . This is impossible o kodd because in his case he unique median o A={a1,...,a k}is he only poin o Alea ing (k −1)/2 poin s o a1,...,a k o each side (“cen alpoin ”); o ke en, all poin s le ing k/2 on each side a e medians o A.✷ Rema k 3.1. The p oo o he abo e heo em shows ha i Xis a s ic ly con ex space and A⊂X,i #Ais odd, o #Ais e en and does no con ain kcollinea poin s, hen sk(A) (1⩽k⩽n) con ains a mos one poin . (The las esul ollows also om P oposi ion 2.2.) ARTICLE IN PRESS UNCORRECTED PROOF S0022-247X(03)00845-X/FLA AID:9036 Vol.•••(•••) ELSGMLTM(YJMAA):m1 2003/11/25 P n:27/11/2003; 13:15 yjmaa9036 P.5 (1-11) by:ML p. 5 P.L. Papini, J. Pue o / J. Ma h. 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 ha e no uniqueness esul . (See Rema k 3.3 below.) Theo em 3.2. Fo any A⊂Xwe ha e (A)= 2(A). P oo . Assume by con adic ion, ha 2(A) < (A) o some A={a1,...,a n}.Take x∈Xsuch ha 2(A, x) = (A) −σ o some σ>0; we ha e (A,x) ⩾ (A) (by de- ini ion) so he e exis s ai∈Asuch ha x−ai⩾ (A). Fo any aj∈A,j= i,weha e x−ai+x−aj 2⩽ 2(A, x) = (A)−σ, so x−aj⩽2 (A)−2σ−x−ai⩽2 (A)−2σ− (A) = (A)−2σ. I xλ=λai+(1−λ)x,0⩽λ⩽1, hen we ha e xλ−x=λai−x; 1 2ai−xλ+xλ−aj⩽1 2ai−x−x−xλ+xλ−x+x−aj ⩽ (A)−σ o all j= i. Choose λ∈(0,1)so ha xλ−ai= (A)−σ; we ob ain, o all j= i xλ−aj⩽2 (A)−σ−ai−xλ=2 (A)−2σ− (A)−σ= (A)−σ; he e o e (A,xλ)⩽ (A)−σ, a con adic ion. ✷ Rema k 3.2. In gene al, in any space, we ha e 3(A) < 2(A) o some A: o example, also in he Euclidean plane E2, he e a e h ee-poin se s whe e he cen e and he median do no coincide. We ha e p o ed(Theo em 3.2) ha 1(A) = 2(A) always. On he con a y, he equali y k(A) = k+1(A) o k⩾2 does no happen equen ly and i has some s ong implica ions. We shall discuss now his ac , gi ing a con e se o Rema k 2.7. Theo em 3.3. Le k(A) = k+1(A) o some k⩾1and A={a1,...,a n};n>k.Then sk(A) ⊂sk+1(A).(In pa icula , by Theo em 3.2,i cis a cen e o A, henc∈s2(A).) Mo eo e , i ck∈sk(A), hen(a leas ) he k+1poin s o Awhich a e a hes o ckha e he same dis ance k(A) om i ;in addi ion, o i=1,...,k, i(A) = k(A);ck∈si(A); si(A) ⊂si+1(A).(No e ha i Xis s ic ly con ex, hen sk+1(A) is a single on o k⩾2 since he k+1poin s a hes o cka e no collinea .) P oo . Le k(A) = k+1(A);ck∈sk(A). O de he elemen s o Aso ha ck−a1⩾ ck−a2⩾···⩾ck−an;weha e k(A) =1 k k  i=1 ck−ai⩾1 k+1 k+1  i=1 ck−ai= k+1(A, ck)⩾ k+1(A). ARTICLE IN PRESS UNCORRECTED PROOF S0022-247X(03)00845-X/FLA AID:9036 Vol.•••(•••) ELSGMLTM(YJMAA):m1 2003/11/25 P n:27/11/2003; 13:15 yjmaa9036 P.6 (1-11) by:ML p. 6 6P.L. Papini, J. Pue o / J. Ma h. 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 The e o e, ou assump ion implies ha ck∈sk+1(A); mo eo e , 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= k k+1, so ck−ak+1= k(A); bu hen, since ck−ak+1⩽min 1⩽i⩽kck−ai⩽1 k k  i=1 ck−ai= k(A), ck−a1=···=ck−ak=ck−ak+1. By ecalling Rema k 2.7, we ob ain he con- clusion. ✷ Rema k 3.3. In gene al, also i Xis he Euclidean plane, a 2-cen um o Ais no a cen e : o example, i A={(0,1);(0,−1);(ε, 0)},0⩽ε⩽1, hen he unique cen e o Ais he o igin, while all poin s (0,α);|α|⩽(1−ε2)/2, a e 2-cen a. Rema k 3.4. I Ahas a mos one (k +1)-cen um and k(A) = k+1(A), henx∈ sk+1(A) ⇒sk(A) ⊆{x}. Wi hou he assump ion o uniqueness on sk+1(A) his is no ue, as he ollowing example shows. Le Xbe he plane wi h he max no m, and A={(−9 10,0);(11 10,1);(−9 10,−1)};weha e 2(A) = 3(A) =1; P=(1 10,0)belongs o s2(A) ⊂s3(A); he o igin belongs o s3(A) bu no o s2(A). Ou nex esul , whose p oo ollows om he de ini ion o k(A), ex ends [3, P oposi- ion 2.7]. Theo em 3.4. Le mk∈sk(A),mj∈sj(A),max{k,j}⩽n=#A. Then we ha e mk−mj⩽ k(A) + j(A). (7) In pa icula , i j=kand {mk,m  k}⊂sk(A), hen  mk−m k ⩽2 k(A). (8) Rema k 3.5. The es ima es (7) and (8) a e sha p.(See [3, Example 2.9].) Bu i we assume ha Xis s ic ly con ex, hen we ha e be e es ima es. In ac , acco ding o Rema k 3.1, in his case ( o k= 2) we ha e uniqueness o solu ions in many cases. Bu o k= jwe canno gi e be e inequali ies (see [4, §4]) apa om he ac ha s ic inequali y holds in bo h (7) and (8). Now assume ha we ha e equali y in (7). Looking a he p oo o Theo em 3.4, we ob ain subsequen ly; o he j a hes poin s o mj,ai,i=1,2,...,j,weha e mj−ai+ai−mk=mj−mk; hej a hes poin s o mk, all ha e dis ance k(A, mk) om i ; he e o e, i j>k hen k(A) = j(A) and bo h mkand mjbelong ARTICLE IN PRESS UNCORRECTED PROOF S0022-247X(03)00845-X/FLA AID:9036 Vol.•••(•••) ELSGMLTM(YJMAA):m1 2003/11/25 P n:27/11/2003; 13:15 yjmaa9036 P.7 (1-11) by:ML p. 7 P.L. Papini, J. Pue o / J. Ma h. 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 o sj(A).I j=k, hen he k a hes poin s o mj[mk] a e on he sphe e o adius k cen e ed a mj[ espec i ely a mk]; mo eo e he dis ance be ween he cen e s o he wo balls is wice he adius k. In he ollowing we conside a localiza ion p ope y o he k-cen a wi h espec o co(A), he con ex hull o he se A. Theo em 3.5. I Xis a wo-dimensional space, o i Xis a Hilbe space, hen o any A and any k(1 ⩽k⩽#A), i holds sk(A) ∩co(A) =∅. Mo eo e , i Xis a Hilbe space, o i dim(X) =2and Xis s ic ly con ex, hen sk(A) ⊂co(A). P oo . The assump ions imply ha sk(A) =∅.I dim(X) =2 hen(see[21]) o e e y x∈X he e exis s x∗∈co(A) such ha x∗−a⩽x−a o any a∈A;i.e.,x∗−ai⩽ x−ai o i=1,...,n=#A,so k(A, x∗)⩽ k(A, x):i we akex∈sk(A), his shows ha he e also exis s x∗∈sk(A) ∩co(A). Now le Xbe Hilbe o i dim(X) =2, Xs ic ly con ex; i x/∈co(A),le x∗be he bes app oxima ion o x om co(A):weha ex∗−ai<x−ai o i=1,...,n,so k(A, x∗)< k(A, x), hus an elemen o sk(A) mus belong o co(A).✷ Co olla y 3.1. Le Xbe Hilbe o i dim(X) =2,Xs ic ly con ex;gi en A⊂Xwi h no subse o kpoin s being collinea , i mk∈sk(A) and c∈s1(A), henmk−c= (A) implies ha mk∈A. P oo . Follow he line o he p oo o [4, P oposi ion 5.1]. ✷ Ano he in e es ingp ope yo k-cen ao ase Ais ha hey allow o cha ac e ize inne p oduc spaces in e ms o hei in e sec ion wi h he con ex hull o A. Cha ac e iza ions o his ype a e known om he six ies. (See [8,9].) The same p ope yconce ning medians was conside ed in he nine ies by Du ie [7], whe e pa ial answe s we e gi en. I has been p o ed only ecen ly o medians o h ee-poin se s, his esul can be ound in [6]. Theo em 3.6. I dim(X) ⩾3and he no m o Xis no hilbe ian, hen he e exis s a h ee- poin se Asuch ha s3(A) ∩co(A) =∅. By using such heo em, i is no di icul o ob ain he ollowing p oposi ion. P oposi ion 3.1. I dim(X) ⩾3and he no m o Xis no hilbe ian, hen o e e y n⩾3 he e exis s an n-poin se Fsuch ha s3(F ) ∩co(F ) =∅. P oo . We p o e he esul o n=4, he ex ension o n⩾4 being simila . Unde he assump ions done,acco ding o P oposi ion 2.2, in x∈co(A) 3(A, x) is always a ained; now ake A={a1,a2,a3}as gi en by Theo em 3.6: o some σ>0weha e in x∈co(A) 3(A, x) = 3(A) +4σ> 3(A). ARTICLE IN PRESS UNCORRECTED PROOF S0022-247X(03)00845-X/FLA AID:9036 Vol.•••(•••) ELSGMLTM(YJMAA):m1 2003/11/25 P n:27/11/2003; 13:15 yjmaa9036 P.8 (1-11) by:ML p. 8 8P.L. Papini, J. Pue o / J. Ma h. 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 ha 3(A, ¯x) < 3(A)+σ; i is no a es ic ion o assume ha ¯x−a3⩽ min{ ¯x−a1,¯x−a2}.Now akea4/∈Asuch ha a3−a4⩽σand le F=A∪{a4}. We ha e 3(F, ¯x) ⩽ 3(A, ¯x) +σ⩽ 3(A) +2σ.Now akey∈co(F ): he eisx∈co(A) such ha x−y⩽σ; he e o e | 3(F, y) − 3(F, x)|⩽σ,so 3(F, y) ⩾ 3(F, x) −σ⩾ 3(A, x) −σ⩾ 3(A) +3σ; hus in y∈co(F ) 3(F, y) ⩾ 3(A) +3σ⩾ 3(F, ¯x) +σ⩾ 3(F ) +σ, his p o es he hesis. ✷ Gi en a se Awi h npoin s and k<n, we can di ide he space Xin o n k egionsRj,so ha when xis aken in one o hese egions, he same kpoin s o Aa e he a hes o x;o cou se, inside each o hese egions he e a e k!di e en possible o de ings σ1,...,σ k.I is possible o ha e Ri∩Rj=∅( he alues o he k h dis ance can be equal o he (k +1) h one); also, i Rjis de e mined by a1,...,a k hen ai/∈Rj o i=1,...,k. Also in gene al he medians o a1,...,a k(i hey exis ) do no belong o Rj. No e ha hese egions a e no in gene al con ex: o example, i Xi he plane wi h he max no m, gi en a1=(1,0) and a2=(−1,0), hese x−a1⩾x−a2is no con ex.Bu he same is ue, o some pai , in any space wi h a non-hilbe ian no m. I Xis a Hilbe space, hen he egions Rja e con ex:in ac , conside , e.g., he egion Rde e mined by he poin s a1,...,a k,k<#A: hen R= k  i=1x∈X:x−ah⩽x−ai o h=k+1,...,n . Ris he in e sec ion o k(n −k)-con ex egions, he e o e i is con ex. A de ailed analysis o hese se s can be ound in [13]. (No only o Hilbe spaces.) Also in he pa icula case o wo-dimensional spaces some geome ical p ope ies as well as he complexi y analysis a e gi en in [14]. Minimizing k(A) is equi alen o sol e n kcons ained Fe ma p oblems; hen looking o he minimum o he alues ob ained: o each Rj, de e mined by kgi en poin s, say {a1,...,a k}, look o a median o hese poin s, es ic ed o he “ easible egion” Rj.Al- go i hms o he solu ion o his kind o p oblems in wo-dimensional spaces can be ound in [14]; also, in ne wo ks ( ini e me ic spaces) algo i hms a e gi en in [10,16]. Gi en X, conside o k∈N he pa ame e Jk(X) =sup2 k(A) δ(A) :A⊂X ini e, max{2,k}⩽#A.(9) Fo k=1, he numbe J1(X) =J(X) is called he ini e Jung cons an and has been s udied in ensi ely; in gene al, 1 ⩽J(X)⩽2, while he alue o J(X) gi es in o ma ion on he s uc u e o X. As shown pa ially in [5] and la e comple ely in [18], we always ha e J(X)=sup2µ(A) δ(A) :A⊂X ini e, 2 ⩽n=#A. Since µ(A) ⩽ k(A) ⩽ (A) always (see (1)), we ob ain he ollowing esul . ARTICLE IN PRESS UNCORRECTED PROOF S0022-247X(03)00845-X/FLA AID:9036 Vol.•••(•••) ELSGMLTM(YJMAA):m1 2003/11/25 P n:27/11/2003; 13:15 yjmaa9036 P.9 (1-11) by:ML p. 9 P.L. Papini, J. Pue o / J. Ma h. 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 Theo em 3.7. In e e y space X, o e e y posi i e in ege k, we ha e Jk(X) =J(X). (10) Ou las esul in his sec ion was al eady known o medians (see [4]) bu i can be ex ended o gene al k-cen a. P oposi ion 3.2. Le mk∈sk(A) o some se A. Assume ha Ak⊂A,#Ak=kand k(A) =1 ka∈Akmk−a.I mk−1 ka∈Aka= k(A) hen Xis no s ic ly con ex. P oo . By he iangula inequali y we ha e k(A) =    mk−1 k a∈Ak a    ⩽1 k a∈Ak mk−a= k(A). Thus, mkis also a cen e o Akand k(A) = (Ak). Now, we apply i s claim in [4, P opo- si ion 3.1] o hese Ak o ge he esul . ✷ 4. Concluding ema ks To conclude ou analysis o k-cen a, we s udy se e al p ope ies o hese poin s e- ga ding equila e al se s. Recall ha Ais called equila e al i ai−aj=cons an o i= j,1⩽i, j ⩽n=#A. Also, ecall ha he cen oid o a ini e se Aisgi enby he poin 1 #Aa∈Aa. Fo equila e al se s he e a e se e al nice p ope ies connec ing cen e s, medians and cen oids (see [2]). Some o hem can be ex ended u he o k-cen a. P oposi ion 4.1. Le Abe an equila e al se in an inne p oduc space Xand le k⩾3; hen he cen oid o Abelongs o sk(A). P oo . Assume ha 0 is he cen e o A; henai,aj=cons an o i= j,1⩽i, j ⩽ n=#A.Le y=n j=1λjaj; hen he unc ion (λ 1,...,λ n)=k i=1y−aiis sym- me ic. In Hilbe spaces i always exis s mk∈sk(A) ∩co(A). Mo eo e , unde he hypo hesis o he p oposi ion sk(A) is a single on, hen mkis he unique minimize o and λ1= λ2=···=λn=1/n; hus mkis he cen oid o A.✷ Rema k 4.1. Le A={a1,...,a n}be an equila e al se wi h ai−aj=d,∀i= j; hen i is easy o see ha k(A, x) ⩾d 2 o any x∈X. Indeed, o any x∈X,k k(A, x) is a ained as a sum o dis ances om x o kpoin s o A. Le us deno e by Ak(x) he subse o Acon aining he poin s ha de ine k(A, x).Ak(x) i sel is an equila e al se wi h ai−aj=d,∀i= j,ai,aj∈Ak(x); hen k k(A, x) = a∈Ak(x) a−x⩾kd 2,