a
Loca ing was e pipelines o minimize hei impac on ma ine
en i onmen
Te esa Ca
´ce es
a
, Juan A. Mesa
b
, F ancisco A. O ega
c
Depa men o Applied Ma hema ics I, Compu e Enginee ing Highe Technical School, Uni e si y o Se ille, Spain
b
c
Depa men o Applied Ma hema ics II, Enginee ing Highe Technical School, Uni e si y o Se ille, Spain
Depa men o Applied Ma hema ics I, A chi ec u e Highe Technical School, Uni e si y o Se ille, Spain
Abs ac
A was e pipeline, conside ed as an undesi able acili y, is o be loca ed in a coas al egion. Two c i e ia a e aken in o
accoun , he Euclidean dis ance om a gi en se o p o ec ed a eas (co al ee s and sandbanks) and a u ili y unc ion ela ed
o he pipe leng h, bo h o be maximized. The pape desc ibes a me hodology o ob ain an efficien se o poin s whe e he
ex eme o a ma ine pipeline should be loca ed. Since he o mula ion o he model is based on he zone Vo onoi diag am,
he compu a ional complexi y o he sol ing p ocedu e is low.
Keywo ds: Undesi able acili y loca ion; Fo bidden egions; Zone Vo onoi diag am
1. In oduc ion
The coas al inge is he e i o y whe e ma ine, ai and e es ial en i onmen s in e ela e. He e e y
di e se and agile ecosys ems coexis , al hough subjec ed in many cases o inc easing deg ada ion due o
indus ial and u ban de elopmen s dis espec ul o he en i onmen .
Nea ly wo- hi ds o he wo ld’s popula ion li e along he seaboa d. In Spain his p opo ion can be es i-
ma ed as 69% by using da a co esponding o yea 2001 (Ins i u o Nacional de Es adı
´s ica, 2004). Almos a
qua e o he Medi e anean li o al in Spain is a ificial su ace. Mos ma ine con amina ion is p oduced on
land. Each yea , 10 billion ons o indus ial and u ban sewage a e di ec ly pou ed in o he Medi e anean sea,
and 90% is un ea ed. Pollu ion specifically affec s oceanic p ai ies and co al ee s due o dec easing ege able
biomass and biological di e si y (see Wo ldwide Fund o Na u e/Adena, 2000).
Posidonia oceanica (Linnaeus) Delile is a plan wi h lea es, flowe s and ui , simila o hose plan s which
li e in o es s and ga dens, bu which li es in he sea be ween he su ace and a dep h o 50 m, whe e he e is s ill
enough ligh o pho osyn hesis. I is endemic o he Medi e anean sea and, by p o iding he p incipal
sou ce o oxygena ion o he Medi e anean sea, i is i s mos impo an ecosys em. The Posidonia meadow
p oduces a ba ie ee which main ains he balance o he li o al sedimen a ion since hei long lea es
es ain he swell he eby p o ec ing he li o al om e osion by minimizing he impac o he wa es on he
beaches (see Ma ba
´e al., 1996). The Posidonia meadow is he habi a o mo e han 400 plan species and
1000 animal species; i p o ides shel e , ood and an adequa e en i onmen o he ep oduc ion o many p o -
i able species. Due o i s ecological ole, his sea-g ass is a p o ec ed species in Spain and in F ance.
Nowadays, Posidonia oceanica is dec easing on he coas al inge due o se e al ac o s:
1. Sea con amina ion, undamen ally om e es ial sou ces, p oduces a subsequen educ ion in wa e qual-
i y, which obs uc s pho osyn hesis, he eby causing he dea h o he plan .
2. Illegal coas al d ag fishing is ha m ul because o i s s ong physical impac .
3. Public wo ks on he coas al inge (spo s ha bou s, b eakwa e s, egene a ion o beaches) modi y he li -
o al dynamic and he e o e he en i onmen al condi ions o he sea floo .
4. The equen seasonal ancho age o ships in he same places on he coas can damage he sea floo .
The Eu opean Union (EU) ecognizes he need o p o ec he habi a s and ma ine ecosys ems in coas al
wa e s; in pa icula , meadows o Posidonia oceanica, co al ee s and sandbanks (see EU Di ec i e, 1992).
Following he co esponding EU-di ec i es, go e nmen agencies a e a p esen p omo ing he planning
and he managemen o coas al en i onmen s.
Resea ch ca ied ou in diffe en zones, o de e mine he dis ibu ion and bounda ies o he diffe en sub-
s a um and sedimen s o sea-g ass beds along he coas , commonly gene a e a da abase o isual, opog aphic
and hema ic maps so ha he analysis by means o a Geog aphic In o ma ion Sys em (GIS) can be pe o med
(see Calzadilla Pe
´ ez e al., 2002; Jaya issa e al., 2002; Melloul and Collin, 2002).
Once he geog aphical loca ion o he s udy a ea has been es ablished, igilance and con ol sys ems o
hese habi a s a e applied in o de o de ec , by ae ial pho og aphs, u bidi ies o he wa e column’s e ical
s uc u e. Fo his pu pose, he collec ed sa elli e images a e p ocessed wi h he GIS in o de o assess he
in e ac ion be ween he de ec ed dis u bances and he Posidonia oceanica beds. In Fig. 1 a sa elli e image
is shown o he sou h-wes coas o Spain nea he mou h o he Tin o i e (p o ince o Huel a, Andalusia).
Simula ion ools, which ha e been ecen ly de eloped o assess he wa e quali y, in eg a e he so wa e o
manage elede ec ion and geo-s a is ical in o ma ion. The images gene a ed by hose sys ems a e ypically pla-
na (see He, 2003). The e o e, he o mula ion o p oblems on a plane makes sense al hough hei na u e is i-
dimensional.
The se ing conside ed in his pape is a geome ical abs ac ion o a coas al scena io which consis s o a
plana egion, which includes zones o biological in e es , whose le -hand side ep esen s he li o al line. Tak-
ing in o accoun he exis ence o uppe and lowe bounda ies o he ownship in cha ge o he ins alla ion o
he pipeline, he scena io will be assumed o be a ec angula s ip. He e one was e pipeline (as Fig. 2 shows)
mus be loca ed pe pendicula o he coas al line so ha i s emissions ha e he lowes impac on ma ine
en i onmen .
The mode n plas ic ma e ials, such as polye hylene, used o he ab ica ion o ou all pipelines, a e essen-
ially immune o he co osi e effec s o seawa e and o he a ack by ma ine o ganisms. Mo eo e , due o he
Fig. 1. Telede ec ion by sa elli e.
flexibili y o his ma e ial, he ou e o an ou all pipeline can easily a oid obs acles, haza ds and en i onmen-
ally sensi i e a eas. In planning a ma ine ou all he fi s s ep should be o de e mine a sui able loca ion o
he diffuse . The de e mina ion o he loca ion and design o he diffuse should be based on ob aining ade-
qua e dis ance om sensi i e a eas and sufficien dep h, dispe sion and/o die-off o pollu an s commensu a e
wi h he le el o ea men p io o discha ge o assu e negligible en i onmen al o heal h impac (Reiff, 2002).
The o al cos o an ou all is dependen , o a g ea deg ee, on he leng h and diame e o he ou all pipe-
line. The leng h can be de e mined by he loca ion o en i onmen ally sensi i e a eas, beaches and wa e spo
a eas, he slope o he ocean floo , he p e ailing wind di ec ion and he di ec ion and eloci y o cu en s. In
his pape , he leng h (xP0) o he ou all pipeline is associa ed o a u ili y unc ion U il(x)P0 whose ou -
line sa isfies he ollowing p ope ies:
1. The pipeline leng h mus be s ic ly posi i e (U il(0) = 0; U il(x)>0,"x> 0).
2. Func ion U il(x) is s ic ly inc easing o x> 0 up o a h eshold alue x
*
> 0 whe e a maximum is a ained.
Wi hin eason, he u he he ou all is om he coas , he be e .
3. Func ion U il(x) asymp o ically dec eases o a ze o le el since he excessi e leng h pu s up he cos o ins al-
la ion.
A gene alized gamma unc ion
U ilðxÞ¼xaebx;8xP0;
commonly used o de elop he ic ion ac o s in he models o ip dis ibu ion (O u
´za and Willumsen,
2001), sa isfies he p e ious spa ial beha iou (Fig. 3).
Pa ame e s aand ba e posi i e and ha e ye o be calib a ed. The p ocedu e o pa ame e calib a ion mus
be based on he s a is ical analysis o dis ibu ion o obse ed leng hs o was e pipelines. In his sense, he
Fig. 2. Ma ine pipe.
0246 8 10
0
0.025
0.05
0.075
0.1
0.125
0.15
Leng h
U ili y
Fig. 3. An ins ance o he gene alized gamma densi y unc ion.
me hod o leas -squa es can be used o de e mine he bes fi pa ame e s aand b o he pipeline leng hs col-
lec ed in a da abase.
Al hough hese pa ame e s appea non-linea ly in he defini ion o he u ili y unc ion, a ans o ma ion
can be applied o ob ain an app op ia e linea combina ion in he unknown pa ame e s. In pa icula , aking
loga i hms in he exp ession y=x
a
e
bx
log y¼alog xbx)log y
log x¼abx
log x.
The e o e, gi en a lis o s a is ical da a (x
d
,y
d
), d2D, whe e x
d
indica es he leng h o he ou all pipeline
whose u ili y is es ima ed by y
d
, he op imal alues o he a iables aand bin he leas -squa es sense can
be calcula ed by means o he exp essions:
b¼jDjPxd
log xd
log yd
log xd

