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,