Sociedad de Es adis ica e In es igaci6n Ope a i a
Top
(1998)
Vol.
6,
No.
2, pp. 313-319
Maximin loca ion" Disc e iza ion no always wo ks
Isabel Alonso, Emilio Ca izosa and Edua do Conde
Depa amen o de Es adls ica e L O.
Uni e sidad de Se illa
Ta ia s/n, 41012 Se illa, Spain
[email p o ec ed], [email p o ec ed], [email p o ec ed]
Abs ac
In his no e we show by means o a simple example ha , i he maximin p oblem
wi h (nonlinea ) conca e inc easing u ili y unc ions is sol ed by inspec ing he
ex eme poin s o he (gene alized) Vo onoi diag am (as usually p oposed), one
may ha e o inspec an in ini e numbe o candida e poin s.
Key Wo ds: Maximin, Gene alized Vo onoi diag am, Disc e iza ion.
AMS subjec classi ica ion: 90B85; 68U05.
1 In oduc ion
In his pape we p esen an example o which he disc e iza ion s a egy
equen ly used o maximin loca ion p oblems does no wo k judiciously.
The p oblem consis s o inding a loca ion on S o a new obnox-
ious acili y maximizing he minimum u ili y om he exis ing acili ies,
Dasa a hy-Whi e (1980), E ku -Neuman (1989), Melach inoudis-Cullinane
(1985), Melach inoudis-MacG ego (1995), Plas ia (1996). In o he wo ds,
we wish o sol e he p oblem:
max~s mini=l .....
n{qi(~/i(X))} (P)
whe e:
9 The easible se S is a polygonal egion in R 2.
9 Func ions 7i, i -- 1,..., n ep esen gauges, Rocka ella (1970), mea-
su ing he e ec s o he new acili y on he demand poin s
i, i =
1,... ,n, i.e.,
1
"yi(x)
= in {A > O:
-~(x - i) E Bi} Vx E R 2 Vi = 1,..., n
The esea ch o he second and hi d au ho s is pa ially suppo ed by G an PB96-
1416-C02-02 o Minis e io de Educaci6n y Cul u a, Spain
Recei ed: Decembe 1997; Accep ed: Oc obe 1998
314
I. Alonso, E. Ca izosa and E. Conde
whe e Bi is a compac con ex se wi h he o igin o coo dina es in i s
in e io . The ypical ins ance is he euclidean no m (each
Bi
equals
he uni ci cle, Dasa a hy-Whi e (1980), Melach inoudis-Cullinane
(1985), al hough nonsymme ic balls ha e also been sugges ed by
Plas ia (1996).
9 E e y demand poin i is associa ed wi h a non-dec easing conca e u il-
i y unc ion
qi
measu ing he u ili y o he new se ice. The mos
s udied case is he one wi h each
qi
being he iden i y, Dasa a hy-
Whi e (1980), Okabe-Boo s-Sugiha a (1992), Okabe-Suzuki (1997),
O'Rou ke (1994), P epa a a-Shamos (1985), al hough mo e ealis ic
models can be ob ained i u ili ies which a e only conca e a e allowed,
E ku -Neuman (1989), Plas ia (1996).
Since he objec i e unc ion o (P) does no enjoy good p ope ies o con-
exi y, a echnique o global op imiza ion is needed.
The mos equen ly used p ocedu e, Dasa a hy-Whi e (1980), Mela-
ch inoudis-Cullinane (1985), Melach inoudis-MacG ego (1995), Hakimi-
Labb&Schmeichel (1992), consis s o a disc e iza ion s a egy which wo ks
by building explici o implici ly he
Vo onoi diag am
and e alua ing i s
ex eme poin s among which he candida e solu ions o global op imum
can be ound.
The
Vo onoi egion Y( i)
associa ed wi h
i
is de ined as ollows:
Y( i) = {x E S~ qi(Ti(x)) <_ qj(Tj(x)), Vj = 1,..., n, },
see e.g. Okabe-Boo s-Sugiha a (1992).
Based on his cha ac e iza ion, he ollowing ela ion is sa is ied a he
Vo onoi egion
V( j):
min
{qi(~/i(x))}--
qj(~,j(x)) Vx e ~2( j)
i--l,...,n
Hence, p oblem (P) can also be exp essed as:
max max
qd(Tj(x))
l<_j<_n xEl~( j)
Maximin loca ion
315
which, due o he inc easing cha ac e o he u ili y unc ions qj, educes
o:
max
qj[
max 7/(x)]
l<j<n xEV( i )
Hence, one mus sol e he n op imiza ion p oblems:
max 7j(x)
Since each gauge conside ed
7i(x)
is con ex and he maximum o a con ex
unc ion on V( i) is a ained a i s ex eme poin s, such poin s ha e o be
examined o ind an op imal solu ion.
This s a egy has been success ully used o pa icula ins ances o p ob-
lem (P). Melach inoudis and MacG ego (1995) add ess he p oblem o
Euclidean dis ances, a plana polyhed al egion consis ing o m aces and
linea unc ions
qi,
leading o an
O(mn z)
algo i hm.
We p esen an example in which such me hod would lead o e alua e
an in ini e numbe o candida e poin s. We conclude, a his ime, his
me hod would be useless o some ins ances o p oblem (P).
2 An example
We conside as easible egion he segmen S = {(z, 0) : z E [0, 1]}.
Le 71 = 72 = I1"]1 be he Euclidean no m. Le l = (0,1) and 2 =
(0,-1).
The ollowing cons an c = ~ E [1, V~] and he conca e inc easing
u ili y unc ions ql and q2 a e conside ed o sa is y he ela ion:
ql(llx - iii) - q2(llx - 211) =
( - c)Ssin( _-~), i ~ [1,,/7] {c} (R)
= ql( ) -
q2( ) =
( )
= 0,
i = c
P oposi ion 2.1.
The p e iously de ined unc ion is wice con inuously
di e en iable.
316 I. Alonso, E. Ca izosa and E. Conde
I is needed he cons uc ion o he u ili y unc ions ql and q2 ha lead
us o sa is y he conca i y and inc easing condi ions as well as he ela ion
(R). The p eceding asse ion is needed in o de o e i y he condi ions
equi ed o u ili ies unc ions.
P oposi ion 2.2. Le ~ and l sa is y a > V~ l ~_ O. We conside :
[q2( ) =-89 2 +c~ ]
The u ili y unc ion q2 is conca e and inc easing in E [1, x/2].
On he o he hand, we s udy he condi ions o be sa is ied by he u ili y
unc ion ql.
P oposi ion
2.3. Le ~ and l be scala s such ha :
o~ >
x/2 l +
max e l, ~ 1 [ i ( ) [ and l > max e[1, ~l [ "( ) [
i we conside :
Iql( ) -- ( ) +q2( ) -= ( )- lil 2 - -od I
hen ql is conca e and inc easing, and also he ela ion (R) is sa is ied.
Indeed, since we ha e conside ed c~ sa is ying
c~> /2 l+ max I ( )],
hen ' - ~ + a > ' -
i + ~ +
max e[1, ~ 1 ] '( ) ]_> 0.
Hence q~ ( ) > 0, o all E [1, ~], and he u ili y unc ion ql is inc eas-
ing.
Mo eo e l _> max e[1,~q] ] "( ) ], hus l _> "( )
o all
~ [1,
~].
Hence, q~'( ) <_ 0 o all E [1, 2], and so we ha e shown i s conca i y.
Ma~min loca ion
317
Fo ins ance, i is easily checked ha
0.04 > max ] '( )l
E[l ,V'~]
3 > max [ "( ){,
e[l,4~]
hus aking
a = 3.1
/~ = 2,
p oblem (P) has a single op imal solu ion due o he inc easing cha ac e o
u ili y unc ions ql and q2 in [1, 2]. This solu ion is a ained a x = (1, 0)
while he disc e iza ion s a egy o Vo onoi diag ams leads us o an in ini e
numbe o unc ion e alua ions, as i is shown below.
In Figu e 1 we ha e ep esen ed he Vo onoi diag ams V( l) and V( 2)
o his ins ance.
(,2)
I I 2~. I I
-1.5 -I -0.5 0 0.5 1 1.5
1.5
1
0.5
0
-0.5
-1
Figu e 1: Vo onoi diag am in he plane
The bounda y o such Vo onoi egions ha e a shape
almos
linea a ound
he Y axis. Howe e , he ue beha iou close o he Y axis is sinusoidal,
as clea ly depic ed in he de ail o Figu e 1 shown in Figu e 2: In ac ,
he bounda y o such Vo onoi diag ams in e sec s he Y axis (wi hin he
easible egion o ou p oblem) in an in ini y o poin s, hus he Vo onoi
diag am es ic ed o he easible egion [0, 1] x {0} will ha e an in ini e
numbe o connec ed componen s9

318 I. Alonso, E. Ca izosa and E. Conde
0.72
{(z~,O) : k = 1...}
le-08
5e-09
0
- -5e-09
-le-08
0.735
I I
0.725 0.73
Figu e 2: Vo onoi diag ams. A de ail
In ac , a e some algeb a, one ob ains,
P oposi ion 2.4. Fo each k E Z wi h I k I> 2 hen, de ining zk as
zk = + e)2- 1 ~ [0, 1],
i ollows:
,,((zk, O)) = ,2((zk, O)) = 5 + c
so, om ( R ) :
q, (71 (zk, 0)) = q2(72(zk, 0))
hen 12(Vl) and k'( 2) ha e in ini ely many connec ed componen s, wi h he
sequence {(Zk, O)}lkl>2 as bounda y poin s.
This yields he ollowing: he equa ion qx(71(x))
= q2(72(x))
has an
in ini e numbe o solu ions, so an in ini e numbe o unc ion e alua ions
should be pe o med o ob ain a global op imum among he candida e
solu ions.
In sho , we ha e
Maximin loca ion 319
P oposi ion 2.5.
Le a and/3 be wo scala s as ollows:
a > ~/3 + max e[1,dT] [
'( )
[ , /3 > max e l, ~] I/"( )
I
hence, he u ili y unc ions ql and q2 conside ed as abo e p o ide an exam-
ple in which he equen ly used disc e iza ion s a egies o sol e maximin
p oblems a e no e ec i e, since in his case hey lead us o an in ini e
numbe o unc ion e alua ions.
Re e ences
Dasa a hy, B. and L.J. Whi e (1980) . A maximum loca ion p oblem. Ope a ions
Resea ch, 28, 1385-1401.
E ku , E. and S. Neuman (1989). Analy ical models o Loca ing undesi able
acili ies. Eu opean Jou nal o Ope a ional Resea ch, 40,275-291.
Hakimi, S.L. Labbd, M. and E. Schmeichel (1992). The Vo onoi pa i ion o a
ne wo k and i s implica ions in loca io heo y. ORSA Jou nal on Compu ing,
4,
412 -417.
Melach inoudis, E. and T.P. Cullinane (1985). Loca ing an undesi able acili y
wi hin a geog aphic egion using he MAXIMIN c i e ion, Jou nal o Regional
Science, 25, 115-127.
Melach inoudis, E. and J. MacG ego (1995). An O( nn ~) algo i hm o he Max-
imin p oblem in E 2. Ope a ions Resea ch Le e s, 18, 25-30.
Okabe, A. Boo s, B. and K. Sugiha a (1992). Spa ial Tessella ions: Concep s and
Applica ions o Vo onoi Diag ams. Wiley, New Yo k.
Okabe, A. and A. Suzuki (1997). Loca ional op imiza ion p oblems sol ed h ough
Vo onoi diag ams. Eu opean Jou nal o Ope a ional Resea ch, 98, 445-456.
O'Rou ke, J. (1994). Compu a ional Geome y in C. Camb igde Uni e si y P ess,
Camb igde.
Plas ia, F. (1996). Op imal loca ion o undesi able acili ies: A selec i e o e iew.
Belgian Jou nal o Ope a ions Resea ch, S a is ics and Compu e Science, 36,
109-127.
P epa a a, F.P. and M.I. Shamos (1985). Compu a ional Geome y. An in oduc-
ion. Sp inge -Ve lag, New Yo k.
Rocka ella , R.T. (1970). Con ex Analysis. P ince on Uni e si y P ess.