Pxd
log xd

Plog yd
log xd

jDjPxd
log xd

2Pxd
log xd

2;
a¼Plog yd
log xd

Pxd
log xd

2

Pxd
log xd

Pxd
log xd
log yd
log xd

jDjPxd
log xd

2Pxd
log xd

2.
The aim o his a icle is o analyse he p oblem o loca ing a was e pipeline on a coas al egion i o bidden
egions exis in o de ha bo h he impac on ma ine habi a s is minimized and a u ili y unc ion associa ed o
pipe leng h is maximized. The pape is o ganized as ollows: Sec ion 2desc ibes he me hodology o sol ing
he maxmin loca ion p oblem. Sec ion 3ob ains he op imum o he u ili y unc ion. Sec ion 4s a es he
model o loca ion in he plane in o mal e ms as a bi-c i e ion p oblem, showing an example. In Sec ion
5, conclusions a e p esen ed and se e al ex ensions o his p oblem a e in oduced.
2. The maxmin loca ion p oblem
2.1. Fo mula ion
Le X(x,y) be he end o a was e pipeline pa allel o axis OX, inside a bounded ec angle in he fi s squa e
o he Ca esian plane, whose lowe le -hand e ex coincides wi h he o igin o he coo dina es.
We assume o he sake o simplici y ha he a eas o be p o ec ed can be enclosed in he in e io o ci cles
(co al ee s) and ec angles pa allel o Ca esian axes (sandbanks and meadows o Posidonia oceanica). The e
a e wo echnical easons o assuming hese shapes o he sensi i e egions: fi s , he unde lying dis ance in
he scena io is Euclidean, and subsequen ly he le el cu es o iso-affec a ion will be ci cum e ences in he
absence o p edominan cu en s, and secondly, he digi iza ion equi ed o p ocess he images ob ained by
spa ial sampling in he coas al zone is based on he p e ious exis ence o a ec angula g id which suppo s
maps o colou a ia ions (see Cae io e al., 2003).
In gene al co al ee s ha e i egula shapes (usually non-con ex, close o a ac al shape) and he o ien a-
ion o sandbank bounda ies is dependen on he p e ailing di ec ion o he wa es. Ne e heless, he possibil-
i y o o e lapping hose basic figu es (ci cles and ec angles) o a small size p o ides a easonable le el o
accu acy in he assump ion. E iden ly, a highe esolu ion in he maps will lead o a g ea e compu a ional
effo o he de e mina ion o solu ions.
When conside ing a medium scale, a polygonal app oxima ion o he mo phology o he p o ec ed habi a s
can be app op ia e. No ice ha only one homogeneous ype o polygonal con ou is assumed in he pape :
o bidden egions a e iso-o ien a ed ec angles. This assump ion p o ides an immedia e decomposi ion o
he s udy egion in o cells, which a e also ec angula , whe e he cu es con aining efficien poin s can be eg-
ula ly de e mined (see figu e which illus a es he las case conside ed in he Appendix). The me hodology
de eloped o his con ex can be easily adap ed o sol e he co esponding loca ion p oblem in p esence o
polygonal egions which a e non-necessa ily ec angula .
Le X= [0,M]·[0,L] be a subse o R2, wi h M,L> 0, which deno es he egion unde conside a ion. Le
C¼ Ci:i2Igbe a se o o bidden ci cula egions, wi h espec i e cen es a A
i
(a
i1
,a
i2
) and non-nega i e
adii
i
, which ep esen s he se o co al ee s which need p o ec ion in ela ion o pollu an emissions. In addi-
ion, le R¼ Rj:j2Jgbe a se o ec angula egions, wi h he espec i e lowe le -hand e ices deno ed
by V
j
(
j1
,
j2
), leng h l
j
and heigh h
j
, which a e assumed o be he Posidonia oceanica p ai ies o sandbanks
( ec angula bands pa allel o coas al inge) conside ed as zones o biological in e es . These ci cles and ec -
angles a e comple ely o pa ially con ained in X.
In gene al, le Z¼ Zk:k2Kg ep esen a se o ci cula o ec angula zones. The easible egion o he
p oblem is S¼Xnð[kZkÞ. Since each Z
k
is a simply-connec ed closed se , he dis ance om a poin P o a
zone Z
k
can be defined as
dðP;ZkÞ¼min
Q2Zk
d2ðP;QÞ;
whe e d
2
(Æ,Æ) deno es he Euclidean dis ance.
Once he in ensi y o he was e dispe sion dec eases wi h he Euclidean dis ance om he diffuse X, he
na u al objec i e will coincide wi h he o mula ion o he co esponding 1-Maxmin p oblem; namely,
max
X2SDminðXÞmin
k dðX;ZkÞg.
Fo a comp ehensi e su ey o he li e a u e on in e se op imiza ion, he eade is e e ed o Qin e al. (2003).
2.2. A concise e iew
This maxmin p oblem can be ans o med in o an equi alen o mula ion:
max d
s. .
d6dðX;ZkÞ;k2K
X2S;
!
max d
s. .
d6min
Q2Rj
d2ðX;QÞ;j2J;
d6min
Q2Ci
d2ðX;QÞ;i2I;
X2S
8
>
>
>
>
>
>
>
<
>
>
>
>
>
>
>
:
Analogous o mula ions o he a o emen ioned p oblem can be ound in he li e a u e designed o he
modelling o eal scena ios. Fo ins ance,
1. Melach inoudis and Cullinane (1985) used his maxmim objec i e o loca e one undesi able acili y wi hin a
geog aphical egion; in pa icula , hey applied he model o he s a e o Massachuse s, app oxima ing he
o bidden egions (50 exis ing ci ies) by means o ci cles. Ka ush–Kuhn–Tucke condi ions we e used o
iden i y he se o local maxima.
2. Fe nandez e al. (1997) used wo app oaches: he fi s me hodology was based on he Ka ush–Kuhn–
Tucke condi ions and he second geome ical de elopmen exploi ed he concep o p oximi y o segmen ,
o sol e he p oblem:
max d
s. .
d6min
Q2Sj
d2ðX;QÞ;j2J;
X2S;
8
>
>
>
>
<
>
>
>
>
:
whe e each S
j
was a o bidden polygonal egion. The au ho s applied he me hodology o loca e an incin-
e a ion plan in a egion o he Sou h o Spain whe e he p edominan wind di ec ions indica e a specific
shape o he p o ec ed a ea cen ed a each popula ion cen e.
3. Tuy e al. (2003, in p ess) p oposed an efficien diffe ence-o -con ex (DC) op imiza ion algo i hm o sol e
he maxmin p oblem

max d
s. .
d6min
Q2Di
d2ðX;QÞ;i2I;
X2S;
8
>
>
>
>
<
>
>
>
>
:
whe e each D
i
was a ci cula egion o be p ese ed.
Two examples we e p esen ed in his las pape o illus a e he me hodology ollowed. One o hem
in ol ed 11 ci cles wi h diffe en cen es and adii, whe e 45 i e a ions we e necessa y so ha he DC algo i hm
would each he op imal solu ion. Fig. 4 shows he la ges emp y ci cle om he se o exis ing ci cles consid-
e ed in a ec angula egion.
2.3. Ou me hodological p oposal
Al hough diffe en non-con ex quad a ic p og amming me hods can be applied o sol e his la ges emp y
ball p oblem, we p opose an app oach based on he concep o he a ea Vo onoi diag am (Okabe e al., 2000)
o find a fini e domina ing se o ci cle cen es om which global op ima can be de e mined.
The a ea Vo onoi diag am can be cons uc ed om i s co esponding line Vo onoi diag am. Le
E¼ð
Sk2KoZkÞ[oX ep esen he union o he se o bounda ies o Zand he ou edges o ec angle X.
In ou model he lines which delimi each o bidden zone oZ
k
belong o he ollowing ypes:
1. Scena io bounda ies; namely, axis OX (y= 0), axis OY (x= 0) and delimi a ions x=M,y=L.
2. Con ou o ci cle C(A, ) cen ed a A(a
1
,a
2
) and wi h adius >0.
3. Con ou o ec angle R(V,l,h), whose lowe le -hand e ex is loca ed a poin V(
1
,
2
) and whose ho izon-
al and e ical dimensions a e espec i ely l> 0 and h>0.
Le joZ
k
jbe he numbe o line segmen s and ci cum e ence a cs which enclose p o ec ed a ea Z
k
. Define
jEjas he o al numbe o lines o be conside ed o building he line Vo onoi diag am: jEj¼Pk2KjoZkj. The
ollowing p oposi ion deals wi h he compu a ion o he bisec o cu es o all possible pai s o bounda y
ypes o he a o emen ioned zones.
P oposi ion 1. Bisec o cu es o zone pai s a e piece-wise cu es composed o s aigh lines, pa abolas and/o
hype bolas.
The e o e, he edges o his line Vo onoi diag am a e always simple con inuous cu es. An applica ion o
Ca a heodo y’s ep esen a ion heo em on he plane (see Rocka ella , 1970) leads us o s a e ha he diag am
e ices may be defined as hose poin s sha ed by h ee o mo e Vo onoi edges. Due o his ac , he a ea Vo o-
noi diag am can be efficien ly gene a ed in ime OðjEjlog jEjÞ ollowing he p ocedu e sugges ed by Okabe
1
2
3
4567
8
9
10
11
LAND
X
Fig. 4. La ges emp y ci cle.
e al. (2000); namely, fi s build he line a ea Vo onoi diag am associa ed o edges which ep esen he bound-
a ies o o bidden zones, and hen dele e he supe fluous edges. The a o emen ioned compu a ional complex-
i y is ensu ed by he p ope y labelled OKA1 in ha book (page 187).
Figs. 5 and 6 espec i ely show he line Vo onoi diag am and he a ea Vo onoi diag am associa ed wi h he
example o Tuy’s pape .
Once he line Vo onoi diag am has been buil , he la ges emp y ci cle p oblem:
Gi en a se o dis inc ec angula and ci cula zones Zfind he la ges emp y ci cle whose cen e is in se X
can be sol ed.
3. Maximizing he u ili y unc ion
The wo pa ame e s aand bo unc ion
y¼U ilðxÞ¼xaebx
allow he analys o fine- une he u ili y associa ed wi h he pipeline leng h. I s calib a ion can be based on he
coincidence be ween s a is ical pa ame e s o pipeline samples ( o an iden ical pu pose) and heo e ical alues
o he u ili y unc ion whe e ele an p ope ies exis . Among hese a e:
1. Since unc ion y=x
a
e
bx
, is a diffe en iable unc ion, he s udy o he sign o i s de i a i e unc ion
y0¼ðabxÞxa1ebx;
in he in e al x2(0,M), indica es ha i s only maximum is a ained a poin x¼a
b o a> 1. A ypical
leng h o he pipeline leng h a e age is 
l¼200 m (Reiff, 2002). The e o e, he assump ion a
b¼
lpe mi s
a fi s educ ion o he numbe o pa ame e s o calib a e.
1
2
3
4567
8
9
10
11
LAND
Fig. 5. The line Vo onoi diag am.
1
2
3
4567
8
9
10
11
LAND
Fig. 6. The a ea Vo onoi diag am.
2. Taking in o accoun ha
y0¼abx
xy
a new de i a ion can be pe o med, yielding
y00 ¼ðabxÞ2a
x2y.
Since y> 0, wo inflexion poin s can easily be deduced by imposing condi ion y00 =0:
x1¼a
bffiffiffi
a
p
b;x2¼a
bþffiffiffi
a
p
b.
The second alue indica es ha he asymp o ical dec ease o ze o o he u ili y unc ion s a s when he
pipeline leng h exceeds a dis ance ffiffia
p
b om he leng h a e age 
l¼a
b. Toge he wi h he a o emen ioned p op-
e y, his new p ope y can also be used o e en ually de e mine he pa ame e alues.
3. Assuming an app oach o a single-pa ame e bwhich can ake alue 1, hence, ais he only pa ame e
which cha ac e izes he maximum o he u ili y unc ion. Mo eo e , i we a e in e es ed in a ep esen a ion
o he componen o u ili y in e ms o p obabili y, a simple ac o is all ha is equi ed o no malize he
u ili y unc ion; namely,
U ilðxÞ¼ 1
Cðaþ1Þxaex;a>0.
The no maliza ion ac o is based on he Eule gamma unc ion:
CðzÞ¼Z1
0
z1e d ;z>0.
The gene al p ope ies o his new single-pa ame e e sion o he u ili y unc ion emain he same.
4. Bi-c i e ion op imiza ion
In p ac ice, bi-objec i e p oblems a e o en educed o a single-objec i e p oblem by ollowing one o wo
possible s a egies:
(a) Modelling an objec i e unc ion which is a weigh ed sum o he indi idual unc ions.
(b) Se ing one objec i e, whose alue is limi ed, as a cons ain and hen op imizing he o he objec i e.
Mo eo e , he bi-objec i e p oblem
max DminðXÞ
max U ilðXÞ
s. . X2S
8
>
<
>
:ðDUMPÞ
can also be di ec ly ackled by cons uc ing he se o non-domina ed (efficien o Pa e o-op imal) poin s. The
app oach deal wi h in his pape ollows his me hodology. Fo his pu pose, wo use ul defini ions a e
in oduced.
Defini ion 1. A solu ion X0=(x0,y0) domina es he solu ion X=(x,y) i and only i
Dmin(X0)PDmin(X),
U il(X0)PU il(X).
Dominance is s ic when a leas one inequali y is s ic .
Defini ion 2. Xis an e ficien solu ion o he bi-objec i e p oblem i and only i no o he solu ion X0exis s
which s ic ly domina es X.
Le ESbe he se o hose edges in he conside ed egion Xwhich a e ou side all o bidden zones Zk(i.e.,
ES¼E S) and le NSbe he node se o he zone Vo onoi diag am inside he easible egion S.
P oposi ion 2. ESis a domina ing se o solu ions o DUMP in S.
P oo . Rec angula egion Xcan be e ically scanned by means o segmen s o equa ion x=k, wi h
06k6M, be ween y= 0 and y=L. Each edge e2ESsepa a es Vo onoi egions inside S.
Le Q
i
(k,y
i
(k)) be he in e sec ion poin s o e ical line x=kand ES, o de ed by y-coo dina es. These
poin s cons i u e a fini e domina ing se o all poin s o e ical sec ion x=kinside S:
Conside wo consecu i e poin s Q
i
and Q
i+1
which a e in he con ou o Vo onoi egion Z
k
(i). Le
Q(k,y) be a gene ic poin in e io o Vo onoi egion Z
k
(i) inside e ical segmen QiQiþ1(Fig. 7). Due o he
con exi y p ope y o he Euclidean dis ance, he maximum o unc ion d(Q,Z
k
(i)) is eached a any ex eme
o segmen QiQiþ1. The e o e, a leas one o hese ela ion pai s holds o all poin s Qin e io o segmen
QiQiþ1
U ilðQÞ¼U ilðQiÞ;
dðQ;ZkðiÞÞ <dðQi;ZkðiÞÞ;
U ilðQÞ¼U ilðQiþ1Þ;
dðQ;ZkðiÞÞ <dðQiþ1;ZkðiÞÞ.

P oposi ion is a consequence o his ac . h
P oposi ion 2 sugges s o in es iga e he educ ion o he numbe o non-efficien poin s inside se ES.
•Since each edge o he zone Vo onoi diag am is ei he a s aigh line, a pa abola o a hype bola, a o mal
desc ip ion is possible o each edge ein e ms o a iable y, which ac s as a pa ame e by aking alues in a
ce ain in e al. Subsequen ly, each edge ecan be analy ically exp essed as ollows:
x¼ eðyÞ;8y2½y1ðeÞ;y2ðeÞ.
•This exp ession pe mi s us o analyse u ili y unc ion U il(x(y)) along each edge wi h espec o a iable y
which akes alues in i s defini ion in e al (i.e., "y2[y
1
(e),y
2
(e)]). The in e io o he in e als whe e he
a ia ion o he u ili y is mono onous can be explo ed by means o he cancella ion o he ac o s which
appea when he de i a i e o unc ion U il(x(y)) is calcula ed:
d
dyU ilðxðyÞÞ ¼ xa1ebxx0ðyÞðabxÞ.
In o de o comple e he analysis, he ex emes o in e al [y
1
(e),y
2
(e)] a e added o conside a ion. Le NBbe
he se o in e sec ion poin s be ween edges Eand bounda ies (x=0,x=M,y= 0 and y=L) o he easible
egion X.
Q i+1
Q i
Q
1
2
3
4567
8
9
10
Zk(i)
LAND
Fig. 7. Dominance along e ical segmen x=k.
I
2
>
1
hen d
2
(X,A
2
)>d
2
(X,A
1
) and hence he hype bola b anch u ns a ound he ci cle wi h he smalles
adius
1
(see Fig. 16).
8. The bisec o cu e (see Fig. 17) o he pai composed o ci cle C(A, ) and ec angle R(V,l,h) is a con inuous
union o a cs o hype bola b anches (H) and pa abolas a cs (P) since
•The bisec o cu e o poin V(a ec angle e ex) and he ci cle is exp essed as d
2
(X,A) =d
2
(X,V); i
implies equa ion d
2
(X,A)d
2
(X,V)= which iden ifies he b anch o he hype bola whose ocal poin s
a e a poin s Aand V, and whose dis ance be ween e ices is .
•The bisec o cu e o a e ical (o ho izon al) edge o ec angle R(V,l,h) and he ci cle is an a c o a
pa abola.
9. Finally, he bisec o cu e (see Fig. 18) co esponding o ec angle pai s R
1
(V
1
,l
1
,h
2
) and R
2
(V
2
,l
2
,h
2
)isa
con inuous union o po ions o media ix lines (L) and pa abolas (P).
Re e ences
Calzadilla Pe
´ ez, A., Damen, M.C.J., Genele i, D., Hobma, T.W., 2002. Moni o ing a ecen del a o ma ion in a opical coas al we land
using emo e sensing and GIS. case s udy: Guapo i e del a, Laguna de Taca igua, Venezuela. En i onmen , De elopmen and
Sus ainabili y 4, 201–219.
Cae io, S., Painho, M., Goo ae s, P., Cos a, H., Sousa, S., 2003. Spa ial sampling design o sedimen quali y assessmen in es ua ies.
En i onmen al Modelling & So wa e 18, 853–859.
Cohon, J.L., 1978. Mul iobjec i e P og amming and Planning. Academic P ess, New Yo k.
EU Di ec i e 1992. Council Di ec i e 92/43/EEC o 21 May 1992 on he conse a ion o na u al habi a s and wild auna and flo a. Official
Jou nal o he Eu opean Communi ies 35(L 206), 7–489.
Fe nandez, F., Pue o, J., Rod iguez-Chı
´a, A.M., 1997. A maxmin loca ion p oblem wi h non-con ex easible egion. Jou nal o
Ope a ional Resea ch Socie y 48, 479–489.
Haide , S., Paquie , A., Mo el, R., Champagne, J.Y., 2003. U ban flood modelling using compu a ional fluid dynamics. Wa e &
Ma i ime Enginee ing 156, 129–135.
LAND
Sandbank
Co al
ee
H
H
P
PVo onoi
edge
Fig. 17. The bisec o o pai [ci cle C, ec angle R].
LAND
P
LP
LP
L
Sandbank
Sandbank Vo onoi
edge
Fig. 18. The bisec o o pai [ ec angle R
1
, ec angle R
2
].

He, C., 2003. In eg a ion o geog aphic in o ma ion sys ems and simula ion model o wa e shed managemen . En i onmen al, Modelling
& So wa e 18, 809–813.
Ins i u o Nacional de Es adı
´s ica, 2004. Censo de Poblacio
´n y Vi iendas 2001. Repo in Spanish a ailable a elec onic add ess: <h p://
www.ine.es/in oine>.
Jaya issa, L.P., Gue o, M-C., He ia achchi, S., Koedam, N., 2002. Changes in ege a ion co e and socio-economic ansi ions in a
coas al lagoon (Kalame iya, S i Lanka), as obse ed by elede ec ion and g ound u hing, can be a ibu ed o an ups eam i iga ion
scheme. En i onmen , De elopmen and Sus ainabili y 4, 167–183.
Ma ba
´, N., Dua e, C.M., Ceb ia
´n, J., Gallegos, M.E., Olesen, B., Sand-Jensen, K., 1996. G ow h and popula ion dynamics o posidonia
oceanica on he Spanish Medi e anean coas : Elucida ing seag ass decline. Ma ine Ecology P og ess Se ies 137, 203–213.
Melach inoudis, E., Cullinane, T.P., 1985. Loca ing an undesi able acili y wi hin a geog aphical egion using he maxmin c i e ion.
Jou nal o Regional Science 25, 115–127.
Melloul, A.J., Collin, M.L., 2002. P io i iza ion o sus ainable g oundwa e managemen needs: The case o he Is ael’s s essed Coas al
Aqui e . En i onmen , De elopmen and Sus ainabili y 4, 347–360.
Okabe, A., Boo s, B., Sugiha a, K., Chiu, S.N., 2000. Spa ial Tessella ions: Concep s and Applica ions o Vo onoi Diag ams. Wiley,
Chiches e .
O u
´za , J.D., Willumsen, L.G., 2001. Modelling T anspo , hi d ed. Wiley, Chiches e .
Qin, Z., Xu, Y., Zhu, B., 2003. On some op imiza ion p oblems in obnoxious acili y loca ion. In: Lec u e No es in Compu e Science,
Compu ing and Combina o ics: 6 h Annual In e na ional Con e ence, COCOON 2000 (Sydney, Aus alia), ol. 1858/2000. Sp inge -
Ve lag, Heidelbe g, pp. 320–329.
Reiff, F.M. 2002. Small diame e HDPE (high-densi y polye hylene) subma ine ou alls. Technical Repo OPS/CEPIS/PUB/00.60. Pan
Ame ican Cen e o Sani a y Enginee ing and En i onmen al Sciences (CEPIS). Washing on, DC.
Rocka ella , R.T., 1970. Con ex Analysis. P ince on Uni e si y P ess, New Je sey.
Tuy, H., Nghia, N.D., Vinh, L.S., 2003. A disc e e loca ion p oblem. Ac a Ma hema ica Vie namica 28, 185–199.
Tuy, H., Minoux, M., Hoai-Phuong, N.T., in p ess. Disc e e mono onic op imiza ion wi h applica ion o a disc e e loca ion p oblem.
SIAM Jou nal on Op imiza ion.
Wo ldwide Fund o Na u e/Adena 2000. Las P ade as de Posidonia: Impo ancia y Conse acio
´n. Repo in Spanish a ailable a
elec onic add ess <h p://www.ww .es>.