UNIVERSIDAD DE SEVILLA
MÁSTER UNIVERSITARIO EN MATEMÁTICAS
TRABAJO FIN DE MÁSTER:
PROBLEMA DE LOCALIZACIÓN
CON BARRERAS
DEPARTAMENTO DE ESTADÍSTICA E INVESTIGACIÓN
OPERATIVA, FACULTAD DE MATEMÁTICAS
P esen ado po :
MOISÉS RODRÍGUEZ MADRENA
Di igido po :
JUSTO PUERTO ALBANDOZ
Se illa Junio 2017
Abs ac
In loca ion p oblems, he dis ance unc ions ha model he a el dis ance be ween he
elemen s o he p oblem play a undamen al ole in he adequacy o ideli y o he heo-
e ical p oblem o he eal p oblem conside ed. Think, o example, o p oblems in he
design o connec i e ne wo ks ( o his ype o p oblems belongs, o men ion some eal-
wo ld p oblem, he ou ing o pipelines on ships), o en he sec ions o hese ne wo ks
mus obey a pa icula s uc u e o pa e n, he dis ance unc ions a e hen con enien
o calcula ing he dis ance be ween he nodes o he ne wo k. Ano he eal ea u e o
loca ion p oblems, which is o g ea impo ance in achie ing good modeling, is he
cons ain o he easible solu ion space. This es ic ion is due o he p esence in he
en i onmen whe e he p oblem is conside ed o bodies o obs acles, called ba ie s in
he li e a u e, ha do no allow a elling o passing h ough hem. The ba ie dis ance
unc ions a e, in his case, he way o ob ain he adequacy o he heo e ical p oblem
o he eal p oblem. The objec o s udy o he p esen End o Mas e P ojec a e he
men ioned ba ie dis ance unc ions and hei applica ion o he loca ion p oblems.
The i s chap e gi es a b ie summa y o he elemen a y dis ance measu es used
in he modeling o loca ion and anspo p oblems, as well as hei basic p ope ies.
The ba ie s dis ances, cen al concep o his End o Mas e P ojec , appea in he
second chap e , whe e special a en ion is paid o he case o polyhed al ba ie s and
whe e he main known esul s in he a a e shown. Mo e p ecisely, hese dis ances
a e in oduced in he chap e o add ess he p oblem o he minimum ec angula pa h
in he p esence o hype pa allelepiped complexes ha pe o m as ba ie s in any eal
space o ini e size. Ex ensions o he known esul s o he ea men o his p oblem
in he plana case and new o iginal me hods o hei exac esolu ion a e he main
con ibu ion o his chap e and o he wo k in gene al.
In he hi d chap e a pa icula case o he loca ion p oblem wi h ba ie s is ea ed:
he median p oblem in ec angula me ic and in he con ex o hype pa allelepipeds
ha ac as ba ie s in any eal space o ini e size. The me hods de eloped in he se-
cond chap e a e he basis o he cons uc ion o he new algo i hms ha sol e such
p oblem, which a e p esen ed in his chap e .
The compu a ional pe o mance es s o he algo i hms o he second and hi d
chap e s a e collec ed in he ou h and inal chap e .
I
Ex ac o
En los p oblemas de localización, las unciones de dis ancia que modelan la dis ancia
de iaje en e los elemen os del p oblema juegan un papel undamen al en la ade-
cuación o idelidad del p oblema eó ico al p oblema eal conside ado. Piénsese, po
ejemplo, en los p oblemas de diseño de edes conec i as (a es e ipo de p oblemas
pe enece, po ci a algún p oblema del ámbi o eal, el en u amien o de ube ías en
ba cos), a menudo los amos de es as edes deben de obedece a una de e minada es-
uc u a o pa ón, las unciones de dis ancia son en onces con enien es pa a el cálculo
de la dis ancia en e los nodos de la ed. O a ca ac e ís ica eal de los p oblemas de
localización, de g an impo ancia a la ho a de consegui un buen modelado de los mis-
mos, es la es icción del espacio de soluciones ac ibles. Dicha es icción se debe a
la p esencia en el en o no donde es á conside ado el p oblema de cue pos u obs ácu-
los, denominados ba e as en la li e a u a, que no pe mi en el iaje o paso a a és de
ellos. Las unciones de dis ancia con ba e a son, en es e caso, la o ma de consegui
la adecuación del p oblema eó ico al p oblema eal. El obje o de es udio del p esen e
T abajo de Fin de Más e son las mencionadas unciones de dis ancia con ba e as y
su aplicación a los p oblemas de localización.
En el p ime capí ulo se o ece un esumen suscin o de las medidas de dis ancia
elemen ales usadas en el modelado de los p oblemas de localización y anspo e, así
como de sus p opiedades básicas.
Las unciones de dis ancia con ba e as, concep o cen al del T abajo de Fin de
Más e , apa ecen en el capí ulo segundo, donde se p es a especial a ención al caso de
ba e as poliéd icas y se mues an los p incipales esul ados conocidos en la ma e ia.
Más conc e amen e, es as dis ancias son in oducidas en el capí ulo pa a abo da el
p oblema del camino ec angula mínimo en p esencia de complejos de hipe pa alele-
pípedos ba e a en cualquie espacio eal de dimensión ini a. Ex ensiones de esul a-
dos conocidos pa a el a amien o de es e p oblema en el caso plano y nue os mé odos
o iginales pa a su esolución exac a son la p incipal con ibución de es e capí ulo y del
abajo en gene al.
En el capí ulos e ce o se a a un caso pa icula del p oblema de localización con
ba e as: el p oblema de la mediana en mé ica ec angula y en el con ex o de hipe pa-
alelepípedos que ac úan como ba e as en cualquie espacio eal de dimensión ini a.
Los mé odos desa ollados en el segundo capí ulo son la base pa a cons ui los nue os
algo i mos que esuel en dicho p oblema y que se p esen an en es e capí ulo.
III

IV Ex ac o
Las p uebas de endimien o compu acional de los algo i mos de los capí ulos se-
gundo y e ce o se ecogen en el cua o y úl imo capí ulo.
Índice gene al
Abs ac I
Ex ac o III
1. Funciones de dis ancia 1
1.1. No masymé icas ........................... 1
1.2. No masbloque ............................. 3
1.3. Relación en e las no mas bloque y la no ma de Manha an . . . . . . 9
2. Camino ec angula mínimo en p esencia de pa alelepípedos ba e a 11
2.1. Caminos mínimos y el concep o de isibilidad . . . . . . . . . . . . . 11
2.2. Ba e as poliéd icas y la p opiedad de con ac o con ba e as . . . . . 16
2.3. Camino ec angula mínimo en p esencia de pa alelepípedos ba e a . 18
2.3.1. Fo mulación como un p oblema de camino mínimo en g a os 19
2.3.2. Fo mulaciones de p og amación lineal y en e a mix a . . . . . 35
2.4. Camino bloque mínimo en p esencia de omboides ba e a . . . . . . 73
3. P oblema de la mediana ec angula en p esencia de pa alelepípedos ba-
e a 77
3.1. P oblema de localización con ba e as . . . . . . . . . . . . . . . . . 77
3.2. P oblema de la mediana ec angula en p esencia de pa alelepípedos
ba e a.................................. 79
3.2.1. Exis encia de conjun o dominan e ini o . . . . . . . . . . . . 80
3.2.2. Una o mulación de p og amación lineal y en e a mix a . . . . 84
3.3. P oblema de la mediana bloque en p esencia de omboides ba e a . . 87
4. P uebas compu acionales 89
4.1. Rendimien o de los modelos de p og amación lineal y en e a mix a . . 89
Conclusiones 93
Bibliog a ía 95
1
Funciones de dis ancia
La elección de una unción de dis ancia adecuada juega un papel undamen al a la ho a
de p opo ciona una buena es imación de las dis ancias de iaje en en o nos eales.
Dependiendo del modo de iaje y del ipo de p oblema conside ado, podemos usa ,
po ejemplo, la dis ancia euclídea pa a modela los desplazamien os po ía aé ea o
la mé ica de Manha an pa a p oblemas de anspo e u bano en Nue a Yo k. Es o
signi ica que di e en es modos de anspo e equie en di e en es o mas de es imación
de la dis ancia. Consecuen emen e, el aumen o de la he e ogeneidad en los p oblemas
ela i os al sec o del anspo e ha lle ado apa ejado una c ecien e p eocupación po
es ima con una mayo p ecisión las dis ancias de iaje. En lo que sigue se o ece un
esumen sin é ico de las no mas y medidas de dis ancia usadas en el modelado de los
p oblemas de localización y anspo e, así como de sus p opiedades básicas.
1.1. No mas y mé icas
De inición 1.1. Sea Sun conjun o compac o y con exo en Rncon eniendo al o igen en
su in e io . Además, sea Ssimé ico con espec o al o igen y sea X∈Rn. La no ma
γ:Rn→Rnde Xcon espec o a S iene dada po
γ(X) := ´ın {λ > 0 : X∈λS}.(1.1)
A menudo nos e e i emos a γ(X)como kXkγ.
Toda no ma γde inida de acue do a la De inición 1.1 sa is ace las p opiedades de
la no ma en Rn.
Lema 1.1. (Minkowski, 1911) Sea γde inida de acue do a la De inición 1.1. En on-
ces, pa a odo X, Y ∈Rny pa a odo λ∈R,
γ(X)≥0yγ(X)=0⇔X= 0,(1.2)
γ(λX) = |λ|γ(X),(1.3)
γ(X+Y)≤γ(X) + γ(Y).(1.4)
1
8 1.2. No mas bloque
Figu a 1.5: Bola unidad de la no ma `1y bola unidad de la no ma ponde ada `w
1en R2.
Ejemplo 1.3. La no ma ponde ada uno-i ini o `α,β
1,∞se de ine como la suma de las
no mas ponde adas `α
1y`β
∞:
kXk`α,β
1,∞=kXk`α
1+kXk`β
∞=X
i=1,2
αi|xi|+ m´ax
i=1,2βi|xi|,
donde α1, α2, β1, β2>0( e Figu a 1.6). Los ec o es undamen ales de la no ma
ponde ada uno-in ini o en R2son de la siguien e o ma:
1=0
1
α2+β2, 2=

1
α1+β1+β1
β2α2
1
α2+β2+β2
β1α1
,
3=1
α1+β1
0, 4=

1
α1+β1+β1
β2α2
−1
α2+β2+β2
β1α1
,
5=0
−1
α2+β2, 6=

−1
α1+β1+β1
β2α2
−1
α2+β2+β2
β1α1
,
7=−1
α1+β1
0, 8=

−1
α1+β1+β1
β2α2
1
α2+β2+β2
β1α1
.

1. Funciones de dis ancia 9
Figu a 1.6: Bola unidad de la no ma ponde ada uno-in ini o en R2.
1.3. Relación en e las no mas bloque y la no ma de
Manha an
En es a sección amos a segui a ando el caso del espacio bidimensional eal R2, con-
c e amen e, nos amos a cen a en las no mas bloque con exac amen e cua o ec o es
undamen ales ( e Figu a 1.7) y a discu i su elación con la no ma de Manha an `1
( e Figu a 1.5). Pa a dis ingui es as unciones de dis ancia más gene ales de la no ma
de Manha an con los ec o es undamen ales 1, ..., 4e ique ados como apa ecen en
el Ejemplo 1.2, en adelan e amos a deno a a los ec o es undamen ales de cualquie
o a no ma bloque con cua o ec o es undamen ales po u1, ..., u4.
Figu a 1.7: Bola unidad de una no ma bloque con cua o ec o es undamen ales
u1, ..., u4.
Sea γuna no ma bloque con ec o es undamen ales (o denados en el sen ido de las
agujas del eloj)
u1=u1
1, u1
2 , u2=u2
1, u2
2 , u3=u3
1, u3
2 , u4=u4
1, u4
2 ,
cumpliendo u3=−u1yu4=−u2. Si Tes la ans o mación lineal al que T(u1) =
Tu1= 1yT(u2) = Tu2= 2, en onces
T= 11 12
21 22=1
u1
2u2
1−u1
1u2
2u1
2−u1
1
−u2
2u2
1.(1.21)
10 1.3. Relación en e las no mas bloque y la no ma de Manha an
Obsé ese que la co espondien e ans o mación in e sa iene dada po
T−1=u2
2u1
1
u2
2u1
2.
Si conside amos, po ejemplo, la no ma `∞con los ec o es undamen ales e ique ados
como en el Ejemplo 1.1, en onces enemos
T=1
21−1
1 1 yT−1=1 1
−1 1.
Es ableciendo T(X) := TX pa a odo X∈R2, podemos p oba el siguien e esul ado
que elaciona las dis ancias en no ma bloque con la mé ica `1.
Lema 1.5. Sea γuna no ma bloque con cua o ec o es undamen ales y sea Tla
ans o mación lineal de inida po (1.21). En onces
γ(X, Y ) = `1(T(X), T(Y))
pa a odo X, Y ∈R2.
Demos ación. Conside emos en p ime luga el caso especial en el que Y= 0. Si
además X= 0, en onces el esul ado se ob iene i ialmen e. Sea X∈C(ui, ui+1)
pa a algún i∈ {1, ..., 4}y sea X=λiui+λi+1ui+1 la única ep esen ación de Xen
é minos de uiyui+1 ( eco demos que C(ui, ui+1)es un cono con exo).
Dado que γ iene sólamen e cua o di ecciones undamen ales podemos supone
sin pé dida de gene alidad que ui∈ {u1,−u1}yui+1 ∈ {u2,−u2}. Usando (1.19) y
el Lema 1.3 se sigue que
`1(T(X),0) = | 11x1+ 12x2|+| 21x1+ 22x2|
=
u2
1x1−u1
1x2
u1
2u2
1−u1
1u2
2
+
u2
1x2−u2
2x1
u1
2u2
1−u1
1u2
2
=λi+1 +λi
=γ(X, 0).
Aho a conside emos el caso gene al en el que X, Y ∈R2son ambos di e en es de
0. Dado que Tes una ans o mación lineal, inmedia amen e ob enemos
`1(T(X), T(Y)) = `1(T(X)−T(Y),0) = `1(T(X−Y),0)
=γ(X−Y, 0) = γ(X, Y ).
Nó ese que la de inición de Tpa a una no ma bloque γdada depende de la asignación
T(u1) = 1y cambia si ijamos T(u1) = − 1,T(u1) = 2oT(u1) = − 2.
2
Camino ec angula mínimo en
p esencia de pa alelepípedos ba e a
El p oblema de halla caminos mínimos en en o nos eales iene un g an in e és en el
con ex o de la localización, así como en o os ámbi os más allá de és e. Los p oble-
mas de camino mínimo en p esencia de ba e as ísicas apa ecen, po ejemplo, en la
plani icación de u as ma í imas de mínima longi ud en e di e en es pue os o en la
de e minación del camino óp imo de un obo en una plan a indus ial. En es e capí-
ulo nos amos a cen a en los caminos mínimos en e dos pun os con espec o a la
mé ica de Manha an cuando exis en pa alelepípedos que ac úan como ba e as. Con-
side a emos que dichos pa alelepípedos pueden in e seca , dando luga a obs áculos
complejos. Di e en es algo i mos son p esen ados pa a esol e el p oblema de ca-
mino mínimo en mé ica ec angula : po un lado, un mé odo basado en la ex ensión
al caso n-dimensional de esul ados conocidos pa a la e sión plana del p oblema; po
o o lado, nue os modelos de p og amación lineal y en e a mix a. El capí ulo comienza
in oduciendo las concep os básicos empleados en el es udio de los caminos mínimos
en p esencia de ba e as, sigue mos ando algunos esul ados que se ienen cuando las
ba e as p esen an o mas poliéd icas pa a inalmen e dedica se al p oblema pa icula
en no ma ec angula y ba e as en o ma de pa alelepípedos desc i o an es.
2.1. Caminos mínimos y el concep o de isibilidad
Sea duna mé ica ijada en el espacio n-dimensional Rn(n≥2) que se quie e u iliza
pa a medi dis ancias de iaje en e pa es de pun os de Rn. Asumimos que la mé ica
des á inducida po una no ma k•kd:Rn→Rny que es po an o simé ica (1.8) y
sa is ace la desigualdad iangula (1.9). Como sabemos, dpuede calcula se a pa i de
k•kdcomo
d(X, Y ) = kY−Xkd∀X, Y ∈Rn.
11
12 2.1. Caminos mínimos y el concep o de isibilidad
Además, sea {B1, ..., BN}un conjun o ini o de conjun os ce ados y disjun os dos
a dos de Rncon in e io no acío. Cada conjun o Bi,i= 1, ..., N, es llamado ba e a
(u obs áculo), y la unión de odas las ba e as se deno a po B, i.e., B=SN
i=1 Bi.
Nó ese que no se es á suponiendo que las ba e as engan que se aco adas. Asumimos
que mo e se po el in e io de las ba e as es á p ohibido. Sin emba go, es á pe mi ido
mo e se po la on e a ∂(Bi)de cada egión ba e a Bi,i= 1, ..., N.
Sea F:= Rn in (B)la egión ac ible (o espacio lib e) en Rn. Pa a e i a la
in ac ibilidad, amos a supone que Fes un subconjun o conexo de Rn.
La unción de dis ancia con ba e as ( ambién llamada mé ica de camino mínimo
odis ancia geodésica)dB:F × F → Rmide la longi ud del camino más co o (o los
caminos más co os) en e dos pun os XeYen la egión ac ible F=Rn in (B)que
no in e seca el in e io de ninguna ba e a.
De inición 2.1. Un X-Ycamino es una cu a con inua Pdada po la pa ame ización
p= (p1, ..., pn) : [0,1] →Rncon p(0) = Xyp(1) = Yque es con inuamen e
di e enciable en [0,1] sal o quizá en un núme o ini o de pun os, donde la de i ada
p0= (p0
1, ..., p0
n) iene lími e ini o po la izquie da y po la de echa.
La longi ud l(P)del X-Ycamino Pcon espec o a la mé ica ijada d iene dada
po
l(P) := Z1
0
kp0( )kdd .
Si Pno in e seca el in e io de ninguna ba e a, i.e., si p([0,1]) ∩in (B) = ∅, el X-Y
camino Pes un X-Ycamino pe mi ido.
Usando la noción de X-Ycamino pe mi ido, la dis ancia con ba e as dBen e dos
pun os XeYen la egión ac ible Fpuede de ini se de la siguien e o ma.
De inición 2.2. Pa a X, Y ∈ F, la dis ancia con ba e as dB(X, Y )es el ín imo de las
longi udes de odos los X-Ycaminos pe mi idos, i.e.,
dB(X, Y ) := ´ın {l(P) : Pes un X-Ycamino pe mi ido}.(2.1)
Un X-Ycamino pe mi ido con longi ud dB(X, Y )es un X-Ycamino pe mi ido d-
mínimo (o X-Ycamino óp imo, camino geodésico).
Nó ese que la exis encia de un X-Ycamino pe mi ido d-mínimo, que es una cu a
di e enciable sal o quizá en un núme o ini o de pun os, no puede se ga an izada
siemp e. En pa icula , pueden exis i casos donde el ín imo en (2.1) se alcance pa a
un camino que no sa is aga la condición de di e enciabilidad de la De inición 2.1. Un
ejemplo de es a si uación en el caso bidimensional se mues a en la Figu a 2.1.
2. Camino ec angula mínimo en p esencia de pa alelepípedos ba e a 13
Figu a 2.1: Un ejemplo en R2donde no exis e ningún X-Ycamino `2-mínimo. La
on e a supe io del conjun o ba e a B iene un núme o in ini o de pun os ex emos
en (1/i, 1−1/i2) y(−1/i, 1−1/i2) ,i∈ {2,4,8,16, ...}, es po ello que ningún
camino sob e es a on e a es un X-Ycamino pe mi ido de acue do a la De inición
2.1.
En adelan e nos amos a cen a en los p oblemas y conjun os de ba e as pa a los que
exis e un X-Ycamino pe mi ido d-mínimo pa a oda elección de X, Y ∈ F. Es e es
el caso, po ejemplo, de los conjun os de ba e as poliéd icos en Rn. En es os casos, el
ín imo en (2.1) puede se eemplazado po un mínimo.
La dis ancia con ba e as dBno es, en gene al, posi i amen e homogénea, lo cual
implica que no exis e una no ma induciendo la mé ica dB. Más aún, la dis ancia con
ba e as dB ampoco es, en gene al, con exa. Sin emba go, dBde ine una mé ica en la
egión ac ible F.
Lema 2.1. Sea duna mé ica inducida po una no ma y sea B=SN
i=1 Bila unión de
los conjun os ba e a. En onces, dBde ine una mé ica en F, i.e., pa a odo X, Y, Z ∈
F,
dB(X, Y )≥0ydB(X, Y )=0⇔X=Y, (2.2)
dB(X, Y ) = dB(Y, X),(2.3)
dB(X, Y )≤dB(X, Z) + dB(Z, Y ).(2.4)
Po consiguien e, (F, dB)es un espacio mé ico n-dimensional.
Demos ación. Las desigualdades e igualdades de (2.2) y (2.3) se ienen de o ma
i ial. Pa a p oba la desigualdad iangula (2.4) conside emos es pun os X, Y, Z ∈

14 2.1. Caminos mínimos y el concep o de isibilidad
F. Es ácil e que pa a odo X-Zcamino pe mi ido PX,Z y pa a odo Z-Ycamino
pe mi ido PZ,Y exis e un X-Ycamino pe mi ido PX,Y =PX,Z ∪PZ,Y de longi ud
l(PX,Y ) = l(PX,Z ) + l(PZ,Y )pasando po Z. Po an o,
dB(X, Y ) = ´ın {l(PX,Y ) : PX,Y es un X-Ycamino pe mi ido}
= ´ın {l(PX,Z ) + l(PZ,Y ) : PX,Z es un X-Zcamino pe mi ido y
PZ,Y es un Z-Ycamino pe mi ido}
=dB(X, Z) + dB(Z, Y ).
Nos e e i emos a dBcomo mé ica de camino mínimo odis ancia geodésica. El si-
guien e colo a io es una consecuencia inmedia a de la de inición de dB.
Co ola io 2.1. Sea duna mé ica inducida po una no ma y sea B=SN
i=1 Bila unión
de los conjun os ba e a. En onces
dB(X, Y )≥d(X, Y )∀X, Y ∈ F.
Conside ando la dis ancia desde un pun o dado X∈ F podemos dis ingui , po un
lado, las pa es de Fen las que dB(X, Y )es equi alen e a la mé ica d(X, Y )y, po
o o lado, las pa es de Fdonde dB(X, Y )> d(X, Y ).
De inición 2.3. Dos pun os X, Y ∈ F son d- isibles si
dB(X, Y ) = d(X, Y ),
es o es, si la dis ancia en e XeYno se e inc emen ada po la p esencia de las
egiones ba e a.
El conjun o de pun os que son d- isibles desde un pun o X∈ F es, po an o,
isiblesd(X) := {Y∈ F :dB(X, Y ) = d(X, Y )}.
De o ma simila , llama emos d-somb a de un pun o X∈ F al conjun o de pun os
Y∈ F que no son d- isibles desde X, i.e.,
somb ad(X) := {Y∈ F :dB(X, Y )> d(X, Y )}.
De inición 2.4. La on e a de la clausu a de la d-somb a de un pun o X∈ F (o, pa a
ab e ia , la on e a de somb ad(X)) es
∂(somb ad(X)) := {Y∈ F :Nε(Y)∩somb ad(Y)6=∅y
Nε(Y)*somb ad(Y)∀ε > 0},
donde Nε(Y) := {Z∈Rn:`2(Z, Y )< ε}.
2. Camino ec angula mínimo en p esencia de pa alelepípedos ba e a 15
En la Figua a 2.2 se mues an dos ejemplos de posibles o mas de la d-somb a de un
pun o dado X∈R2con espec o a dos mé icas ddi e en es.
Figu a 2.2: La `2-somb a y la `1-somb a de un pun o X∈R2.
Obsé ese que pa a algunas elecciones de la mé ica dun pun o que es d- isible puede
no se `2- isible, es o es, no isible en el sen ido usual de isibilidad en línea ec a.
Po o a pa e, odo pa de pun os `2- isibles son ambién d- isibles si des una mé ica
inducida po una no ma, como mues a el siguien e lema.
Lema 2.2. Sea duna mé ica inducida po una no ma. En onces
somb ad(X)⊆somb a`2(X), X ∈ F.
Además, si X, Y ∈ F son `2- isibles, X6=Y, en onces el segmen o de ec a que
conec a XeYes un X-Ycamino pe mi ido d-mínimo con longi ud d(X, Y ).
Demos ación. Sin pé dida de gene alidad, sea X= 0 el o igen (siemp e puede ha-
ce se una aslación que lle e Xal o igen) y sea Y∈ F un pun o `2- isible desde X.
En onces, el segmen o de ec a que conec a XeYes un X-Ycamino pe mi ido Pda-
do po la pa ame ización p: [0,1] →Rn,p( ) = ·Y, ∈[0,1]. Usando la de inición
de dis ancia con ba e as dB, De inición 2.2, la longi ud de Ppuede calcula se como
dB(X, Y )≤l(P) = Z1
0
kp0( )kdd =Z1
0



d
d ( Y )


d
d =Z1
0
kYkdd
=kYkd=d(0, Y ).
Po an o, el segmen o de ec a que conec a XeYes un X-Ycamino pe mi ido d-
mínimo con longi ud d(X, Y ). Po consiguien e, la sub egión de Fque es `2- isible
desde un pun o X∈ F es ambién d- isible desde X, y somb ad(X)⊆somb a`2(X)
pa a odo X∈ F.
16 2.2. Ba e as poliéd icas y la p opiedad de con ac o con ba e as
2.2. Ba e as poliéd icas y la p opiedad de con ac o
con ba e as
Un conjun o poliéd ico en R2es un conjun o ce ado cuya on e a es un polígono. En
Rncon n≥3, llama emos conjun o poliéd ico a odo conjun o ce ado cuyas ca as
de dimensión n−1son conjun os poliéd icos en Rn−1. Con iene hace no a aquí la
di e encia en e polied o y conjun o poliéd ico, mien as que el p ime o es siemp e
con exo po se la in e sección de un núme o ini o de semiespacios, el segundo no
iene po qué se lo necesa iamen e. En es a sección nos amos a cen a en el caso pa -
icula en el que el conjun o de ba e as {B1, ..., BN}es á cons i uido po conjun os
disjun os dos a dos, ce ados, poliéd icos, pe o no necesa iamen e con exos, en Rn.
Además, asumimos que el núme o de ca as de las ba e as de B=SN
i=1 Bies ini o
pa a e i a casos degene ados como el que se ilus ó en la Figu a 2.1. Los esul ados
que se mues an a con inuación ga an izan la exis encia de caminos pe mi idos míni-
mos pa a es e ipo de ba e as. Pa a pode abo da el caso gene al n-dimensional se á
necesa io ija an es la a ención en el caso bidimensional, al conjun o ini o de pun os
ex emos de Blo amos a deno a po P(B).
Lema 2.3. Sea {B1, ..., BN}un conjun o ini o de conju os ba e a en R2disjun os
dos a dos, ce ados, poliéd icos y con un conjun o ini o de pun os ex emos P(B).
Sea duna mé ica inducida po una no ma y sean X, Y ∈ F. En onces exis e un X-Y
camino pe mi ido d-mínimo SP con la p opiedad que apa a ece a con inuación.
P opiedad de con ac o con ba e as:
SP es un camino lineal a ozos con pun os c í icos solamen e en los pun os ex emos
de las ba e as.
Demos ación. Sean X, Y ∈ F y sea SP un X-Ycamino pe mi ido d-mínimo en
Fque no sa is ace la p opiedad de con ac o con ba e as. Nó ese que, dado que el
conjun o de ba eas y ambién el conjun o de pun os ex emos de las ba e as P(B)
son ini os, SP puede subdi idi se en un conjun o ini o de pun os e i icando que dos
pun os consecu i os en SP son `2- isibles. El Lema 2.2 implica que el segmen o de
ec a que conec a dos pun os consecu i os en SP es un camino pe mi ido d-mínimo
uniendo es os dos pun os. Po an o, podemos cons ui un camino lineal a ozos SP0
uniendo XeYcon un conjun o ini o de pun os c í icos y cuya longi ud es meno o
igual a la de SP. Aho a puede cons ui se un X-Ycamino pe mi ido d-mínimo SP00
con la p opiedad de con ac o con ba e as a pa i SP0. Sean [Ti−1, Ti]y[Ti, Ti+1]dos
segmen os ec ilíneos consecu i os de SP0. Asumamos que Ti−1yTi+1 son `2- isibles.
En onces, la desigualdad iangula implica que los dos segmen os ec ilíneos [Ti−1, Ti]
y[Ti, Ti+1]pueden se eemplazados po el segmen o ec ilíneo [Ti−1, Ti+1]sin inc e-
men a la longi ud de SP0. Supongamos aho a que Ti−1yTi+1 no son `2- isibles,
usando de nue o la desigualdad iangula , el pun o c í ico Tipuede mo e se a lo la go
de [Ti−1, Ti]o a lo la go de [Ti, Ti+1]hacia Ti−1oTi+1, espec i amen e, sin inc emen-
a la longi ud de SP0, has a que uno de es os segmen os ec ilíneos sea angen e a una
2. Camino ec angula mínimo en p esencia de pa alelepípedos ba e a 17
ba e a.
Du an e la i e ación de ambas ope aciones odo pun o ex emo de una ba e a que
pe enezca a SP0lo in e p e amos como un pun o c í ico Ti, incluso cuando el seg-
men o ec ilíneo [Ti−1, Ti+1]es pa e de SP0. De es a o ma, con la i e ación de ambas
ope aciones se consigue un camino SP00 con la p opiedad deseada después de un nú-
me o ini o de pasos, ya que odo pun o c í ico de SP0que no es aún un pun o ex emo
de una ba e a puede mo e se hacia X,Y, o un pun o ex emo de una ba e a. La exis-
encia de X-Ycamino pe mi ido d-mínimo es á ga an izada, pues si suponemos que
dB(X, Y )se alcanza únicamen e pa a caminos en Fque no sa is acen las condiciones
de la De inición 2.1, epi iendo el p oceso de cons ucción de SP00 a pa i de cual-
quie a de es os caminos, conseguimos un X-Ycamino con la p opiedad de con ac o
con ba e as, y po an o pe mi ido, con longi ud meno o igual que dB(X, Y ), lo cual
es una con adicción.
Nó ese que la p opiedad de con ac o con ba e as no se sa is ace en gene al pa a los
p oblemas en Rncon n≥3. En la Figu a 2.3 se mues a un ejemplo de si uación en
R3en la que no exis e ningún X-Ycamino pe mi ido `2-mínimo con pun os c í icos
sólo en los pun os ex emos de las ba e as p esen es. Sin emba go, el Lema 2.3 puede
gene aliza se al caso n-dimensional como mues a el Lema 2.4 a con inuación.
Figu a 2.3: Un X-Ycamino pe mi ido `2-mínimo en un en o no con dos ba e as po-
liéd icas en R3.
Lema 2.4. Sea {B1, ..., BN}un conjun o ini o de conju os ba e a en Rn,n≥3,
disjun os dos a dos, ce ados, poliéd icos y con un núme o ini o de ca as. Sea duna
mé ica inducida po una no ma y sean X, Y ∈ F. En onces exis e un X-Ycamino
pe mi ido d-mínimo SP con la p opiedad que apa a ece a con inuación.
P opiedad de con ac o con ba e as gene alizada:
SP es un camino lineal a ozos con pun os c í icos solamen e en las ca as de las
ba e as de dimensión n−2o menos.
24 2.3. Camino ec angula mínimo en p esencia de pa alelepípedos ba e a
[Ti, Ti+1]∩in (B) = ∅y a que los complejos son disjun os. De es a o ma, podemos
sus i ui cada segmen o [Ti, Ti+1]de SP00 po un Ti-Ti+1 camino ec angula pe mi ido
de su misma longi ud, siendo el esul ado de es a sus i ución un X-Ycamino ec an-
gula pe mi ido de la misma longi ud que SP00 y, po an o, que SP.
Figu a 2.9: El Ti-Ti+1 camino ec angula pe mi ido Q0es una amalgamación del Ti-
Ti+1 camino ec angula no pe mi ido Q.
Si Qes un X-Ycamino ec angula mínimo pe mi ido, el p opio Qes un X-Y
camino en el sen ido de la De inición 2.1: puede pa ame iza se en el in e alo [0,1],
siendo con inuamen e di e enciable sal o en un núme o ini o de pun os, es os son,
los codos. Que el camino pa ame izado es pe mi ido es e iden e pues el camino ec-
angula Qsin pa ame iza lo es. Po úl imo, seleccionada una pa ame ización pde
Q(cualquie pa ame ización es ánda pa a caminos lineales a ozos), puede comp a-
ba se, usando la p opiedad de adi i idad con espec o al in e alo de in eg ación de la
in eg al, que
l(Q) = Z1
0
kp0( )k`1d .
Si el Lema 2.4 (o el Lema 2.3 según el caso) simpli icaba la búsqueda de X-Ycaminos
pe mi idos `1-mínimos pa a ob ene dB(X, Y )al asegu a nos la exis encia de uno de
es os caminos con la pa icula idad de se lineal a ozos y con pun os c í icos sola-
men e en pa es conc e as de las ba e as, la noción de X-Ycamino ec angula y el
Lema 2.5 acili an aún más la a ea del cálculo de dB(X, Y )dada la sencillez de es os
úl imos caminos, pues no son más que una sucesión ini a de segmen os pa alelos a los
ejes coo denados que nos lle an de un pun o al o o. Es e es el momen o de o maliza
el p oblema al que que emos da solución.

2. Camino ec angula mínimo en p esencia de pa alelepípedos ba e a 25
P oblema 2.1. Dado el conjun o {B1, ..., BN}de complejos de pa alelepípedos iso-
é icos en Rndisjun os dos a dos y dados dos pun os XeYen la egión ac ible F,
siendo F=Rn B yB=SN
i=1 Bi, calcula dB(X, Y )así como un X-Ycamino
ec angula pe mi ido Qde esa longi ud, es deci , mínimo.
Lo p ime o que debemos plan ea nos es si es posible es ingi la egión de Fdonde
podemos encon a un camino ec angula mínimo pe mi ido. Dicha es icción a a
se posible y pa a ello se emplea á el siguien e concep o.
De inición 2.6. Sea Bla unión de un conjun o ini o de complejos de pa alelepípedos
iso é icos en Rndisjun os a dos a dos y sea F=Rn B. La en ol en e ec angula
i e a i a RBde X, Y ∈ F y de Bes el pa alelepípedo iso é ico en Rnmás pequeño al
que
X, Y ∈ RBy∂RB∩in (B) = ∅.
La en ol en e ec angula i e a i a de la De inición 2.6 puede ob ene se median e el
siguien e algo i mo.
Algo i mo 2.1. (Cos ucción de la en ol en e ec angula i e a i a)
Inpu : Los pun os X= (x1, ..., xn) eY= (y1, ..., yn) en Fy el conjun o {B1, ..., BN}
de complejos de pa alelepípedos ba e a en Rn, cada uno de ellos desc i o po el con-
jun o de pa alelpípedos {B1
i, ..., Bmi
i}que lo o man, i= 1, ..., N.
Paso 1: Hace Rigual al pa alelepípedo de cen o κ:= ((x1+y1)/2, ..., (xn+yn)/2)
y mi ad de la anchu a en cada coo denada OXk,ξk:= |κk−xk|=|κk−yk|,
k= 1, ..., n.
Paso 2: Mien as exis a un pa alelepípedo Bj
i∈Bi,j= 1, ..., mi,i= 1, ..., N, al
que ∂R ∩ in (Bj
i)6=∅, hace Rigual al pa alelepípedo dado po : el cen o
de coo denadas
κk:= (m´ax{κ0
k+ξ0
k, κ00
k+ξ00
k} − m´ın{κ0
k−ξ0
k, κ00
k−ξ00
k})/2,
siendo κ0
k, κ00
kyξ0
k, ξ00
klas coo denadas de los cen os y las mi ades de las
anchu as en la coo denada OXkdel pa alelepípedo Rcons uido en la e apa
an e io y el pa alelepípedo Bj
i espec i amen e, k= 1, ..., n; y mi ad de la
anchu a en cada coo denada OXk,k= 1, ..., n,
ξk:= |κk−m´ax{κ0
k+ξ0
k, κ00
k+ξ00
k}| =|κk−m´ın{κ0
k−ξ0
k, κ00
k−ξ00
k}|.
Ou pu : RB:= R.
El Algo i mo 2.1 sigue la idea elemen al de i englobando sucesi amen e median e un
pa alelepípedo con enedo mínimo los pa alelepípedos que o man los complejos de B
26 2.3. Camino ec angula mínimo en p esencia de pa alelepípedos ba e a
has a ob ene RB. La Figu a 2.10 ilus a la aplicación del Algo i mo 2.1 en un ejemplo
con cinco complejos de pa alelepípedos ba e a en el plano.
Figu a 2.10: Cons ucción de RBusando el Algo i mo 2.1.
Lema 2.6. El Algo i mo 2.1 halla la en ol en e ec angula i e a i a de X, Y ∈ F y
Ben un núme o ini o de pasos.
2. Camino ec angula mínimo en p esencia de pa alelepípedos ba e a 27
Demos ación. El Algo i mo 2.1 e mina en un núme o ini o de pasos, pues es amos
asumiendo que el núme o de complejos ba e a así como el núme o de pa alelepípedos
po los que es án o mados cada uno de ellos son ini os, luego el Paso 2 del algo i mo
se ejecu a á a lo sumo PN
i=1 mi eces, siendo Nel núme o de complejos ba e a y mi
el núme o de pa alelepípedos que cons i uyen el complejo Bi,i= 1, ..., N.
Pa a p oba la co ección del Algo i mo 2.1 amos a deno a po Rl,l= 1, ..., L,
al pa alelepípedo ob enido as la l-ésima i e ación del algo i mo, de es a o ma, R1es
el pa alelepípedo con enedo mínimo de XeY, y RLes el pa alelepípedo ob enido
al inaliza el algo i mo. En onces, el Algo i mo 2.1 cons ui á co ec amen e la en ol-
en e ec angula i e a i a RBsi RL=RB.
Cla amen e, Rl⊆ Rl+1 se iene pa a odo l= 1, ..., L. Po an o, X, Y ∈ RL.
P obemos aho a que ∂RL∩in (Bi)6=∅,i= 1, ..., N. Si es o no se da, en onces exis e
un pun o Z∈∂RL∩in (Bi). Sea Bj
i,j∈ {1, ..., mi}, un pa alelepípedo del complejo
Bi al que Z∈Bj
i. Si Z∈in (Bj
i)en onces llegamos a un absu do pues o que po el
Paso 2 del algo i mo el pa alelepípedo Bj
ihab ía sido añadiendo a RLen algún mo-
men o de la ejecución, no dando luga a que z∈∂RL. Si Zpe enece a la on e a de
Bj
i, en onces, po las suposiciones que es amos haciendo sob e la desc ipción de los
complejos de pa alelepípedos ba e a, exis i á o o pa alelepípedo Bk
idel complejo Bi
dis in o de Bj
i al que Z∈in (Bk
i), con lo que, de nue o po el Paso 2, se llega ía a
una con adicción, eniéndose po an o ∂RL∩in (B) = ∅. Pues o que X, Y ∈ RLy
∂RL∩in (B) = ∅, se iene la con ención RB⊆ RL, po se RBel meno pa alele-
pípedo iso é ico que e i ica es as condiciones.
Po o o lado, R1⊆ RBse iene po el Paso 1 del algo i mo. Supongamos aho-
a que RL*RB. En onces exis e un índice ∈ {2, ..., L} al que Rl⊆ RBpa a
odo l∈ {1, ..., −1}, pe o R *RB. Sea B
Rel pa alelepípedo añadido en la i e-
ación , el cual es pa e del complejo BR. Po consiguien e, B
R*RB, y dado que
∂RB∩in (BR) = ∅, se iene ambién ∂RB∩in (B
R) = ∅ya que in (B
R)⊆in (BR).
Usando que R −1⊆ RBllegamos a que in (B
R)∩ R −1=∅, lo que con adice la
cons ucción del pa alelepípedo R en la i e ación .
Deno emos po Wal núme o o al de pa alelepípedos que o man los complejos ba-
e a, es deci , con la no ación que enimos u ilizando, W=PN
i=1 mi. El Paso 1 del
Algo i mo 2.1 iene un cos e O(n), siendo nla dimensión del espacio Rnen el que
es emos abajando. Como se ha dicho en la demos ación del Lema 2.6, el Paso 2 se
ealiza a lo sumo W eces. Las comp obaciones ∂R ∩ in (Bj
i)6=∅del Paso 2 pa a los
pa alepípedos Bj
i∈Bi,j= 1, ..., mi,i= 1, ..., N, ienen un cos e O(n), pues pa a
lle a las a cabo sólo enemos que compa a los in e alos [κk−ξk, κk+ξk]de ambos
pa alelepípedos en cada coo denada k= 1, ..., n, además, es as comp obaciones se
ealiza án cada ez que llegamos al Paso 2 un núme o de eces aco ado po W(una
ez po cada uno de los pa alelepípedos que o man los complejos ba e a). Es ácil
obse a que la ac ualización de Rque se lle a a cabo en el Paso 2 iene un cos e O(n).
Po an o, una co a supe io asin ó ica pa a la ejecución del Algo i mo 2.1 es O(W2n).
28 2.3. Camino ec angula mínimo en p esencia de pa alelepípedos ba e a
Lema 2.7. Sea Bla unión de un conjun o ini o de complejos de pa alelepípedos iso é-
icos en Rndisjun os a dos a dos y sean X, Y ∈ F con F=Rn B. En onces, siemp e
exis e un X-Ycamino ec angula mínimo pe mi ido con enido en la en ol en e ec-
angula i e a i a RBde X,YyB.
Demos ación. Obsé ese que podemos asumi que no hay ba e as en Rn RBpues-
o que es a asunción sólo pod ía dec emen a la longi ud de los caminos ec angula es
que no es án con enidos en RBmien as que no iene e ec o sob e los caminos ec-
angula es que sí lo es án. Asumimos pues que no hay ba e as en Rn RB. Como
sabemos, el Lema 2.3, el Lema 2.4 y el Lema 2.5 implican la exis encia de un X-Y
camino ec angula mínimo pe mi ido Q. Supongamos que Qes al que Q*RB. Sean
(αi, ωi)los pa es de pun os de la on e a de RB, ales que, cuando consida amos Q
o ien ado desde Xhas a Y,Qabandona RBpo αiy uel e a en a en la en ol en e
ec angula i e a i a po ωi. La pa e del camino Qαi,ωide Qque a desde αiaωise
encuen a po an o comple amen e con enida en el ex e io de RB, sal o αiyωique
es án en la on e a. Lo que amos a demos a es que cada po ción Qαi,ωide Qpuede
se sus i uida po un αi-ωicamino ec angula de la misma longi ud con enido en la
on e a de RB, con lo que ob end íamos un X-Ycamino ec angula mínimo pe mi-
ido Q0con enido en RB.
Sean αyωcualquie a de los pa es de pun os mencionados an es y sea Qα,ω la
po ción de Qque los une. El camino Qα,ω es un α-ωcamino ec angula mínimo pe -
mi ido, pues de lo con a io, Q ampoco se ía un camino ec angula mínimo pe mi i-
do. Obsé ese que, pues o que Qα,ω ∩in (RB) = ∅, si conside amos a RBcomo una
ba e a, Qα,ω sigue siendo un α-ωcamino ec angula mínimo pe mi ido. Los pun os
αyωson los únicos pun os de Qα,ω que pe enecen a la on e a de RB, si seguimos
conside ando a la en ol en e ec angula i e a i a RBcomo una ba e a (la cual con-
end á a Bpo la asunción hecha al comienzo de la demos ación), po el Lema 2.4
(asumimos en adelan e que Rnes al que n≥3, la demos ación en R2es análoga
u ilizando el Lema 2.3), exis e un α-ωcamino pe mi ido `1-mínimo Plineal a ozos
con pun os c í icos solamen e en las ca as de dimensión meno o igual que n−2de
RB. Po el Lema 2.5, l(P) = l(Q). Sea [Ti, Ti+1]cualquie a de los segmen os que
o man P. Como Ti, Ti+1 ∈ RByRBes con exo po se un polied o, en conc e o un
hipe pa alelepípedo de dimensión n, el segmen o [Ti, Ti+1]⊆ RB. Pe o [Ti, Ti+1]es
un Ti-Ti+1 camino pe mi ido, luego debe es a con enido en la on e a de RB. Lo que
amos a p oba a con inuación es que exis e una ca a de dimensión n−1de RBque
con iene a [Ti, Ti+1].
Es sabido, que las ca as de dimensión kde RBson hipe pa alelepípedos de dimen-
sión k,k= 1, ..., n −1. Como Ties á en la on e a de RB, en onces alguna de las
coo denadas (Ti)jde Tidebe se igual a uno de los alo es ex emos κj−ξj, κj+ξjdel
pa alelepípedo RBen esa coo denada, siendo κjla j-ésima coo denada del cen o de
RByξjla mi ad de la anchu a en esa misma coo denada OXjde RB,j∈ {1, ..., n}.
De lo con a io siemp e pod ía encon a se una bola B(Ti, δ)⊆in (RB),δ > 0, lo cual
es una cons adicción con que Tipe enezaca a la on e a de RB. Lo mismo ocu e
2. Camino ec angula mínimo en p esencia de pa alelepípedos ba e a 29
con Ti+1. Si (Ti)j= (Ti+1)j=κj+sξjcon s∈ {−1,1}pa a alguna coo denada OXj,
j∈ {1, ..., n}, en onces TiyTi+1 es án con enidos en la ca a de dimensión n−1de RB
cons iuida po el hipe pa alalepípedo de dimensión n−1con enido en el hipe plano
Xj=κj+sξj. Si (Ti)j= (Ti+1)j6=κj+sξjpa a odo s∈ {−1,1}y oda coo denada
OXj,j= 1, ..., n, en onces puede comp oba se que κj−ξj<(Ti+Ti+1)j/2< κj+ξj
pa a odo j= 1, ..., n, es deci , el pun o medio de TiyTi+1, que es á con enido en
[Ti, Ti+1], pe enece al in e io de RB, lo cual es una con adicción pues [Ti, Ti+1]es
un camino pe mi ido po se lo P.
Como TiyTi+1 es án con enidos en un hipe pa alelepípedo de dimensión n−1,
cualquie camino ec angula que a de TiaTi+1 de o ma que en cada codo no i ial
de la sucesión se iguala una de las coo denadas de Tia la coo denada co espondien-
e de Ti+1 ( e Figu a 2.8), es á con enido en dicho pa alelepípedo que a su ez es á
con enido en la on e a de RB. Dichos Ti-Ti+1 caminos ec angula es ienen longi ud
`1(Ti, Ti+1), es deci , la misma que [Ti, Ti+1](Lema 2.2). De es a o ma, podemos sus-
i ui cada segmen o [Ti, Ti+1]de Ppo un Ti-Ti+1 camino ec angula pe mi ido de
su misma longi ud, siendo el esul ado de es a sus i ución un α-ωcamino ec angula
pe mi ido de la misma longi ud que Qα,ω con endio en la on e a de RB.
El Lema 2.7 nos dice que, a la ho a de encon a un X-Ycamino ec angula mínino
pe mi ido, podemos es ingi la búsqueda a F ∩ RBen luga de conside a odo F.
Es o implica que, en el P oblema 2.1, podemos ob ia odos los complejos de hipe -
pa alelepípedos ba e a que no es én con enidos en RB, pues no son necesa ios en el
cálculo de dB(X, Y ).
A con inuación, amos a ealiza un mallado sob e RB, de o ma que busca X-Y
caminos ec angula es mínimos pe mi idos sea equi alen e a esol e un p oblema de
camino mínimo en el g a o que cons i uye es a malla. La cons ucción de es a malla a
a eque i un a amien o dis in o según es emos en el caso plano o en Rncon n≥3.
Conside emos p ime o el caso bidimensional. Pa a cada pun o Z∈ {X, Y }∪P(B),
siendo P(B)el conjun o ini o de pun os ex emos de B, y pa a cada ec o undamen-
al ide la no ma ec angula , e ique ados como en el Ejemplo 1.2, y la co espondien e
di ección undamen al di,i= 1, ..., 4, sea
(Z+di)B:= {Z+λdi:λ∈R+,(Z+µdi)∩in (B)∩(R2 RB) = ∅ ∀0≤µ≤λ}
el conjun o de pun os del plano que son `2- isibles desde Zen la di ección undamen al
diden o de la en ol en e ec angula i e a i a RBde X,YyB. Di emos que (Z+di)B
es una línea de cons ucción ec angula .
De inición 2.7. En R2, la ed
N`1:= 
[
Z∈{X,Y }∪P(B)
4
[
i=1
(Z+di)B
∪ S(B)∪∂RB,
donde S(B)es el conjun o de las ca as de dimensión 1 de odos los complejos de
pa alelepípedos Bi,i= 1, ..., N, es la ed de cons ucción ec angula de X,YyB.

30 2.3. Camino ec angula mínimo en p esencia de pa alelepípedos ba e a
Los pun os de in e sección de los segmen os en N`1(los cuales pueden se ca as de
dimensión 1 de un complejo de pa alelepípedos ba e a o ca as de dimensión 1 de RB
o líneas de cons ucción ec angula ) de inen el conjun o P(N`1)de nodos de la ed,
yC(N`1)es el conjun o de celdas esul an es en RB in (B), i.e., el conjun o de po-
lied os con pun os ex emos en P(B). Nó ese que es os polied os que cons i uyen las
celdas son de hecho hipe pa alelepípedos iso é icos, pues los segmen os en N`1son
siemp e pa alelos a los ejes de coo denadas. Conside a emos que C(N`1)es á com-
pues o po los hipe pa alelepípedos iso é icos de dimensión 2 esul an es del mallado
que N`1p oduce en RB, así como po los hipe pa alelepípedos iso é icos de dimensión
1 (segmen os) esul an es de dicho mallado que no es án con enidos en los hipe pa a-
lelepípedos de dimensión 2 an e io es, de o ma que SC∈C(N`1)=RB in (B). En la
Figu a 2.11 se mues a un ejemplo de una ed de cons ucción ec angula N`1en R2.
Figu a 2.11: Red de cons ucción ec angula N`1de X,YyB=B1∪B2en R2. Los
hipe pa alelepípedos de dimensión 2 de C(N`1)se ap ecian cla amen e, mien as que
los de dimenión 1 se han señalado como líneas de mayo g oso (hay es).
Vamos a e aho a cómo podemos ealiza un mallado de RBen Rncon n≥3. Sea
Bun pa alelepípedo cualquie a en Rnde cen o κ= (κ1, ..., κn) y mi ad de la anchu a
en cada coo denada OXkigual a ξk,k= 1, ..., n. Las ca as de dimensión n−1de B
son los hipe pa alelepípedos de dimensión n−1dados po {(z1, ..., κj+sξj, ..., zn) ∈
Rn:κi−ξi≤zi≤κi+ξi, i = 1, ..., n, i 6=j}con j∈ {1, ..., n}ys∈ {−1,1}, y su
núme o es, po an o, 2n. Conside emos los hipe planos Hpa alelos a los hipe planos
OX1· · · Xj−1Xj+1 · · · Xn,j= 1, ..., n, y que co an a Búnicamen e en su on e a.
Cada uno de es os hipe planos con iene una ca a de dimensión n−1de B, el hipe -
plano Hdado po Xj=κj+sξjcon s∈ {−1,1}con iene al hipe pa alelepípedo
{(z1, ..., κj+sξj, ..., zn) ∈Rn:κi−ξi≤zi≤κi+ξi, i = 1, ..., n, i 6=j}de
dimensión n−1,j= 1, ..., n, luego su núme o es ambién 2n. En cuan o a lo planos
Πpa aleleos a los planos OXiXj,i, j = 1, ..., n,i<j, y que co an a Búnicamen e
2. Camino ec angula mínimo en p esencia de pa alelepípedos ba e a 31
en su on e a, su núme o es n(n−1)2n−3: el núme o de planos OXiXj,i, j = 1, ..., n,
i < j, es n
2, o lo que es los mismo, n(n−1)/2; pa a cada plano OXiXj, las posibi-
lidades de coloca lo en la on e a de Bson 2n−2, es o es, el núme o de posibilidades
de combina los alo es ex emos κk+sξk,s∈ {−1,1}, en las coo denadas es an es
OXk,k= 1, ..., n,k6=i, j. Así, n
22n−2=n(n−1)2n−3es ambién el núme o de
ca as (pa alelepípedos) de dimensión 2 de B.
Vol amos a nues o conjun o de complejos ba e as {B1, ..., BN}y omemos dos
pa alelepípedos Bj
i,Bh
kcualesquie a (que pueden pe enece al mismo complejo o in-
cluso se iguales), i, k ∈ {1, ..., N},j∈ {1, ..., mi},h∈ {1, ..., mk}. Sea Hun hipe -
plano de los an e io es pa a Bj
i al que la ca a de dimensión n−1que con iene de Bj
ino
es á comple amen e con enida en el in e io de Bi, y sea Πun plano de los desc i os an-
es pa a Bh
kque cumple ambién que la ca a de dimensión 2que con iene de Bh
kno es á
comple amen e con enida en el in e io de Bk. U ilizando la ó mula de la dimensión
sabemos que la in e sección de HyΠpuede se , o bien, una ec a, o bien, el p opio Π.
Nos in e esa sólo las in e secciones de HyΠque dan luga a ec as . Tomada la ec a
, que es necesa iamen e pa alela a uno de los ejes de coo denadas, nos quedamos con
los segmen os {S1, ..., SK}de que se ob ienen al ealiza el siguien e p ocedimien o:
en p ime luga , nos quedamos con el segmen o S= ∩ RBde ; y, en segundo luga ,
omamos los segmen os maximales {S1, ..., SK}de S ales SK
i=1 Si=S in (B). El nú-
me o de es os segmen os es ini o pues el núme o de pa alelepípedos de cada complejo
es ini o así como el númeo de ca as que poseen. Los segmen os {S1, ..., SK}son las
líneas de cons ucción ec angula p oducidas po el hipe plano Hy el plano Π. De la
misma o ma, podemos cons ui es as líneas conside ando ambién como hipe planos
Hy planos Πa los hipe planos pa alelos a OX1· · · Xj−1Xj+1 · · · Xn,j= 1, ..., n, y a
los planos pa alelos a OXiXj,i, j = 1, ..., n,i<j, que pasan po los pun os XeY
en e los que que emos calucla dB(X, Y ), así como a las ca as de dimensión n−1y 2
de RB. Los segmen os esul an es del p oceso al conside a es os planos e hipe planos
son ambién líneas de cons ucción ec angula en Rncon n≥3.
Obsé ese que, pues o que la ca a de dimensión n−1de Bj
ique con iene el hipe -
plano Hno es á comple amen e con enida en el in e io de Biy la ca a de dimensión 2
de Bh
kque con iene el plano Πno es á comple amen e con enida en el in e io de Bk,
HyΠcon ienen, espec i amen e, una ca a de dimensión n−1de Biy una ca a de
dimesnión 2de Bk. De hecho, en lo que es amos in e esados ealmen e es en in e seca
hipe planos que con ienen ca as de dimensión n−1de un complejo con planos que
con ienen ca as de dimensión 2de o o o el mismo complejo. Sin emba go, el p oce-
dimien o an e io cons i uye una o ma sencilla de ob ene las líneas de cons ucción
ec angula a pa i de los pa alelepípedos que cons i uyen los complejos, y no a pa i
de es os úl imos di ec amen e.
De inición 2.8. En Rncon n≥3, la ed de cons ucción ec angula N`1de X,YyB
es la o mada po la unión de las líneas de cons ucción ec angula desc i as en los
pá a os an e io es o madas en e odos los pa es posibles de hipe planos Hy planos
Πen las condiciones del mismo pá a o.
32 2.3. Camino ec angula mínimo en p esencia de pa alelepípedos ba e a
Al igual que en R2, los pun os de in e sección de los segmen os en N`1de inen el
conjun o P(N`1)de nodos de la ed, y C(N`1)es el conjun o de celdas esul an es en
RB in (B). Los polied os que cons i uyen las celdas de C(N`1)son aho a hipe pa a-
lelepípedos iso é icos de dimensión non−1. Pa a e es a úl ima a i mación enemos
que mos a que dado un pun o Z∈ P(N`1)exis e un segmen o que pa e de Zen
odas las di ecciones undamen ales isibles desde Z(es o es, si Zpe ece a la ca a
de dimensión n−1de un pa alepípedo que hace de ba e a o de RB, no iene sen i-
do conside a la di ección undamen al que al pa i de Zse in oduce inmedia amen e
después de Zen el in e io del pa alelepípedo o de RB). El pun o Zpuede se un pun o
ex emo de un segmen o de N`1o el esul ado de la in e sección de dos segmen os de
N`1. Supongamos que Zes un pun o ex emo de un segmen o de N`1. Sea la ec a a
la que pe enece dicho segmen o y a pa i de la cual se ob ienene el mismo. Sean Hy
Π, espec i amen e, el hipe plano y el plano cuya in e sección da luga a . Po an o,
Z∈ , H,Π. Supongamos, sin pé dida de gene alidad, que OX1es la di ección en la
que a ía , que Hes pa alelo al hipe plano X2= 0 y que Πes pa alelo al plano que
a ía en las di ecciones OX1yOX2siendo cons an e en el es o. Po la cons ucción
desc i a de N`1, el que Zsea un pun o ex emo de un segmen o Sde N`1signi ica que
exis e una ca a de dimensión n−1de un pa alelepípedo de los complejos ba e as o
de RBque impide que el segmen o Sse p olongue po Zen la di ección OX1. Sea H0
el hipe plano que con iene a dicha ca a, el cual se á pa alelo al hipe plano X1= 0. Se
iene, po an o, Z∈ H0. Po úl imo conside emos una ca a de dimensión n−1que
con iene a la ca a de dimensión 2del pa alelepípedo o de RBque da luga al plano Π,
en caso de que Π enga algunos de es os o ígenes. Sea H00 el hipe plano que la con ie-
ne, el cual es pa alelo al hipe plano Xj= 0 con j6= 1,2. Si Πes un plano que pasa
po XoY, en onces igualmen e omamos un hipe plano H00 que pase po XoYy que
con enga a Π. También en es e caso H00 es pa alelo al hipe plano Xj= 0 con j6= 1,2.
Como Z∈Πse iene Z∈ H00. Po úl imo, obse emos que H,H0yH00 son odos
hipe planos que in e ienen en la cons ucción de N`1(con ienen a ca as de dimensión
n−1de pa alelepípedos no con enidas comple amen e en el in e io del complejo co-
espondien e, o de RB, o pasan po XoY), po an o, dado cualquie sen ido pa a una
di ección OXk, nó ese que siemp e puede oma se uno de es os hipe planos y un plano
con enido en o o de los hipe planos que pase po Z(plano que in e iene ambién
en la cons ucción de N`1) cuya in e sección dé luga a un segmen o de N`1que pasa
po Zy con inúa en el sen ido dado de OXksi es o es posible. Si Zes el esul ado
de la in e sección de dos segmen os de N`1se azona de la misma o ma. Las celdas
de dimensión n−1de C(N`1)son las con enidas en las ca as de dimensión n−1de
RBy se deben, en el caso de que ocu an, a las in e secciones de las on e as de los
complejos con la on e a de RB.
Analicemos cuál es el cos e compu acional de la cons ucción de N`1. La ed de
cons ucción ec angula N`1es una ed geomé ica de e minada po sus nodos P(N`1)
y los segmen os (con su longi ud co espondien e) que los unen, po an o, de e mina-
dos es os enemos aquella. Comencemos po el caso bidimensional. Sea Σel núme o
2. Camino ec angula mínimo en p esencia de pa alelepípedos ba e a 33
de pun os en {X, Y }∪P(B), siendo P(B)el conjun o ini o de pun os ex emos de
B, y sea W=PN
i=1 miel núme o o al de pa alelepípedos que o man los complejos
ba e a de B. En p ime luga enemos que ob ene RBcon un cos e de O(W2). Dado
un pun o de {X, Y }∪P(B) enemos que conside a las cua o líneas de cons uc-
ción ec angula que pa en de él. Pa a sabe has a dónde se ex ienden dichas líneas
debemos de ec a si in e secan el in e io de los pa alelepípedos que cons i uyen los
complejos ba e a, así como si in e secan alguna de las ca as de dimensión 1 de RB.
Las comp obación de in e sección con el in e io de un pa alelepípedo así como con
una ca a de dimensión 1 de RBse ealiza en iempo cons an e. Las líneas de cons uc-
ción se ob ienen, po an o, en un iempo de O(4Σ)O(W+ 4) = O(ΣW). El núme o
de líneas de cons ucción es á aco ado po O(Σ). Pa a ob ene los pun os P(N`1)y
di idi las líneas de cons ucción en segmen os debemos comp oba las in e secciones
en e líneas de cons ucción, lo que iene un cos e O(Σ2). Pa a ob ene la longi ud de
los segmen os, omamos cada línea de cons ucción y la eco emos calculando la dis-
ancia en e nodos adyacen es en dicha línea, como el núme o de nodos en una línea
de cons ucción es a lo sumo O(Σ), las longi udes de los segmen os se hallan en un
iempo O(Σ2). Luego N`1se ob iene en O(m´ax{W2,Σ2}). Pues o que si los comple-
jos es án adecuademen e desc i os po sus pa alelepípedos W < Σ,N`1se iene en un
iempo O(Σ2).
En Rncon n≥3, el paso inicial del cálculo de RBconlle a un iempo O(W2n). La
in e seccion de odos los hipe planos Hcon los planos Πpa a ob ene las ec as iene
un cos e O(W2n42n−3)( éase la discusión sob e el núme o de ca as de dimensión n−1
y2de un pa alelepípedo en Rnen los pá a os p eceden es, y considé ese que la in e -
sección de un hipe plano y un plano en Rn equie e un núme o O(n)de ope aciones).
La di isión en segmen os de cada ec a equie e comp oba la in e sección de és a
con el in e io de odos los pa alelepípedos que cons i uyen los complejos, cada una de
es as comp obaciones se ealiza en O(n), luego la di isión de odas las ec as en seg-
men o iene un cos e O(W3n52n−3). Po ese mismo cos e calculamos las longi udes de
los segmen os. Pa a ob ene los pun os P(N`1)debemos comp oba las in e secciones
(cada comp obación de in e sección equie e O(n)ope aciones) en e los segmen os
an e io es, lo que iene un cos e O(W6n1122n−6). Si dos segmen os in e secan en un
pun o es os deben di idi se en nue os segmen os cuyas longi udes deben se calculadas
(pa a que es o se en ienda, al in e seca [(1,0) ,(1,2) ]con [(0,1) ,(2,1) ], debemos
calcula la longi ud de los segmen os [(1,0) ,(1,1) ],[(1,1) ,(1,2) ],[(0,1) ,(1,1) ]
y[(1,1) ,(2,1) ], pues (1,1) es un nue o nodo), pe o es e cálculo puede ealiza se en
iempo cons an e en el mismo momen o en el que se ob iene los pun os P(N`1). Po
an o, la ob ención de N`1en Rncon n≥3 iene un cos e O(W6n1122n−6).
Teo ema 2.1. El P oblema 2.1 es equi alen e al p oblema de halla el camino mínimo
en e XeYen la ed geomé ica N`1.
Demos ación. En p ime luga , obsé ese que e ec i amen e Xes es un nodo de N`1,
el cual se ob iene po la in e sección sucesi a en e los hipe planos Hpa alelos a los
40 2.3. Camino ec angula mínimo en p esencia de pa alelepípedos ba e a
j= 1, ..., n, es equi alen e al p oblema de p og amación lineal y en e a mix a
m´ın d(2.6)
s.a: d≥d0−(1 −ω0)M2,(2.7)
d≥dk s −(1 −ωk s)M2,∀k= 1, ..., n, = 1, ..., n, 6=k, s =−1,1,(2.8)
ω0+X
k= 1, ..., n, = 1, ..., n,
6=k, s =−1,1
ωk s = 1,(2.9)
u+
jk −u−
jk =xj
k−κk,∀j= 1,2, k = 1, ..., n, (2.10)
u+
jk ≤Mδjk,∀j= 1,2, k = 1, ..., n, (2.11)
u−
jk ≤M(1 −δjk),∀j= 1,2, k = 1, ..., n, (2.12)
dc
jk =u+
jk +u−
jk,∀j= 1,2, k = 1, ..., n, (2.13)
d0
k≥x1
k−x2
k,∀k= 1, ..., n, (2.14)
d0
k≥x2
k−x1
k,∀k= 1, ..., n, (2.15)
dζ
jks ≥xj
k−(κk+sξk),∀j= 1,2, k = 1, ..., n, s =−1,1,(2.16)
dζ
jks ≥(κk+sξk)−xj
k,∀j= 1,2, k = 1, ..., n, s =−1,1,(2.17)
dc
jk ≥ξk−ξkλ1
jk,∀j= 1,2, k = 1, ..., n, (2.18)
X
h=1,...,n,h6=k
λ1
jh ≤(n−2) + λ2
jk,∀j= 1,2, k = 1, ..., n, (2.19)
λ2
1k+λ2
2k≤1+Λk,∀k= 1, ..., n, (2.20)
−∆k≤δ1k−δ2k≤∆k,∀k= 1, ..., n, (2.21)
Λk+ ∆k≤1+Ωk,∀k= 1, ..., n, (2.22)
d0=X
k=1,...,n
d0
k+MX
h=1,...,n
Ωh,(2.23)
dk s =dζ
1 s +dζ
2 s +X
h=1,...,n,h6=
d0
h+MX
=1,...,n, 6=k
Ω ,
∀k= 1, ..., n,
= 1, ..., n,
6=k,
s=−1,1,
(2.24)
d, d0≥0,(2.25)
d0
k≥0,∀k= 1, ..., n, (2.26)
dk s ≥0, ωk s ∈ {0,1},∀k= 1, ..., n, = 1, ..., n, 6=k, s =−1,1,(2.27)
u+
jk, u−
jk, dc
jk ≥0, λ1
jk, λ2
jk, δjk ∈ {0,1},∀j= 1,2, k = 1, ..., n, (2.28)
dζ
jks ≥0,∀j= 1,2, k = 1, ..., n, s =−1,1,(2.29)
Λk,∆k,Ωk∈ {0,1},∀k= 1, ..., n, (2.30)
siendo M > 0una cons an e lo su icien emen e g ande.
Demos ación. En (2.25)-(2.30) se de ine la na u aleza de las a iables de decisión: d
es una a iable posi i a que en el óp imo oma á el alo dB(X1, X2);d0
1, ..., d0
nson

2. Camino ec angula mínimo en p esencia de pa alelepípedos ba e a 41
ambién a iables posi i as que en el óp imo oma án los alo es |x1
1−x2
1|, ..., |x1
n−x2
n|,
espec i amen e, si es os alo es son necesa ios pa a el cálculo de dB(X1, X2); la
a iable dk s ep esen a el alo de la dis ancia dB(X1, X2)en el caso de que X1
yX2no sean `1- isibles debido a que P oyˆ
k(X1),P oyˆ
k(X2)∈in (P oyˆ
k(B)) y
m´ın{x1
k, x2
k}< κk<m´ax{x1
k, x2
k}, y el meno X1-X2camino ec angula pe mi i-
do sea el de longi ud Pi=1,...,n,i6= |x1
i−x2
i|+|x1
−(κ +sξ )|+|x2
−(κ +sξ )|,
mien as que ωk s es una a iable bina ia que oma á el alo 1si e ec i amen e X1y
X2se encuen an en ese caso y 0en caso con a io; u+
jk,u−
jk ydc
jk oma án, espec i a-
men e, los alo es |xj
k−κk|si xj
k≥κko0en caso con a io, |xj
k−κk|si xj
k≤κko0
en caso con a io, y |xj
k−κk|; las a iables dζ
jks son a iables posi i as que ep esen an
los alo es |xj
k−(κk+sξk)|necesa ios pa a el cálculo de dB(X1, X2)en los di e en es
casos; λ1
jk,λ2
jk yΛkson a iables bina ias que de e mina án la posición ela i a de las
coo denadas de X1yX2con espec o a las p oyecciones en P oyˆ
k(·)de B;δjk y∆k
son a iables bina ias que de e mina án la posición ela i a de x1
kyx2
kcon espec o al
cen o de B; las a iables bina ias Ωkde ec an si X1yX2son `1- isibles o no.
Las es icciones (2.10), (2.11) y (2.12) hacen que u+
jk ome el alo |xj
k−κk|si
xj
k> κk, en cuyo caso δjk = 1, y que u−
jk ome el alo |xj
k−κk|si xj
k< κk, en
cuyo caso δjk = 0. Po an o, con (2.13) se consigue que dc
jk ome el alo |xj
k−κk|.
En (2.14)-(2.15) se impone que d0
k≥ |x1
k−x2
k|. Las es icciones (2.16) y (2.17) obli-
gan a dζ
jks a oma alo es mayo es o iguales que |xj
k−(κk+sξk)|. La es icción
(2.18) hace que la a iable bina ia λ1
jk ome el alo 1si dc
jk < ξj, pudiendo oma
el alo 0o1en caso con a io. Po la an o, la es icción (2.19) hace que la a-
iable bina ia λ2
jk ome el alo 1si P oyˆ
k(Xj)∈in (P oyˆ
k(B)), pudiendo oma el
alo 0o1en caso con a io. La es icción (2.20) ue za a que Λk oma el alo 1
si an o P oyˆ
k(X1)como P oyˆ
k(X2)pe enecen a in (P oyˆ
k(B)), pudiendo oma el
alo 0o1en caso con a io. Obsé ese que si m´ın{x1
k, x2
k}< κk<m´ax{x1
k, x2
k},
en onces δ1k−δ2kes 1o−1, en caso con a io δ1k−δ2k= 0 (pudiendo se 1si
se da alguna de las igualdades en m´ın{x1
k, x2
k} ≤ κk≤m´ax{x1
k, x2
k}), luego (2.21)
obliga a que ∆k= 1 si m´ın{x1
k, x2
k}< κk<m´ax{x1
k, x2
k}, pudiendo oma el
alo 0o1en caso con a io. Teniendo en cuen a lo an e io , po (2.22), Ωk= 1
si P oyˆ
k(X1),P oyˆ
k(X2)∈in (P oyˆ
k(B)) ym´ın{x1
k, x2
k}< κk<m´ax{x1
k, x2
k},
cosa que sabemos sólo puede da se en odo caso pa a un k∈ {1, ..., n}, en ca-
so con a io Ωkpuede oma el alo 1o0. En (2.23)-(2.24) se calcula dB(X1, X2)
según la si uación en la que X1yX2se encuen en de acue do al Lema 2.9. En
2.23, a d0(que ep esen a la dis ancia `1(X1, X2)) se le aplica una penalización si
X1yX2no son `1- isibles (es o es, si Ωk= 1 pa a algún k∈ {1, ..., n}). Las
dis ancias dk s ambién son penalizadas si Ωj= 1 pa a algún j∈ {1, ..., n}con
j6=k(es deci , si P oyˆ
j(X1),P oyˆ
j(X2)∈in (P oyˆ
j(B)) ym´ın{x1
j, x2
j}< κj<
m´ax{x1
j, x2
j}). El p oblema de p og amación ma emá ica iene es uc u a de p oble-
ma minimín debido a (2.6)-(2.9), que hacen que se calcule dB(X1, X2)de la o ma
adecuada según el caso: si X1yX2son `1- isibles en onces d0es la meno de las dis-
42 2.3. Camino ec angula mínimo en p esencia de pa alelepípedos ba e a
ancias que se puede selecciona ; si se da P oyˆ
k(X1),P oyˆ
k(X2)∈in (P oyˆ
k(B))
ym´ın{x1
k, x2
k}< κk<m´ax{x1
k, x2
k}, en onces d0ydj s con j6=kson pena-
lizadas, se escoge á en onces en e las dis ancias dk s, cumpliéndose en el óp imo
d= m´ın =1,....,n, 6=k,s=−1,1{dk s}=dB(X1, X2).
Es necesa io en (2.7) y (2.8) que Mes é ele ada al cuad ado pa a que no pueda
anula se con las penalizaciones que se aplican a d0y a cada dk s en (2.23) y (2.24).
Como se ha dicho, en (2.14)-(2.15) se impone que d0
k≥ |x1
k−x2
k|y en (2.16)-(2.17)
que dζ
jks ≥ |xj
k−(κk+sξk)|, dado que en (2.6) se es á minimizando d, en la solución
óp ima del p oblema se da la igualdad pa a las a iables que ep esen en dis ancias
necesa ias pa a el cálculo de la longi ud del camino ec angula pe mi ido óp imo. To-
das las a iables bina ias cuyo alo no quedaba ijado en de e minadas si uaciones,
pudiendo oma los alo es 0o1, oma án el alo 0en dichas ci cus ancias, de lo
con a io se aplica ían penalizaciones en (2.23)-(2.24) que aumen a ían el alo de la
unción obje i o innecesa iamen e.
En el Teo ema 2.2, una elección álida pa a Mes nm´axi=1,...,n{2ξ0
i}+ε, siendo ξ0
ila
mi ad de la anchu a en la coo denada OXide la en ol en e ec angula i e a i a RB
de X,YyB, y εcualquie cons an e es ic amen e posi i a. Muchas de las a iables
de (2.6)-(2.30) (d0,d0
k,dc
jk,dζ
jks,...) ep esen an alo es que, de hecho, podemos ob-
ene an es de plan ea el p oblema de p og amación ma emá ica, pues o que es amos
suponiendo que X1yX2son ijos, de es a o ma se educi ía el núme o de a ia-
bles bina ias usadas en la o mulación (δjk, los alo es λ1
jk yλ2
jk se pod ían sabe de
an emano,...), sin emba go, la o mulación (2.6)-(2.30) es una o mulación gene al pa-
a cualquie pa de pun os X1yX2de la egión ac ible, que pueden supone se no
ijos, lo que pe mi e in eg a la en o mulaciones pa a p oblemas más gene ales que
equie an esol e el p oblema al que (2.6)-(2.30) da solución como subp oblema. Las
o mulaciones que apa ece án en el es o del capí ulo es án dadas de o ma que pueda
supone se que los pun os X1yX2no son ijos, lo que pe mi i á usa las pa a esol-
e los p oblemas que se plan ea án en los siguien es capí ulos. Aún así, el núme o
de a iables bina ias empleadas en la o mulación (2.6)-(2.30) puede educi se como
mues a el siguien e lema.
Lema 2.10. El p oblema de p og amación ma emá ica (2.6)-(2.30) es equi alen e al
p oblema esul an e de hace en és e los siguien es cambios: conside a las a iables
de decisión ∆k,k= 1, ..., n, en (2.30) como a iables posi i as en luga de a iables
bina ias y sus i ui la es icción (2.21) po las es icciones:
∆k≤1,∀k= 1,2,(2.31)
∆k≥δ1k−δ2k,∀k= 1, ..., n, (2.32)
∆k≥δ2k−δ1k,∀k= 1, ..., n. (2.33)
Demos ación. La a iable ∆kse compo e de la siguien e o ma: si m´ın{x1
k, x2
k}<
κk<m´ax{x1
k, x2
k}, en onces δ1k−δ2kes 1o−1, obligando a ∆ka oma el alo 1
2. Camino ec angula mínimo en p esencia de pa alelepípedos ba e a 43
po las es icciones (2.31)-(2.33); si δ1k−δ2k= 0 yΛk= 1,∆kpuede oma odos
los alo es del in e alo [0,1], sin emba go, si ∆k omase un alo es ic amen e mayo
que ce o, la es icción (2.22) ac i a ía la a iable bina ia Ωk, con lo que se p oduci ía
un aumen o del alo de la unción obje i o (2.6) debido a penalizaciones innecesa ias
p oducidas po las es icciones (2.23)-(2.24), luego en es e caso ∆k oma á el alo
0; po úl imo, si δ1k−δ2k= 0 yΛk= 0, el alo que ome ∆kno in luye en el alo
de la unción obje i o (2.6). Po an o, es e cambio no a ec a a la solución óp ima que
p opo ciona el p oblema de p og amación ma emá ica (2.6)-(2.30).
Conseguida una o mulación pa a el P oblema 2.1 cuando B=Bes un único pa a-
lelepípedo en Rn, pasemos a es udia el caso en el que B=B1∪B2, siendo B1yB2dos
hipe pa alelepípedos de dimensión ndisjun os de cen os (κ2
1, ..., κ1
n) y(κ2
1, ..., κ2
n) ,
y mi ad de la anchu a en cada coo denada ξ1
jyξ2
j,j= 1, ..., n, espec i amen e. Bajo
las condiciones que indica el siguien e lema, la o mulación (2.6)-(2.30) es su icien e
pa a esol e es e caso pa icula del P oblema 2.1.
Lema 2.11. Si P oyˆ
k(B1)∩P oyˆ
k(B2) = ∅,∀k= 1, ..., n, en onces dB(X, Y ) =
m´ax{dB1(X, Y ), dB2(X, Y )}.
Demos ación. Dado que la educción de la egión ac ible sólo puede p o oca un
aumen o de la dis ancia con ba e as y no al con a io, es e iden e que dB(X, Y )≥
dB1(X, Y ), dB2(X, Y ). Si XeYson `1- isibles en onces el esul ado se iene de o -
ma i ial ya que dB(X, Y ) = dB1(X, Y ) = dB2(X, Y ) = `1(X, Y ). Supongamos
que XeYno son `1- isibles. En onces, debe da se pa a algún j∈ {1, ..., n}, o bien,
P oyˆ
j(X),P oyˆ
j(Y)∈in (P oyˆ
j(B1)) ym´ın{xj, yj}< κ1
j<m´ax{xj, yj}, o bien,
P oyˆ
j(X),P oyˆ
j(Y)∈in (P oyˆ
j(B2)) ym´ın{xj, yj}< κ2
j<m´ax{xj, yj}, o am-
bas si uaciones, ya que de lo con a io, azonando como en la demos ación del Lema
2.9, pod íamos cons ui un X-Ycamino ec angula pe mi ido de longi ud `1(X, Y ),
lo que con adice la suposición de que XeYno son `1- isibles. Supongamos que
se iene P oyˆ
j(X),P oyˆ
j(Y)∈in (P oyˆ
j(B1)) ym´ın{xj, yj}< κ1
j<m´ax{xj, yj}.
Conside emos el X-Ycamino ec angula Q1de la o ma (2.5) y de longi ud míni-
ma cuando sólo se conside a a B1como ba e a ob iando B2. Como P oyˆ
k(B1)∩
P oyˆ
k(B2) = ∅,∀k= 1, ..., n, obsé ese que ninguno de los segmen os que cons-
i uyen Q1puede se in e secados po el in e io de B2, luego Q1es un X-Yca-
mino ec angula pe mi ido de longi ud dB1(X, Y ). Si se iene P oyˆ
k(X),P oyˆ
k(Y)∈
in (P oyˆ
j(B2)) ym´ın{xj, yj}< κ2
j<m´ax{xj, yj}pa a algún k∈ {1, ..., n}, si-
guiendo el azonamien o que acabamos de hace pa a el pa alelepípedo B1, ob en-
d íamos un X-Ycamino ec angula pe mi ido Q2de longi ud dB2(X, Y ). En caso
con a io dB1(X, Y )≥dB2(X, Y ) = `1(X, Y ). Concluimos así que dB(X, Y ) =
m´ax{dB1(X, Y ), dB2(X, Y )}.
En las condiciones del Lema 2.11, la es a egia de esolución del p oblema que nos
ocupa es sencillamen e la seguien e: calcula dB1(X, Y )ydB2(X, Y )independien-
emen e esol iendo sendos p oblemas de p og amación ma emá ica (2.6)-(2.30), y
44 2.3. Camino ec angula mínimo en p esencia de pa alelepípedos ba e a
oma el X-Ycamino ec angula solución de es os p oblemas de mayo longi ud.
La comp obación de si P oyˆ
k(B1)∩P oyˆ
k(B2) = ∅pa a algún k∈ {1, ..., n}pue-
de hace se en iempo O(n)compa ando los pa es de in e alos [κ1
j−ξ1
j, κ1
j+ξ1
j],
[κ2
j−ξ2
j, κ2
j+ξ2
j],j= 1, ..., n. Nó ese, que si B=SN
i=1 Bi, siendo {B1, ..., BN}
un conjun o de hipe pa alelepípedos de dimensión ndisjun os dos a dos ales que
P oyˆ
k(Bi)∩P oyˆ
k(Bj) = ∅,∀k= 1, ..., n,∀i, j = 1, ..., N con i6=j, el Lema 2.11
puede ex ende se a es e caso y la es a egia an e io de calcula odos las dis ancias
dBi(X, Y ),i= 1, ..., N, y queda nos con la mayo , segui ía siendo álida.
Si no se da P oyˆ
k(B1)∩P oyˆ
k(B2) = ∅,∀k= 1, ..., n, en onces P oyˆ
j(B1)∩
P oyˆ
j(B2)6=∅, pa a un único j∈ {1, ..., n}, pues los pa alelepípedos son iso é icos.
Sean V1=κ1
j+hξ1
jyV2=κ2
j+iξ2
jcon h, i ∈ {−1,1} ales que |V1−V2|es
mínimo, es deci , las coo denadas en OXjde las ca as de dimensión n−1de B1yB2,
espec i amen e, más ce canas en e sí. La coo denada j-ésima al que P oyˆ
j(B1)∩
P oyˆ
j(B2)6=∅así como los alo es V1yV2pueden ob ene se en iempo O(n), pues-
o que la p ime a se ob iene en O(n)y los segundos median e un núme o cons an e de
compa aciones una ez ob enida la an e io . Supongamos sin pé dida de gene alidad
que V1< V 2. Obsé ese que la egión R(V1, V 2) := {Z∈Rn:V1≤zj≤V2}
sepa a a los pa alelepípedos B1yB2en el siguien e sen ido: la ca a de dimensión n−1
de B1en la que la coo denada OXjes cons an e e igual a V1pe enece a la on e a
de R(V1, V 2), así como la ca a de dimensión n−1de B2en la que coo denada OXj
es cons an e e igual a V2, no exis iendo pun os de B1ni B2en in (R(V1, V 2)). En-
onces, no es di ícil e (pa a ello bas a conside a a gumen os simples basados en la
en ol en e ec angula i e a i a como los u ilizados en p uebas an e io es) que se iene
la siguien e casuís ica (u ilizamos de nue o la no ación X1=XyX2=Y):
(a) Si V1≤x1
j, x2
j≤V2en onces dB1∪B2(X1, X2) = `1(X1, X2).
(b) Si x1
j, x2
j≤V2en onces dB1∪B2(X1, X2) = dB1(X1, X2).
(c) Si x1
j, x2
j≥V1en onces dB1∪B2(X1, X2) = dB2(X1, X2).
(d) Si x1
j≤V1yx2
j≥V2en onces exis e ρ∈Rncon V1≤ρk≤V2 al que
dB1∪B2(X1, X2) = dB1(X1, ρ) + dB2(ρ, X2).
(e) Si x2
j≤V1yx1
j≥V2en onces exis e ρ∈Rncon V1≤ρk≤V2 al que
dB1∪B2(X1, X2) = dB1(X2, ρ) + dB2(ρ, X1).
Las Figu as 2.12, 2.13, 2.14 y 2.15 ilus an es a casuís ica en R2cuando P oyˆ
1(B1)∩
P oyˆ
1(B2)6=∅.
2. Camino ec angula mínimo en p esencia de pa alelepípedos ba e a 45
Figu a 2.12: Caso (a).
Figu a 2.13: Caso (b).
Figu a 2.14: Caso (c).

46 2.3. Camino ec angula mínimo en p esencia de pa alelepípedos ba e a
Figu a 2.15: Caso (d) (el caso (e) es simila ).
Si w1
1es una a iable de decisión bina ia, la es icción
V1−M(1 −w1
1)≤x1
j≤V1+Mw1
1,
siendo M > 0una cons an e los su icien emen e g ande, hace que w1
1= 0 si x1
j< V 1,
w1
1= 1 si x1
j> V 1, mien as que si x1
j=V1en onces w1
1puede oma el alo 0o
1. Po an o, las posiciones ela i as de la coo denada j-ésima de los pun os X1yX2
con espec o a V1yV2, las cuales nos pe mi en de ec a en que caso de la casuís ica
an e io se encuen an los pun os X1yX2, pueden de e mina se median e el conjun o
de es icciones:
V1−M(1 −wi
1)≤xi
j≤V1+Mwi
1,∀i= 1,2,(2.34)
V2−M(1 −wi
2)≤xi
j≤V2+Mwi
2,∀i= 1,2,(2.35)
wi
h∈ {0,1},∀i= 1,2, h = 1,2.(2.36)
En la casuís ica (a)-(e), podemos conside a sólamen e los casos (b), (c), (d) y (e),
pues el caso (a) es á con emplado an o en (b) como en (c). Es deci , si se da (a),
en onces:
(a) ⇒(b) ⇒dB1∪B2(X1, X2) = dB1(X1, X2) = `1(X1, X2),
(a) ⇒(c) ⇒dB1∪B2(X1, X2) = dB2(X1, X2) = `1(X1, X2).
Además, obsé ese que los casos (d) y (e) son excluyen es pues es amos suponiendo
V1< V 2. Si φ1,φ2,φ3yφ4son a iables bina ias que ep esen an, espec i amen e,
la ocu encia de los casos (b), (c), (d) y (e), cuando oman el alo el 1, en onces, a
pa i de las posiciones ela i as de x1
jyx2
jcon espec o a V1yV2de ec adas po las
a iables bina ias wi
h,i= 1,2, h = 1,2, podemos de e mina en cuál de los casos nos
2. Camino ec angula mínimo en p esencia de pa alelepípedos ba e a 47
encon amos median e las es icciones:
4
X
k=1
φk= 1,(2.37)
φ1≤(1 −w1
2) + (1 −w2
2),(2.38)
φ2≤w1
1+w2
1,(2.39)
φ3≥w2
2−w1
1,(2.40)
φ4≥w1
2−w2
1,(2.41)
φk∈ {0,1},∀k= 1, ..., 4.(2.42)
La es icción (2.37) ue za a que se seleccione uno y sólo uno de los casos. La es-
icción (2.38) indica que si x1
j, x2
j> V 2en onces no puede da se el caso (b), de la
misma o ma, la es icción (2.39) indica que si x1
j, x2
j< V 1en onces no puede da se
el caso (c). Si x1
j< V 1yx2
j> V 2en onces necesa iamen e φ3= 1 ( es icción (2.40))
y si x2
j< V 1yx1
j> V 2en onces necesa iamen e φ4= 1 ( es icción (2.41)). Cuando
es as es icciones se in eg en al modelo co espondien e, el cuál es a á minimizando
dB1∪B2(X1, X2)en la unción obje i o, siemp e se in en a á que φ1= 1 oφ2= 1,
pues dB1∪B2(X1, X2)es meno en los casos (b) y (c) que en los casos (d) y (e). Si se
da el caso (d) o (e) (sólo puede da se uno de ellos) en onces necesa iamen e φ3= 1 o
φ4= 1, no pudiendo hace se φ1= 1 oφ2= 1. Luego, las es icciones (2.37)-(2.42)
de ec an adecuadamen e el caso en el que se encuen an los pun os X1yX2. Puede
comp oba se que, en los casos ex emos en los que los wi
hpueden oma los alo es
0o1, las es icciones (2.37)-(2.42) siguen de ec ando adecuadamen e el caso de la
casuís ica (b)-(e) en el que se encuen an los pun os X1yX2, pues en dichos casos
ex emos podemos encon a nos en di e en es casos de la casuís ica (b)-(e) a la ez.
Sean %1, %2, %3∈Rn. La dis ancia dB1(%1, %2)puede calcula se adap ando la o -
mulación (2.6)-(2.30) a los pun os %1,%2y a la ba e a B1. Pa a ello, bas a sus i ui
en (2.6)-(2.30) los papeles de X1yX2po los de %1y%2, y el de Bpo B1. Lla-
memos d12 a la a iable posi i a que hab ía que minimiza en la unción obje i o del
p oblema de p og amación ma emá ica esul an e (la que en (2.6)-(2.30) e a simple-
men e d). De la misma o ma, la dis ancia dB2(%2, %3)puede calcula se adap ando la
o mulación (2.6)-(2.30) a los pun os %2,%3y a la ba e a B2. Llamemos aho a d23 a
la a iable posi i a que hab ía que minimiza en la unción obje i o del nue o p oble-
ma de p og amación ma emá ica esul an e. Conside emos el siguien e p oblema de
p og amación ma emá ica:
m´ın d12 +d23
s.a: (2.6)-(2.30), adap adas pa a el cálculo de dB1(%1, %2),(2.43)
(2.6)-(2.30), adap adas pa a el cálculo de dB2(%2, %3).(2.44)
Po lo dicho an es es á cla o que es e p oblema de p og amación ma emá ica calcu-
la dB1(%1, %2) + dB2(%2, %3). Vamos a acla a en qué sen ido podemos apoya nos en
48 2.3. Camino ec angula mínimo en p esencia de pa alelepípedos ba e a
es a o mulación pa a esol e nues o p oblema. Obsé ese que si es amos en el ca-
so (b) de nues a casuís ica en onces dB1(%1, %2) + dB2(%2, %3)es dB1∪B2(X1, X2) =
dB1(X1, X2)si %1=X1,%2=X2y%3=X2. Si es amos en el caso (c) en onces
dB1(%1, %2) + dB2(%2, %3)es dB1∪B2(X1, X2) = dB2(X2, X2)si %1=X1,%2=X1
y%3=X2. En el caso de encon a nos en el caso (d), dB1(%1, %2) + dB2(%2, %3)es
dB1∪B2(X1, X2) = dB1(X1, ρ) + dB2(ρ, X2)si %1=X1,%2=ρy%3=X2, siendo
ρ∈R(V1, V 2). Po úl imo, en el caso de encon a nos en el caso (e), dB1(%1, %2) +
dB2(%2, %3)es dB1∪B2(X1, X2) = dB1(X2, ρ) + dB2(ρ, X1)si %1=X2,%2=ρy
%3=X1, siendo ρ∈R(V1, V 2). Luego, si conseguimos ija adecuadamen e los
alo es de %1,%2y%3según el caso, end íamos la o mulación de un p oblema de
p og amación ma emá ica que equi ald ía a nues o p oblema. Si ρ∈R(V1, V 2), u i-
lizando las a iables de decisión bina ias φk,k= 1, ..., 4, que indicaban el caso en el
que nos encon ábamos (y de las cuales sólo una podía oma el alo 1), los alo es de
%1,%2y%3pueden ija se median e las es icciones
x1
k−M(1 −φ1)≤%1k≤x1
k+M(1 −φ1), k = 1, ..., n, (2.45)
x2
k−M(1 −φ1)≤%2k≤x2
k+M(1 −φ1), k = 1, ..., n, (2.46)
x2
k−M(1 −φ1)≤%3k≤x2
k+M(1 −φ1), k = 1, ..., n, (2.47)
x1
k−M(1 −φ2)≤%1k≤x1
k+M(1 −φ2), k = 1, ..., n, (2.48)
x1
k−M(1 −φ2)≤%2k≤x1
k+M(1 −φ2), k = 1, ..., n, (2.49)
x2
k−M(1 −φ2)≤%3k≤x2
k+M(1 −φ2), k = 1, ..., n, (2.50)
x1
k−M(1 −φ3)≤%1k≤x1
k+M(1 −φ3), k = 1, ..., n, (2.51)
ρk−M(1 −φ3)≤%2k≤ρk+M(1 −φ3), k = 1, ..., n, (2.52)
x2
k−M(1 −φ3)≤%3k≤x2
k+M(1 −φ3), k = 1, ..., n, (2.53)
x2
k−M(1 −φ4)≤%1k≤x2
k+M(1 −φ4), k = 1, ..., n, (2.54)
ρk−M(1 −φ4)≤%2k≤ρk+M(1 −φ4), k = 1, ..., n, (2.55)
x1
k−M(1 −φ4)≤%3k≤x1
k+M(1 −φ4), k = 1, ..., n, (2.56)
donde %ik ep esen a la k-ésima coo denada de %iyρkla k-ésima coo denada de ρ.
Teniendo en cuen a la discusión an e io , una o mulación pa a esol e el p oble-
ma del camino ec angula mínimo en e X1yX2en p esencia de dos pa alelepípedos
ba e a disjun os cuyas p oyecciones P oyˆ
j(·)in e secan pa a algún j∈ {1, ..., n}, es
la que ecoge el siguien e eo ema.
Teo ema 2.3. El P oblema 2.1 cuando B=B1∪B2, siendo B1yB2dos hipe pa-
alelepípedos de dimensión ndisjun os ales que P oyˆ
j(B1)∩P oyˆ
j(B2)6=∅con
j∈ {1, ..., n}, y e ique ados de o ma que V1< V 2siendo V1=κ1
j+hξ1
jy
V2=κ2
j+iξ2
jcon h, i ∈ {−1,1} ales que |V1−V2|es mínimo, es equi alen e
2. Camino ec angula mínimo en p esencia de pa alelepípedos ba e a 49
al p oblema de p og amación lineal y en e a mix a
m´ın d12 +d23 (2.57)
s.a: (2.34)-(2.56),(2.58)
V1≤ρj≤V2,(2.59)
ρk∈R,∀k= 1, ..., n, (2.60)
%ik ∈R,∀i= 1,2,3, k = 1, ..., n. (2.61)
Demos ación. La co ección de es a o mulación se sigue de la discusión man enida
en los pá a os p eceden es.
La cons an e Mpuede oma se nue amen e nm´axi=1,...,n{2ξ0
i}+ε, siendo ξ0
ila mi ad
de la anchu a en la coo denada OXide la en ol en e ec angula i e a i a RBde X,Y
yB=B1∪B2, y εcualquie cons an e es ic amen e posi i a. Nó ese que la sepa ación
de B1yB2 ealizada median e R(V1, V 2)puede hace se ambién en el caso en el que
P oyˆ
k(B1)∩P oyˆ
k(B2) = ∅,∀k= 1, ..., n, pa a ello omamos cualquie k∈ {1, ..., n}
pa a el que se cumpla V1=κ1
k+ξ1
k≤V2=κ2
k−ξ2
koV2=κ2
k+ξ2
k≤V1=κ1
k−ξ1
k.
Es e kexis e, de lo con a io B1yB2no se ían disjun os, y puede ob ene se en iempo
O(n). Po lo an o, la o mulación (2.57)-(2.61) es álida pa a esol e el p oblema
del camino ec angula mínimo en e dos pun os en p esencia de dos pa alelepípedos
ba e a disjun os en cualquie esi u a. El Lema 2.10 ambién puede usa se en es a
o mulación pa a dismui el núme o de a iables bina ias, pues la o mulación (2.57)-
(2.61) con iene (po duplicado) a la o mulación (2.6)-(2.30).
Como úl imo caso pa icula del P oblema 2.1 an es de abo da el mismo, nos plan-
eamos el p oblema en el que B=SN
i=1 Bisiendo los Bihipe pa alelepípedos de di-
mensión ndisjun os dos a dos, es deci , conside amos el caso pa icula del P oblema
2.1 cuando cada complejo ba e a es á o mado po un único pa alelepípedo. Como ya
hemos comen ado, si P oyˆ
k(Bi)∩P oyˆ
k(Bj) = ∅,∀k= 1, ..., n,∀i, j = 1, ..., N con
i6=j, el Lema 2.11 puede ex ende se a es e caso y la es a egia de calcula odas las
dis ancias dBi(X, Y ),i= 1, ..., N, y queda nos con la mayo , es álida ambién en
es e caso. Pues o que la comp obación de la condición P oyˆ
k(Bi)∩P oyˆ
k(Bj) = ∅,
∀k= 1, ..., n,i6=j, end ía que lle a se a cabo pa a odos los pa es posibles de pa a-
lelepípedos, dicha comp obación puede aliza se en un iempo O(N2n). No obs an e,
nues o obje i o es esol e el p oblema en cualquie ci cuns ancia, es deci , se cumpla
o no la condición an e io . Como se ha podido comp oba al abo da el p oblema pa a
el caso N= 2, la es a egia de de ec a la posición ela i a de los pun os XeYcon
espec o a los pa alelepípedos ba e a B1yB2complica conside ablemen e la o mu-
lación del p oblema de p og amación ma emá ica que se enía pa a el caso N= 1, y
hace bas an e di ícil la adap ación de dicha o mulación cuando N≥3. Es po ello que
un cambio de es a egia es necesa io. En adelan e, κi
kdeno a a la coo denada k-ésima
del cen o del pa alelepípedo Biyξi
ka la mi ad de la anchu a de ese mismo pa alele-
pípedo en la coo denada OXk,i= 1, ..., N,k= 1, ..., n.
56 2.3. Camino ec angula mínimo en p esencia de pa alelepípedos ba e a
consecuencia pues las a iables ωimk sólo apa ecen en es a es icción y en las an e io-
es ((2.81) y (2.83)). Supongamos que (ai)j< κm
j<(ai+1)jo(ai+1)j< κm
j<(ai)j
pa a algún j∈ {1, ..., n}(de hecho es o sólo puede ocu i en una coo denada pues la
es icción (2.75) ue za a que aiyai+1 se di e encian a lo sumo en una coo denada),
en cuyo caso θimj = 1, y supongamos además que θimk = 0,∀k6=j. En es e caso, de-
be asegu a se, o bien, (ai) ,(ai+1) ≤κm
−ξm
, o bien, (ai) ,(ai+1) ≥κm
+ξm
, pa a
cie o 6=j, o dicho de o a o ma, debe asegu a se que dac
im ≥ξm
pa a algún 6=j,
pues dado que aiyai+1 se di e encian a lo sumo en una coo denada, siendo es a en on-
ces necesa iamen e la j-ésima ya que (ai)j< κm
j<(ai+1)jo(ai+1)j< κm
j<(ai)j,
dac
(i+1)m ≥ξm
se end á po ene se dac
im ≥ξm
. En es a si uación dado que la es-
icción (2.81) queda ía dac
imk ≥ξm
kωimk y alguno de los ωimk oma á el alo 1po la
es icción (2.82), se end á que dac
im ≥ξm
pa a algún , al a ía comp oba que es e
es dis in o de j, pe o es o se iene po la es icción (2.83) que ue za a que ωimj = 0,
cumpliéndose así la condición 3 del Lema 2.13 pa a ga an iza que los codos a1, ..., a¯
S
o man un X1-X2camino ec angula pe mi ido. Como sabemos, las a iables θimk
oman el alo 1necesa iamen e si (ai)k< κm
k<(ai+1)ko(ai+1)k< κm
k<(ai)k,
pudiendo oma alo es en el in e alo [0,1] en caso con a io, aún así, obsé ese que
las es icciones (2.81)-(2.83) uncionan co ec amen e en el es o de casos no desa-
ollados, pues alo es de las a iables θimk que, pudiendo oma cualquie alo en
el in e alo [0,1], hagan demasiado pequeña la can idad M(1 −Pn
h=1 θimh)de la es-
icción (2.81), p oduci án un inc emen o innecesa io del alo de la unción obje i o.
Dado que en la unción obje i o (2.62) se es á minimizando la suma de las longi udes
de los segmen os que cons i uyen el camino ec angula pe mi ido que une X1yX2,
en el óp imo, el camino que de e minan los segmen os [a1, a2], ..., [a¯
S−1, a¯
S]es un X1-
X2camino ec angula mínimo pe mi ido y la unción obje i o (2.62) oma el alo
dB(X1, X2).
De nue o, Mpuede oma se nm´axi=1,...,n{2ξ0
i}+ε, siendo ξ0
ila mi ad de la anchu a en
la coo denada OXide la en ol en e ec angula i e a i a RBde X,YyB=SN
i=1 Bi,
yεcualquie cons an e es ic amen e posi i a, siemp e y cuando en (2.62)-(2.88) no
se conside en los pa alelepípedos ba e a que no es én con enidos en RB. Es o úl imo
lo podemos hace po el Lema 2.7, y además supone una disminución del núme o de
a iables bina ias que emplea (2.62)-(2.88). Pues o que el núme o de a iables bina ias
usadas en la o mulación (2.62)-(2.88) depende di ec amen e de la co a supe io pa a
el núme o de codos ¯
S, es inmedia o e que cuan o más ajus ada sea es a co a, meno
se á en gene al el iempo que necesi e el sol e que es emos u ilizando pa a encon a
la solución óp ima del p oblema. Si en (2.62)-(2.88) omamos ¯
Smeno que el núme o
mínimo de codos necesa io pa a o ma un X1-X2camino ec angula mínimo pe -
mi ido, en onces (2.62)-(2.88) de uel e como solución el X1-X2camino ec angula
pe mi ido de meno longi ud que puede o ma se con ese núme o de codos. Si consi-
de amos el P oblema 2.1 gene al, no el caso pa icula del Teo ema 2.4, y o mulamos
(2.62)-(2.88) con las pa alelepípedos que con i uyen los di e en es complejos ba e a,

2. Camino ec angula mínimo en p esencia de pa alelepípedos ba e a 57
las condiciones del Lema 2.13 que cumple (2.62)-(2.88), son su icien es pa a ga an i-
za que la o mulación (2.62)-(2.88) esuel e el P oblema 2.1.
Co ola io 2.2. El P oblema 2.1 es equi alen e al p oblema de p og amación ma e-
má ica (2.62)-(2.88) omando como pa alelepípedos en la o mulación los que o man
los complejos ba e as.
Demos ación. Bas a obse a que, pues o que enimos suponiendo que los pa ale-
lepípedos {B1
i, ..., Bmi
i}que componen un complejo Bi, lo desc iben co ec amen e
si, pa a cualquie pun o de un pa alelepípedo Bj
i,j= 1, ..., mi, que pe enezca a la
on e a de Bj
iy, al mismo iempo, al in e io del complejo Bi, en onces, exis e o o
pa alelepípedo dis in o Bh
idel mismo complejo al que dicho pun o pe enece a su in e-
io , o lo que es lo mismo, que Smi
k=1 in (Bk
i) = in (Bi), las condiciones del Lema 2.13
que cumple (2.62)-(2.88) son equi alen es a deci que el X1-X2camino ec angula
o mado sea un camino ec angula pe mi ido.
La o mulación (2.62)-(2.88) como mé odo pa a esol e el P oblema 2.1 p esen a un
incon enien e: la ob ención de una co a supe io ¯
Spa a el núme o de codos de un
X1-X2camino ec angula mínimo pe mi ido no es inmedia a. La asunción hecha en
el Lema 2.12 de que siemp e puede encon ase un X1-X2camino ec angula mínimo
pe mi ido al que una ez que pasa po la on e a de un pa alelepípedo ba e a, no
uel e a pasa po ella, no es cie a en el caso de los complejos de pa alelepípedos.
En la Figu a 2.16 se mues a un ejemplo en el caso plano dónde odo X1-X2camino
ec angula mínimo pe mi ido pasa necesa iamen e dos eces po la on e a de un
complejo ba e a y dos eces po la on e a de un mismo pa alelepípedo cons i uyen e
de dicho complejo. Del Teo ema 2.1 se desp ende que una co a supe io ¯
Spa a el
núme o de codos de un X1-X2camino ec angula mínimo pe mi ido necesa ia en la
o mulación (2.62)-(2.88) cuando és a se u iliza pa a esol e el P oblema 2.1, es el
núme o de nodos del g a o co espondien e a N`1. Sin emba go, la ob ención de ese
núme o equie e la cons ucción de N`1, cuya complejidad sólo hemos podido aco a
po O(W6n1122n−6). Es necesa io pues explo a una nue a es a egia pa a esol e el
P oblema 2.1 en su e sión gene al.
58 2.3. Camino ec angula mínimo en p esencia de pa alelepípedos ba e a
Figu a 2.16: Todo X1-X2camino ec angula mínimo pe mi ido pasa necesa iamen e
dos eces po la on e a de B1y dos eces po la on e a de B1
1.
El mé odo pa a esol e el P oblema 2.1 que se a a desa olla a con inuación se
basa undamen ealmen e en el siguien e esul ado.
Lema 2.14. Sean C1yC2dos hipe pa alelepípedos iso é icos de dimensiones n1, n2∈
{n−1, n}, espec i amen e, que in e secan en sus on e as pe o no en sus in e io es.
En onces, pa a odo X∈C1y pa a odo Y∈C2, exis e un X-Ycamino ec angula
de longi ud `1(X, Y )comple amen e con enido en C1∪C2.
Demos ación. Du an e oda la p ueba supond emos sin pé dida de gene alidad n1≥
n2. Deno emos po ˆ
ξ1
jyˆ
ξ2
j,j= 1, ..., n, a la mi ad de la anchu a en cada coo de-
nada de C1yC2, y po (ˆκ1
1, ..., ˆκ1
n) y(ˆκ2
1, ..., ˆκ2
n) a sus cen os, espec i amen e.
La in e sección de C1yC2,C1∩C2, se encuen a necesa iamen e en una ca a ζ1
de C1de dimensión n1−1en la que es cons an e la coo denada, digamos, OXj,
j∈ {1, ..., n}, y en una ca a ζ2de C2de dimensión n2−1en la que es cons an-
e esa misma coo denada OXj. Es o se iene po que los pa alelepípedos son iso é i-
cos e in e secan en su on e a pe o no en su in e io . Más aún, C1∩C2es un hi-
pe pa alelepípedo de dimensión n2−1, el cual se ex iende en OXken el in e alo
[ k, gk] = [ˆκ1
k−ˆ
ξ1
k,ˆκ1
k+ˆ
ξ1
k]∩[ˆκ2
k−ˆ
ξ2
k,ˆκ2
k+ˆ
ξ2
k},k= 1, ..., n. Es deci , [ k, gk]pue-
de se [ˆκ1
k−ˆ
ξ1
k,ˆκ2
k+ˆ
ξ2
k],[ˆκ2
k−ˆ
ξ2
k,ˆκ1
k+ˆ
ξ1
k],[ˆκ1
k−ˆ
ξ1
k,ˆκ1
k+ˆ
ξ1
k]o[ˆκ2
k−ˆ
ξ2
k,ˆκ2
k+ˆ
ξ2
k],
k= 1, ..., n. En adelan e supond emos ˆκ1
j<ˆκ2
j, po an o, odos los pun os de C1∩C2
ienen la j-ésima coo denada igual a j= ˆκ1
j+ˆ
ξ1
j= ˆκ2
j−ˆ
ξ2
j=gj.
Sean X∈C1eY∈C2. Es e iden e que pa a odo pun o Z1de C1siem-
p e exis e un X-Z1camino ec angula de longi ud `1(X, Z1)con enido comple a-
men e en C1(el camino ec angula en el que en cada codo no i ial se iguala una
de las coo denadas de Xa la de Z1co espondien e). Lo mismo ocu e con C2e
Y. Supongamos en p ime luga que ζ2⊆ζ1. En onces conside amos el segmen o
s= [(y1, ..., yj, ..., yn) ,(y1, ..., j, ..., yn) ], el cual es á con enido en C2, y deno amos
Z2= (y1, ..., j, ..., yn) . El pun o Z2pe enece a C1∩C2, en pa icula a C1, luego
exis e un X-Z2camino ec angula QX,Z2de longi ud `1(X, Z2)con enido en C1. El
2. Camino ec angula mínimo en p esencia de pa alelepípedos ba e a 59
X-Ycamino ec angula QX,Z2∪ses un X-Ycamino ec angula con enido en C1∪C2
de longi ud
l(QX,Z3∪s) = l(QX,Z3) + l(s) =
n
X
i=1,i6=j
|xi−yi|+|xj− j|+| j−yj|,
pe o xj≤ j≤yj, luego |xj− j|+| j−yj|=|xj−yj|, po lo que QX,Z2∪s iene
longi ud `1(X, Y ). Si ζ1⊆ζ2se azona de la misma o ma.
Conside emos aho a el caso gene al en el que no necesa iamen e ζ2⊆ζ1ni
ζ1⊆ζ2. Tomemos C1∩C2y conside emos el pa alelepípedo iso é ico C3dado po
el conjun o de pun os {Z2+τej:Z2∈C1∩C2,0≤τ≤2ξ2
j}, siendo ej∈Rn
el ec o cuya única componen e no nula es la j-ésima, siendo és a igual a 1, es deci ,
C3es la egión ba ida cuando se desplaza C1∩C2desde jhas a ˆκ2
j+ˆ
ξ2
j( e Figu a
2.17).
Figu a 2.17: Pa alelepípedos C1,C2yC3en R2.
Cla amen e C3⊆C2. Conside emos que Y /∈C3, pues si Y∈C3el esul ado se iene
cons uyendo el mismo X-Ycamino ec angula que el cons uido en el caso en el que
ζ2⊆ζ1. El pun o Ype enece a C3si y sólo si i≤yi≤gipa a odo i= 1, ..., n
con i6=j. Como Y /∈C3, sean i1, ..., imlos índices pa a los que, o bien, yik< ik, o
bien, yik> gik. Sea Qel camino ec angula compues o po msegmen os que pa e de
Yy al que en cada codo se iguala la coo denada yikde ya iksi yik< iko a giksi
yik> gik. Sea Zel pun o al que llega es e camino. El pun o Zpe enece a C3yQes un
Y-Zcamino ec angula con enido en C2(y po an o en C1∪C2) de longi ud `1(Y, Z).
Como Z∈C3, po el pá a o an e io sabemos que exis e un Z-Xcamino ec angula
Q0con enido en C1∪C3(y po an o en C1∪C2) de longi ud `1(Z, X), pues C1y
C3son dos pa alelepípedos iso é icos que in e secan en sus on e as pe o no en sus
in e io es, y si ζ3es la ca a de C3en la que es á con enido C1∩C3=C1∩C2, en onces
ζ3⊆ζ1. El camino ec angula Q∪Q0es así un Y-Xcamino ec angula con enido
comple amen e en C1∪C2. Veamos que su longi ud es `1(Y, X). Si i /∈ {i1, ..., im},
60 2.3. Camino ec angula mínimo en p esencia de pa alelepípedos ba e a
en onces el apo e a la longi ud de Q∪Q0del desplazamien o en la i-ésima coo denada
es |yi−zi|+|zi−xi|, pe o en es e caso yi=zi, luego es |yi−xi|. Po o o lado, si
i∈ {i1, ..., im}, en onces el apo e a la longi ud de Q∪Q0del desplazamien o en la
i-ésima coo denada es |yi−zi|+|zi−xi|, donde zies isi yi< iogisi yi> gi. Si
zi= i, en onces yi< ziyzi≤xi, pues como yi< zinecesa iamen e i= ˆκ1
i−ˆ
ξ1
i,
ya que si i= ˆκ2
i−ˆ
ξ2
ino se pod ía ene yi< zi, luego |yi−zi|+|zi−xi|=|yi−xi|.
Si zi=gi, en onces yi> ziyzi≥xi, pues como yi> zinecesa iamen e gi= ˆκ1
i+ˆ
ξ1
i,
ya que si gi= ˆκ2
i+ˆ
ξ2
ino se pod ía ene yi> zi, luego |yi−zi|+|zi−xi|=|yi−xi|.
Concluimos así que la longi ud de Q∪Q0es `1(X, Y )quedando p obado el lema.
Vol amos a pensa en la ed de cons ucción ec angula N`1de X,YyB. Es a ed nos
pe mi ía da un mé odo de cálculo de un X-Ycamino ec angula mínimo pe mi ido
basado en el Teo ema 2.1, el cual consis ía básicamen e en aplica cualquie algo i mo
de cálculo de camino mínimo en el g a o que cons i uye N`1. Hablamos en onces de
la complejidad asín o ica de u iliza el algo i mo de Dijks a pa a halla dicho camino.
No se comen ó en ese momen o, pe o e iden emen e, una ez cons uido el g a o que
desc ibe N`1, puede u iliza se ambién pa a esol e el P oblema 2.1, la o mulación
lineal clásica de p og amación ma emá ica pa a esol e el p oblema del camino mí-
nimo en g a os como un p oblema de lujo. El Lema 2.14 nos a a pe mi i además
esol e el P oblema 2.1 como un p oblema de camino mínimo en g a os de nodos
no ijos. La idea es descompone RB in (B)en egiones en e las cuales los cami-
nos ec angula es se compo an de una o ma deseable que los hace, en algún sen ido,
manejables. Es as egiones, como se puede in ui y deduci del Lema 2.14, son los hi-
pe pa alelepípedos iso é icos. Es e es el caso de la descomposición en pa alelepípedos
C(N`1)de RB in (B)que da la ed de cons ucción ec angula . Los pa alelepípedos
de C(N`1)sólo in e secan con o os en su on e a, más aún, po la cons ucción hecha
de N`1, es as in e secciones son ca as comunes de los pa alelepípedos que in e secan.
El Lema 2.14 puede aplica se en onces en cualquie pa de pun os de sendos pa alele-
pípedos adyacen es (es deci , que in e secan en sus on e as) de C(N`1). El siguien e
lema p opo ciona un mé odo pa a esol e el P oblema 2.1 basado en el Lema 2.14, el
obje o del lema es simplemen e mos a como puede se u ilizado el Lema 2.14 pa a
da solución al P oblema 2.1, si bien es e mé odo se segui á e inando en lo que es a
de capí ulo.
Lema 2.15. Sean X1, X2∈ F y sea N`1la ed de cons ucción ec angula de X1,
X2yB. Sea G= (V, E)el g a o di igido que posee un nodo νi∈Vpo cada pa a-
lelepípedo Cide C(N`1), y al que el a co (i, j)∈E(y, po an o, el a co (j, i)∈E)
si y sólo si los pa alelepípedos CiyCjde C(N`1)son adyacen es, es o es, in e secan.
Deno emos po i0al índice al que X1∈Ci0∈ C(N`1)(si hay más de uno i0se á
cualquie a de ellos), po i al índice al que X2∈Ci ∈ C(N`1)(si hay más de uno i
se á cualquie a de ellos), i06=i , y no emos ˜
N=|C(N`1)|. Sea ˜κi
kla coo denada k-
ésima del cen o de Ciy˜
ξi
kla mi ad de su anchu a en la coo denada OXk,i= 1, ..., ˜
N,
k= 1, ..., n. En onces, el P oblema 2.1 es equi alen e al p oblema de p og amación
2. Camino ec angula mínimo en p esencia de pa alelepípedos ba e a 61
lineal y en e a mix a
m´ın X
(i,j)∈E
Dij (2.89)
s.a: X
(i0,j)∈E
ηi0j= 1,(2.90)
X
(h,i )∈E
ηhi = 1,(2.91)
X
(i,j)∈E
ηij −X
(h,i)∈E
ηhi = 0,∀j= 1, ..., ˜
N, i 6=i0, i ,(2.92)
dijk ≥ci
k−cj
k,∀(i, j)∈E, k = 1, ..., n, (2.93)
dijk ≥ −ci
k+cj
k,∀(i, j)∈E, k = 1, ..., n, (2.94)
Dij ≥
n
X
k=1
dijk −M(1 −ηij),∀(i, j)∈E, (2.95)
˜κi
k−˜
ξi
k≤ci
k≤˜κi
k+˜
ξi
k,∀i= 1, ..., ˜
N, k = 1, ..., n, (2.96)
ci0
k=x1
k,∀k= 1, ..., n, (2.97)
ci
k=x2
k,∀k= 1, ..., n, (2.98)
Dij ≥0, ηij ∈ {0,1},∀(i, j)∈E, (2.99)
dijk ≥0,∀(i, j)∈E, k = 1, ..., n, (2.100)
ci
k∈R,∀i= 1, ..., ˜
N, k = 1, ..., n, (2.101)
siendo M > 0una cons an e lo su icien emen e g ande.
Demos ación. En (2.99)-(2.101) se de ine la na u aleza de las a iables de decisión:
ci
k ep esen a la k-ésima coo denada de un pun o en el i-ésimo pa alelepípedo Ci∈
C(N`1);dijk es una a iable posi i a que en el óp imo oma á, al menos, el alo abso-
lu o de la di e encia en la k-ésima coo denada |ci
k−cj
k|de los pun os (ci
1, ..., ci
n) ∈Ci
y(cj
1, ..., cj
n) ∈Cj;Dij es una a iable posi i a que en el óp imo oma á el alo
`1((ci
1, ..., ci
n) ,(cj
1, ..., cj
n) )si los pun os (ci
1, ..., ci
n) y(cj
1, ..., cj
n) pe enecen al X1-
X2camino ec angula mínimo pe mi ido que se encuen a en el óp imo y el pun o
(ci
1, ..., ci
n) se isi a an es que el pun o (cj
1, ..., cj
n) cuando el X1-X2camino óp imo
se eco e desde X1has a X2, en cuyo caso la a iable bina ia ηij oma á el alo 1, en
caso con a io Dij = 0 yηij oma á ambién el alo 0.
Las es icciones (2.90)-(2.92) son las es icciones clásicas de conse ación de
lujo u ilizadas en los p oblemas de p og amación ma emá ica pa a halla caminos mí-
nimos en g a os. Es as es icciones imponen que del nodo inicial νi0debe de sali un
a co ( es icción (2.90)), que al nodo inal νi debe de llega o o ( es icción (2.91)), y
que en cualquie o o nodo debe conse a se el lujo ( es icción (2.92)), es o es, que al
nodo llegue un a co y de él salga o o, o que al nodo no llegue ni de él salga ningún a co.

62 2.3. Camino ec angula mínimo en p esencia de pa alelepípedos ba e a
De es a o ma, se cons uye un camino de νi0aνi en G. Cada nodo νies á ep esen-
ando a un pun o en el pa alelepípedo Ci∈ C(N`1)( es icción 2.96), la longi ud Dij
del a co (i, j) iene dada po , al menos, la dis ancia `1((ci
1, ..., ci
n) ,(cj
1, ..., cj
n) )en e
los pun os de CiyCjque se seleccionen en el óp imo ( es icciones (2.93) y (2.94)).
Como en (2.89) se es á minimizando P(i,j)∈EDij, en el óp imo el camino encon ado
se á de longi ud mínima siemp e y cuando Dij = 0 si el a co (i, j)no se selecciona
en el camino, es deci , si ηij = 0, pe o es o se consigue con (2.95), pues si es o ocu e
en onces (2.95) impone Dij ≥Pn
k=1 dijk −M < 0, desigualdad que no es á exigiendo
nada pues Dij ≥0po de inición en (2.99), haciéndose Dij = 0 po la minimización
que se es á haciendo en (2.89), si po el con a io el a co (i, j)se selecciona en el ca-
mino, es o es, si ηij = 1, (2.95) impone Dij ≥Pn
k=1 dijk, así po la minimización
que se es á haciendo en (2.89),Dij =Pn
k=1 dijk =`1((ci
1, ..., ci
n) ,(cj
1, ..., cj
n) )en el
óp imo. En esumen, dado que (2.97) y (2.98) imponen que el pun o de pa ida sea
X1y el de llegada X2, el p oblema (2.89)-(2.101) halla en el óp imo una secuencia
de pun os X1, ..., (ci
1, ..., ci
n) , ..., X2en SCi∈C(N`1)Cicumpliendo: que un pun o y su
suceso pe enecen a pa alelepípedos adyacen es de C(N`1); y que la suma de dis an-
cias en mé ica `1en e pun os consecu i os de la secuencia es mínima. Vamos a e
que esa suma de dis ancias que se ob iene en el alo óp imo de (2.89)-(2.101) es la
longi ud de un X1-X2camino ec angula mínimo pe mi ido y cómo se ob iene es e
camino a pa i de la solución óp ima del p oblema.
Como SCi∈C(N`1)Ci=RB in (B), los pun os (ci
1, ..., ci
n) seleccionados en el óp-
imo pe enecen a la egión ac ible F. Po el Lema 2.14, exis e un camino ec angula
Qij comple amen e con enido en Ci∪Cj⊆ RB in (B)de longi ud la dis ancia en
mé ica `1uniendo al pun o (ci
1, ..., ci
n) y su suceso (cj
1, ..., cj
n) en la secuencia óp i-
ma, pues es os pun os pe enecen a sendos pa alelepípedos CiyCjque in e secan en
su on e a. De es o se deduce que e ec i amen e el alo óp imo de (2.89)-(2.101) es
la longi ud de un X1-X2camino ec angula mínimo pe mi ido, pues la unión de los
caminos ec angula es Qij es un X1-X2camino ec angula pe mi ido (es á con enido
en SCi∈C(N`1)Ci=RB in (B)) y mínimo, ya que se es á minimizando su longi ud
en (2.89) y la egión ac ible de (2.89)-(2.101) es SCi∈C(N`1)Ci=RB in (B), donde
es su icien e busca un camino ec angula mínimo pe mi ido po el Lema (2.7). Di-
cho camino ec angula puede cons ui se uniendo los pun os (ci
1, ..., ci
n) consecu i os
seleccionados en la secuencia óp ima median e el camino desc i o en la demos ación
cons uc i a del Lema 2.14.
El mé odo que da el Lema 2.15 pa a esol e el P oblema 2.1 equie e la ob ención del
conjun o de celdas (pa alelepípedos) C(N`1)(si X1yX2es án en la misma celda de
C(N`1), en onces X1yX2son `1- isibles y dB(X1, X2) = `1(X1, X2) i ialmen e, es
po ello que en el lema se supone i06=i ). Es o puede hace se a pa i de N`1, aunque
como azonamos en su momen o, sólo habíamos podido aco a el cos e de cons ucción
de N`1po O(W6n1122n−6)(exponencial) cuando n≥3, con W=PN
i=1 miy siendo
miel núme o de pa alelepípedos que desc iben al complejo ba e a Bi,i= 1, ..., N.
2. Camino ec angula mínimo en p esencia de pa alelepípedos ba e a 63
Además, el núme o de a iables bina ias de (2.89)-(2.101) depende di ec amen e del
núme o de pa alelepípedos de C(N`1), el cual, cabe espe a que sea ele ado dado el nú-
me o de segmen os (O(W3n32n−3)) y nodos (O(W6n622n−6)) de N`1cuando n≥3.
Más aún, los pa alelepípedos CiyCjde C(N`1)que in e secan lo hacen en una ca a
común, lo cual con i uye un caso pa icula de las condiciones de aplicación del Lema
2.14, es deci , el Lema 2.14 no se es á explo ando odo lo que se pod ía explo a con
la descomposición de RB in (B)en los pa alelepípedos C(N`1). El mé odo que da el
Lema 2.15 puede puli se a ando de co egi es a se ie de incon enien es. Es e e ina-
mien o pasa necesa iamen e po una descomposición en pa alelepípedos de RB in (B)
que, en algún sen ido, ap o eche mejo que C(N`1)el Lema 2.14.
El núme o de a iables bina ias empleadas po el modelo de p og amación ma-
emá ica lineal y en e a mix a inal basado en el Lema 2.14 que se p esen a á en el
é mino de la sección, es igual al núme o de pa alelepípedos en las condiciones del
Lema 2.14 en el que se descomponga RB in (B), po ello, a a emos de ealiza
una descomposición C0de RB in (B)en un núme o educido de pa alelepípedos.
Es impo an e ambién que podamos asegu a una buena co a supe io asín o ica pa-
a la complejidad de ealiza dicha descomposición, pues si la complejidad de lle a
a cabo la descomposición en pa alelepípedos C0de RB in (B)es muy ele ada, de
nada nos se i ía el aho o compu acional conseguido al disminui el núme o de a-
iables bina ias del modelo de p og amación ma emá ica. Comenza emos dando una
descomposición de RB in (B)de es as ca ac e ís icas en el plano y la ex ende emos
a dimensiones supe io es de o ma ecu si a.
Algo i mo 2.2. (Cos ucción de C0en R2)
Inpu : Los pun os X= (x1, x2) eY= (y1, y2) en Fy el conjun o {B1, ..., BN}
de complejos de pa alelepípedos ba e a en R2, cada uno de ellos desc i o po el
conjun o de pa alelpípedos {B1
i, ..., Bmi
i}que lo o man, i= 1, ..., N, y es os a su ez
desc i os po su cen o (κi,j
1, κi,j
2) y la mi ad de su anchu a ξi,j
ken cada coo denada
OXk,i= 1, ..., N,j= 1, ..., mi,k= 1,2.
Paso 1: Ob ene RBmedian e el Algo i mo 2.1. Desca a odos los complejos ba e-
a que no es én con enidos en RB. Si ninguno de los complejos ba e a es á
con enido en RB, hace L3:= RBe i a Ou pu .
Paso 2: O dena de meno a mayo , los alo es (se en iende, de los pa alelepípedos
no desca ados en el paso an e io ) κi,j
1+sξi,j
1,i= 1, ..., N,j= 1, ..., mi,s∈
{−1,1}, así como el alo máximo y mínimo en la coo denada OX1de RB, en
una lis a L1, y los alo es κi,j
2+sξi,j
2,i= 1, ..., N,j= 1, ..., mi,s∈ {−1,1},
así como el alo máximo y mínimo en la coo denada OX2de RB, en una
lis a L2, no incluyendo las posibles epe iciones de elemen os en ninguna de
las lis as. Selecciona la coo denada OX1o la coo denda OX2. En adelan e
suponemos seleccionada la coo denada OX1, el algo i mo seleccionada la
coo denada OX2es análogo.
64 2.3. Camino ec angula mínimo en p esencia de pa alelepípedos ba e a
Paso 3: C ea una lis a acía L3. Añadi a L3las ca as de dimenisón 1 (hipe pa a-
lelepípedos de dimensión 1, segmen os pa alelos a los ejes coo denados) de
los pa alelepípedos Bj
icon enidas en la on e a de RB,k= 1,2. Pa a cada
i= 1, ..., |L1| − 1hace lo siguien e: si zies el i-ésimo elemen o de L1,zi+1
el (i+ 1)-ésimo, z−
2yz+
2los alo es ex emos de RBen OX2, y Ri,i+1 el pa-
alelepípedo de é ices (zi, z−
2) ,(zi+1, z−
2) ,(zi, z+
2) y(zi+1, z+
2) , en onces
añadi a L3las componen es conexas (hipe pa alelepípedos de dimensión 2)
de la clausu a de Ri,i+1 B.
Paso 4: Encon a los segmen os maximales que pueden o ma se median e la unión
de los segmen os de L3ob enidos en la p ime a pa e del paso an e io , añadi
es os segmen os maximales a L3y elimina los segmen os que los cons i uyen.
Pa a cada i= 1, ..., |L1|−2hace los siguien e: pa a cada pa alelepípedo C0
ob enido de Ri,i+1 (es deci , pa a cada componen e conexa de la clausu a de
Ri,i+1 B) y pa a cada pa alelepípedo C00 ob enido de Ri+1,i+2, comp oba
si C0∪C00 es ambién un pa alelepípedo, en cuyo caso elimina C0yC00 de
L3y añadi C0∪C00 aL3(en la i e ación i+ 1,C0∪C00 se conside a un
pa alelepípedo ob enido de Ri+1,i+2).
Ou pu : C0:= L3.
Lema 2.16. En R2, el Algo i mo 2.2 descompone RB in (B)en un núme o O(W)de
pa alelepípedos iso é icos, siendo W=PN
i=1 miel núme o de pa alelepípedos que
desc iben los complejos ba e a B1, ..., BN.
Demos ación. Los segmen os añadidos a L3en el Paso 3 del Algo i mo 2.2 son hipe -
pa alelepípedos iso é icos de dimensión 1, y sus posibles uniones en el Paso 4 ambién
lo son. Veamos que e ec i amen e las componen es conexas de la clausu a de Ri,i+1 B
son hipe pa alelepípedos iso é icos de dimensión 2. Pa a i= 1, ..., |L1|−1, pues o que
en Ri,i+1 no puede es a con enida ninguna ca a de ningún pa alelepípedo Bj
hde la
o ma [(κh,j
1+sξh,j
1, κh,j
2−ξh,j
2) ,(κh,j
1+sξh,j
1, κh,j
2+ξh,j
2) ]con s∈ {−1,1}a menos
que κh,j
1+sξh,j
1sea el i-ésimo o el (i+ 1)-ésimo elemen o de L3,Ri,i+1 B consis e
en a ios hipe pa alelepípedos iso é icos de dimensión 2 disjun os unos con o os en
los que al an algunas de sus ca as, en onces, la clausu a de Ri,i+1 B añade a es-
os pa alepípedos iso é icos las ca as al an es. Las posibles uniones en el Paso 4 de
los hipe pa alelepípedos iso é icos de dimensión 2 ob enidos en el Paso 3 del Algo i -
mo 2.2, son cla amen e hipe pa alelepípedos iso é icos de dimensión 2 ambién. Sea
Z∈ RB in (B). No es di ícil e , que si Zpe enece a la on e a de RBy al mismo
iempo a la on e a de uno de los complejos ba e a, en onces Zes á con enido en
alguno de los hipe pa alelepípedos de dimensión 1 de C0, en cualquie o o caso, Z
pe enece a alguno de los hipe pa alelepípedos de dimensión 2 de C0. Luego C0es una
descomposición en pa alelepípedos de RB in (B), es deci , SC0∈C0C0=RB in (B).
P obemos aho a que el núme o de pa alelepípedos de C0es O(W). E iden emen e,
2. Camino ec angula mínimo en p esencia de pa alelepípedos ba e a 65
el núme o de hipe pa alelepípedos de dimensión 1 de C0es a lo sumo O(W). En cuan-
o al núme o de hipe pa alelepípedos de dimensión 2 de C0, amos a p oba que es a
lo sumo 3Σ, siendo Σel núme o de pun os ex emos P(B)de los complejos ba e a
B1, ..., BN. Pa a ello bas a p oba que odo hipe pa alelepípedo de dimensión 2 de C0
con iene un pun o de P(B)en su on e a, como cada pun o Zde P(B)puede pe ene-
ce a lo sumo a es hipe pa alelepípedos iso é icos de dimensión 2 de C0(cuando Zes
un é ice común de los es pa alelepípedos de C0), el núme o de hipe pa alelepípedos
de dimensión 2 de C0se á a lo sumo 3Σ.
Supongamos que el pa alelepípedo C0ob enido en el Paso 3 o en el Paso 4 del
Algo i mo 2.2 no posee ningún pun o de P(B)en sus ca as de dimensión 1 dónde la
coo denada OX1es cons an e. Como C0no posee ningún pun o de P(B)en sus ca as
de dimensión 1 en las que la coo denada OX1es cons an e, necesa iamen e al menos
una de sus ca as de dimensión 1 en las que la coo denada OX2es cons an e es á con-
enida en una de las ca as de dimensión 1 en la que la coo denada OX2es cons an e de
un pa alelepípedo Bj
i, de lo con a io, C0se ex ende ía en OX2desde el mínimo alo
en OX2de RB(deno ado z−
2en el Paso 3) has a el máximo alo en OX2de RB(deno-
ado z+
2en el Paso 3), y como no hab ía pun os zi, zi+1 ∈ L1, con 1< i, i + 1 <|L1|,
ales que zisea el mínimo alo que alcanza en OX1el pa alelepípedo C0yzi+1 el má-
ximo alo que alcanza C0en esa misma coo denada, pues en es e caso C0con end ía
al menos un pun o de P(B)en sus ca as de dimensión 1 en las que la coo denada OX1
es cons an e, necesa iamen e C0=RB. Pe o C0=RBsigni ica que ninguno de los
complejos ba e a es á con enido en RB, lo cual es una con adicción pues en el Paso
1 del algo i mo se hubiese sal ado di ec amen e a Ou pu sin pasa po el Paso 3 ni el
Paso 4.
Po lo an o, si C0no posee ningún pun o de P(B)en sus ca as de dimensión 1
en las que la coo denada OX1es cons an e, necesa iamen e al menos una de sus ca-
as de dimensión 1 en las que la coo denada OX2es cons an e es á con enida en una
de las ca as de dimensión 1 en la que la coo denada OX2es cons an e de un pa a-
lelepípedo Bj
i. La o a ca a de C0en la que la coo denada OX2es cons an e es a á
con enida en una de las ca as de dimensión 1 en la que la coo denada OX2es cons an-
e de o o pa alelepípedo Bl
ho en la on e a de RB. Supongamos que nos encon amos
en el úl imo caso ( e Figu a 2.18 (a)), pa a el o o caso se azona de o ma análoga.
Veamos que en el Paso 4 del algo i mo se desca a C0en L3pa a sus i ui lo po un
pa alelepípedo que lo con iene. Sea gkel máximo alo que alcanza en OX1el pa a-
lelepípedo C0. En onces exis e en L3un pa alelepípedo C00 de la misma al u a que C0,
compa iendo una ca a de dimensión 1 con él, que en OX1se ex iende desde gkhas a
z0= m´ın{zq∈ L1:zq> gk}( e Figu a 2.18 (b)). Además, z0≤κi,j
1+ξi,j
1, κh,l
1+ξh,l
1.
En el Paso 4 del algo i mo se ealiza en onces la unión C0∪C00, que se añade a L3, y se
eliminan C0yC00 de L3, o dicho de o o modo, se ex iende C0po la de echa has a z0.
Más aún, C0se ex ende á po la de echa en el Paso 4 has a m´ın{κi,j
1+ξi,j
1, κh,l
1+ξh,l
1}.
El pa alelepípedo C000 esul an e, compa e é ice con Bj
ioBl
h( e Figu a 2.18 (c)).
Si dicho é ice no es un pun o ex emo del complejo co espondien e es po que las
72 2.3. Camino ec angula mínimo en p esencia de pa alelepípedos ba e a
no emos ¯
N=|C0|. Sea ¯κi
kla coo denada k-ésima del cen o de C0
iy¯
ξi
kla mi ad de su
anchu a en la coo denada OXk,i= 1, ..., ¯
N,k= 1, ..., n. En onces, el P oblema 2.1
es equi alen e al p oblema de p og amación lineal y en e a mix a
m´ın X
(i,j)∈E0
Dij (2.102)
s.a: µi0= 1,(2.103)
µi = 1,(2.104)
X
(h,i0)∈E0
ηhi0+X
(i0,j)∈E0
ηi0j= 1,(2.105)
X
(h,i )∈E0
ηhi +X
(i ,j)∈E0
ηi j= 1,(2.106)
X
(h,i)∈E0
ηhi +X
(i,j)∈E0
ηij = 2µi,∀i= 1, ..., ¯
N, i 6=i0, i ,(2.107)
ηij ≤1,∀(i, j)∈E0,(2.108)
µi+µj≤1 + ηij,∀(i, j)∈E0,(2.109)
ηij ≤µi,∀(i, j)∈E0,(2.110)
ηij ≤µj,∀(i, j)∈E0,(2.111)
dijk ≥ci
k−cj
k,∀(i, j)∈E0, k = 1, ..., n, (2.112)
dijk ≥ −ci
k+cj
k,∀(i, j)∈E0, k = 1, ..., n, (2.113)
Dij ≥
n
X
k=1
dijk −M(1 −ηij),∀(i, j)∈E0,(2.114)
¯κi
k−¯
ξi
k≤ci
k≤¯κi
k+¯
ξi
k,∀i= 1, ..., ¯
N, k = 1, ..., n, (2.115)
ci0
k=x1
k,∀k= 1, ..., n, (2.116)
ci
k=x2
k,∀k= 1, ..., n, (2.117)
Dij, ηij ≥0,∀(i, j)∈E0,(2.118)
µi∈ {0,1},∀i= 1, ..., ¯
N, (2.119)
dijk ≥0,∀(i, j)∈E0, k = 1, ..., n, (2.120)
ci
k∈R,∀i= 1, ..., ¯
N, k = 1, ..., n, (2.121)
siendo M > 0una cons an e lo su icien emen e g ande.
Demos ación. La o mulación (2.102)-(2.121) es igual a la o mulación (2.89)-(2.101)
sal o po las es icciones (2.103)-(2.111) que sus i uyen a (2.90)-(2.92), las a iables
ηij que aho a son a iables posi i as y no bina ias, y las nue as a iables µide inidas
en (2.119). Los pa alelepípedos de C0es án en las condiciones del Lema 2.14 al igual
que lo es aban los de C(N`1). Obsé ese, que po las es icciones (2.108)-(2.111), a
pesa de que ηij es é de inida como a iable posi i a en (2.118), en la p ác ica se a

2. Camino ec angula mínimo en p esencia de pa alelepípedos ba e a 73
a compo a como una a iable bina ia pues sólo se le a a pe mi i oma el alo 0
o el alo 1. Po an o, si demos amos que las es icciones (2.103)-(2.111) ealizan
la misma a ea que (2.90)-(2.92), es os es, encon a un camino en G0desde ν0
i0has a
ν0
i , los p oblemas de p og amación ma emá ica (2.102)-(2.121) y (2.89)-(2.101) se án
equi alen es, y po consiguien e, (2.102)-(2.121) se á equi alen e al P oblema 2.1. La
a iable bina ia µi oma á el alo 1 si el nodo ν0
ies seleccionado en el camino en
G0de ν0
i0aν0
i óp imo. Con es a in e p e ación de las a iables µi, las es icciones
(2.108)-(2.111) indican que una a is a ηij es seleccionada si y sólo si se han seleccio-
nado los pun os ela i os a los pa alelepípedos adyacen es C0
iyC0
j(es deci , si se han
seleccionado los nodos ν0
iyν0
j). Las es icciones (2.103) y (2.104) imponen que los
nodos que ep esen an los pa alelepípedos en los que se encuen an X1yX2sean se-
leccionados. Las es icciones (2.105) y (2.106) ue zan a que sólo se seleccione una
a is a iniciden e en ν0
i0yν0
i espec i amen e. Y la es icción (2.107) impone, sal o
pa a ν0
i0yν0
i , que si ν0
ies seleccionado, en onces en él inciden dos a is as, en caso
con a io, ninguna. Pues o que en (2.102) se es á minimizandpo P(i,j)∈E0Dij, las es-
icciones (2.103)-(2.111) ienen el mismo e ec o que (2.90)-(2.92), y (2.102)-(2.121)
es equi alen e al P oblema 2.1.
El núme o de a iables bina ias de la o mulación (2.102)-(2.121) es igual al núme o
de pa alelepípedos de C0(O(Wn−1)). En luga de conside a las a iables ηij como
bina ias, la o mulación (2.102)-(2.121) las conside a como a iables posi i as, e i-
ando así un núme o de a iables bina ias O(W2n−2), con lo que se espe a un mejo
endimien o del modelo. Que las a iables ηij se compo en como bina ias sin se lo se
consigue con un núme o O(W2n−2)de es icciones. La cons an e Mpuede oma se
nm´axi=1,...,n{2ξ0
i}+ε, siendo ξ0
ila mi ad de la anchu a en la coo denada OXide la
en ol en e ec angula i e a i a RBde X,YyB=SN
i=1 Bi, y εcualquie cons an e
es ic amen e posi i a. El X1-X2camino ec angula mínimo pe mi ido ob enido po
el modelo puede cons ui se uniendo los pun os (c1
i, ..., ci
n) seleccionados en el óp imo
median e el camino desc i o en la demos ación cons uc i a del Lema 2.14.
2.4. Camino bloque mínimo en p esencia de omboides
ba e a
El Lema 1.5 del capí ulo an e io ponía de mani ies o la elación exis en e en R2en e
la no ma de Manha an y cualquie no ma bloque con cua o ec o es undamen ales.
En es a úl ima sección se ap o echa dicho esul ado pa a da un mé odo de esolución
de un p oblema plano que gene aliza al P oblema 2.1 en R2. Conside emos ijada la
no ma bloque γcon ec o es undamen ales (o denados en el sen ido de las agujas del
eloj)
u1=u1
1, u1
2 , u2=u2
1, u2
2 , u3=u3
1, u3
2 , u4=u4
1, u4
2 ,
74 2.4. Camino bloque mínimo en p esencia de omboides ba e a
cumpliendo u3=−u1yu4=−u2. Un γ- omboide cen ado se á un omboide con
é ices de la o ma
1= u2
1
w1+u1
1
w2
u2
2
w1+u1
2
w2!, 2= u2
1
w1−u1
1
w2
u2
2
w1−u1
2
w2!, 3= −u2
1
w1−u1
1
w2
−u2
2
w1−u1
2
w2!, 4= −u2
1
w1+u1
1
w2
−u2
2
w1+u1
2
w2!,
donde w1, w2>0, mien as que un γ- omboide se á un omboide con é ices de la
o ma w+i,i= 1, ..., 4, siendo w∈R2un ec o cualquie a. Llama emos comple-
jo de γ- omboides a la unión de un núme o ini o de γ- omboides siemp e y cuando
el conjun o esul an e de la unión sea conexo, sin pun os de co e, sin huecos (en el
sen ido que enimos u ilizando es e é mino) y al que pa a cualquie pun o en la on-
e a de un γ- omboide cons i uyen e del complejo que, al mismo iempo, pe enezca al
in e io del complejo, en onces, exis a o o γ- omboide del complejo dis in o al que
dicho pun o pe enece a su in e io . Obsé ese que los complejos de γ- omboides son
conjun os poliéd icos en R2. El siguien e p oblema es una gene alización del P oblema
2.1 en R2.
P oblema 2.2. Dado el conjun o {B1, ..., BN}de complejos de γ- omboides en R2
disjun os dos a dos y dados dos pun os XeYen la egión ac ible F, siendo F=
R2 in (B)yB=SN
i=1 Bi, calcula dB(X, Y ).
Pe o el P oblema 2.2 puede educi se al P oblema 2.1 en R2(pa a el que conocemos
di e en es mé odos de esolución) como mues a el lema que apa ece a con inuación.
Lema 2.18. Pa a la no ma bloque con cua o ec o es undamen ales γ ijada, sea T
la ans o mación lineal de inida en (1.21). En onces, pa a odo X, Y ∈ F,
γB(X, Y ) = `1,T (B)(T(X), T(Y)).
Demos ación. Sean X, Y ∈ F dos pun os ac ibles y sea SP un X-Ycamino pe mi-
ido γ-mínimo con la p opiedad de con ac o con ba e as del Lema 2.3. En onces, SP
es un camino lineal a ozos con un núme o ini o de pun os c í icos I1, ..., Ik∈ F.
Como Tes lineal y biyec i a, la imagen T(SP)de SP es ac ible en T(F), i.e.,
T(SP)⊆T(F). Además, los segmen os en SP son as o mados en segmen os en
T(SP), po lo que T(SP)es ambién un camino lineal a ozos con pun os c í icos
T(Ii),i= 1, ..., k. Fijando I0:= X,Ik+1 := Yy usando el Lema 1.5, ob enemos
γB(X, Y ) =
k
X
i=0
γ(Ii, Ii+1) =
k
X
i=0
`1(T(Ii), T(Ii+1)) ≥`1,T (B)(T(X), T(Y)).
Análogamen e, sea SP0un T(X)-T(Y)camino pe mi ido `1-mínimo con la p opiedad
de con ac o con ba e as en T(F). Sean I0
1, ..., I0
k0∈T(F)el conjun o ini o de pun os
ex emos en SP0y sean I0
0:= T(X)yI0
k0+1 := T(Y). En onces
`1,T (B)(T(X), T(Y)) =
k0
X
i=0
`1(I0
i, I0
i+1) =
k0
X
i=0
γ(T−1(I0
i), T−1(I0
i+1)) ≥γB(X, Y ),
2. Camino ec angula mínimo en p esencia de pa alelepípedos ba e a 75
con lo que se comple a la p ueba.
Análogamen e, puede p oba se que bajo los supues os del Lema 1.5,
`1,B(X, Y ) = γT−1(B)(T−1(X), T−1(Y)).
Pa a e que el P oblema 2.2 puede educi se al P oblema 2.1 en R2bas a eco da que
la longi ud de un X-Ycamino ec angula mínimo pe mi ido es dB(X, Y )(Lema 2.5),
no a que si Bj
ies un γ- omboide en onces T(Bj
i)es un pa alelepípedo iso é ico en R2
y obse a que, po la linealidad de T, si {B1, ..., BN}es un conjun o de complejos
de γ- omboides disjun os dos a dos, en onces {T(B1), ..., T(BN)}es un conjun o de
complejos de pa alelepípedos iso é icos en R2disjun os dos a dos.
3
P oblema de la mediana ec angula
en p esencia de pa alelepípedos
ba e a
La p esencia de ba e as en los p oblemas de localización con inua modi ica las ca-
ac e ís icas geomé icas y analí icas de es os. La no con exidad de las unciones de
dis ancia con ba e a da luga a p oblemas de op imización no con exos. La mayo ía
de mé odos clásicos empleados pa a los p oblemas de localización con inua se basan
undamen almen e en la con exidad de la unción obje i o y po ello allan en es e
con ex o. Po o o lado, los mé odos gene ales de op imización global capaces de a-
a con p oblemas no con exos igno an la geome ía ca ac e ís ica de los p oblemas
especí icos que es amos conside ando. La o ma de lidia con es os p oblemas es, po
an o, desa ollando nue os es udios eó icos y en oques algo í micos que pe mi an su-
pe a las di icul ades mencionadas y pode esol e los e icien emen e. Es e capí ulo se
dedica al a amien o del p oblema, clásico en eo ía de la localización, de la mediana,
cuando las dis ancias son medidas con espec o a la mé ica de Manha an y exis en
complejos de hipe pa alelepípedos iso é icos en la egión ac ible que ac úan como
ba e as. Se p oponen nue os mé odos pa a su esolución basados en los esul ados
ob enidos en el capí ulo an e io pa a el p oblema del camino mínimo ec angula en
p esencia de p a alelepípedos ba e a.
3.1. P oblema de localización con ba e as
Muchas decisiones en ma e ia de ges ión, economía, plani icación de la p oducción,
e c., p esen an ace as elacionadas con la “localización de se icios”. La de e mina-
ción de la ubicación de un nue o almacén con espec o a las de un g upo de e minado
de clien es, eniendo en cuen a los cos es de anspo e y los iempos de en ega, es sólo
un ejemplo den o de una as a gama de aplicaciones de la localización. Po o o lado,
77

78 3.1. P oblema de localización con ba e as
la eo ía de la localización es en sí misma una pa e de in e és den o las ma emá icas,
con un conjun o cada ez mayo de p oblemas y desa íos que no necesa iamen e ienen
un ans ondo eal.
Los p oblemas de localización con inua se plan ean a pa i de un conjun o ini o
de pun os de demanda, los cuales son pun os en el espacio n-dimensional Rn, y que
ep esen an, po ejemplo, la ubicación espacial de clien es. Cla amen e n= 2 on= 3
en los p oblemas del ámbi o eal, sob e odo es os p oblemas se dan en R2, ya que en
las aplicaciones p ác icas a menudo se a a con decisiones de localización en el plano.
Vamos a deno a al conjun o de pun os de demanda po Ex:= {Ex1, ..., ExM}con
el conjun o de índices M:= {1, ..., M}, donde Exm∈Rnpa a odo m∈ M.
En un p oblema de localización con inua debe da se además una medida de dis an-
cia d:Rn×Rn→R, que modela, po ejemplo, el cos e de anspo e o el iempo de
iaje en e dos pun os X, Y ∈Rn. Asumimos que des una mé ica inducida po una
no ma k•kden Rn, es deci , dsa is ace (1.7), (1.8) y (1.9).
En onces, el p oblema de localización con inua consis e en localiza un nue o se -
icio X∈Rnde al mane a que se minimice alguna unción de las dis ancias en e el
nue o se icio Xy los pun os de demanda en Ex:
m´ın (X) = (d(X, Ex1), ..., d(X, ExM))
s.a :X∈Rn.(3.1)
No malmen e es una unción con exa y no dec ecien e de las dis ancias d(X, Exm),
m∈ M.
Un p oblema clásico de localización con inua es el p oblema de la mediana, am-
bién conocido como el p oblema de Webe :
m´ın (X) = PM
m=1 wmd(X, Exm)
s.a :X∈Rn,(3.2)
donde el peso no nega i o wm=w(Exm)especi ica la demanda del pun o de deman-
da Exm,m∈ M. Po an o, el obje i o en el p oblema de la mediana es minimiza el
cos e o al de iaje en e el nue o se icio XyEx. Es e p oblema es el que modela,
po ejemplo, el p oblema de decidi la localización de un almacén con espec o a las
de un conjun o de clien es. Los pesos wmpueden se ambién in e p e ados como una
ponde ación de la impo ancia o p io idad del pun o de demanda Exm, si PM
m=1 = 1
en onces wmpuede conside a se como la p obabilidad de que una demanda alea o ia
ocu a en el pun o Exm,m∈ M, en es e caso, en (3.2) se es a ía minimizando el a-
lo espe ado del cos e de iaje en e el nue o se icio Xy el pun o de demanda de Ex
cuya demanda necesi e se sa is echa en un momen o dado. Obsé ese que los pun os
de demanda con wm= 0 pueden omi i se del modelo sin cambia la unción obje i o.
Po lo an o, asumi emos sin pé dida de gene alidad que odos los pesos wm,m∈ M,
son es ic amen e posi i os.
El desa ollo de modelos de localización ealis as es undamen al en los p ocesos
3. P oblema de la mediana ec angula en p esencia de pa alelepípedos ba e a 79
de decisión donde se ienen que localiza se icios. Especialmen e en el caso de los
modelos de localización plana debe conside a se la ep esen ación geomé ica del p o-
blema, y la ealidad geog á ica iene que se inco po ada en es a ep esen ación. Es o se
aduce en es icciones en el p oblema de localización. Dichas es icciones se co es-
ponden con egiones ales que iaja a a és de ellas es á comple amen e p ohibido o
es imposible. Es as egiones son las ba e as, que en el plano pueden se , po ejemplo,
á eas mili a es, co dille as, o lagos, y en el espacio idimensional, obje os ísicos. Las
aplicaciones de la localización con ba e as se encuen an, en e o os, en los ejemplos
que hemos enido dando a lo la go de la memo ia: diseño de ci cui os, plani icación
de u as en ciudades, en u amien o de ube ías en ba cos, e c.
Conside emos el conjun o de ba e as {B1, ..., BN}, el cual no es más que un con-
jun o ini o de conjun os ce ados y disjun os dos a dos en Rn, y sea B=SN
i=1 Bi.
Como en el capí ulo an e io , el iaje a a és de in (B)no es á pe mi ido, lo que inme-
dia amen e implica que el nue o se icio no pueda localiza se en in (B). Así, la egión
ac ible F ⊆ Rnpa a la ubicación del nue o se icio y pa a mo e se iene dada po
F=Rn in (B). Pa a e i a casos in ac ibles suponemos, como en el capí ulo an e io ,
que Fes un subconjun o conexo de Rn. Además, debe asumi se Exm∈ F pa a odo
m∈ M. La dis ancia ddel p oblema de localización con inua pasa a se aho a una
dis ancia con ba e as dB(De inición 2.2), que, como sabemos, e i ica la desigualdad
iangula (2.4) pe o no es, en gene al, posi i amen e homogénea.
Hechas las suposiciones an e io es, el p oblema de localización con inua con ba-
e as es: m´ın B(X) = (dB(X, Ex1), ..., dB(X, ExM))
s.a :X∈ F,(3.3)
donde B(X) = (dB(X, Ex1), ..., dB(X, ExM)) es una unción de las dis ancias en e
el nue o se icio Xy los pun os de demanda en Ex. Nue amen e, en la mayo ía de
casos, es una unción con exa y no dec ecien e de las dis ancias dB(X, Exm),m∈
M.
El p oblema de la mediana con ba e as se á en onces:
m´ın B(X) = PM
m=1 wmdB(X, Exm)
s.a :X∈ F,(3.4)
siendo los pesos wm,m∈ M, es ic amen e posi i os
Desc i o el p oblema de localización con ba e as, pasamos a plan ea el caso es-
pecial de és e sob e el que e sa el capí ulo.
3.2. P oblema de la mediana ec angula en p esencia
de pa alelepípedos ba e a
Di e en es ex ensiones y a iaciones del p oblema de la mediana han sido ampliamen-
e es udiadas en la li e a u a. Como se adelan aba al comienzo del capí ulo, nos amos
80 3.2. P oblema de la mediana ec angula en p esencia de pa alelepípedos ba e a
a cen a aquí en el p oblema de la mediana cuando las dis ancias son medidas con
espec o a la mé ica de Manha an y exis en ba e as en o ma de complejos de hipe -
pa alelepípedos iso é icos en la egión ac ible.
P oblema 3.1. Dado el conjun o {B1, ..., BN}de complejos de pa alelepípedos iso-
é icos en Rndisjun os dos a dos y dado el conjun o de pun os de demanda Ex=
{Ex1, ..., ExM}en la egión ac ible F, siendo F=Rn in (B)yB=SN
i=1 Bi, es el
p oblema 3.4 cuando d=`1.
Dos mé odos se p oponen pa a esol e el P oblema 3.1: el p ime o consis e en la
ob ención de un conjun o dominan e ini o y es una ex ensión a Rncon n≥2cual-
quie a del mé odo conocido pa a el caso plano de es e p oblema; el segundo es una
o mulación de p og amación lineal y en e a mix a. Ambos mé odos se apoyan en los
esul ados ob enidos en el capí ulo an e io .
3.2.1. Exis encia de conjun o dominan e ini o
Nos plan eamos en p ime luga , como hicimos con el P oblema 2.1, si es posible
es ingi la egión de Fdonde podemos encon a la solución óp ima del P oblema
3.1. Obsé ese que el concep o de en ol en e ec angula i e a i a RBde dos pun os
X, Y ∈ F y de Bde la De inición 2.6, puede ex ende se a Mpun os Ex1, ..., ExMde
F, pa a ello bas a exigi en la De inición 2.6 que, en luga de X, Y ∈ RB,Exm∈ RB
pa a odo m∈ M. U iliza emos la misma no ación RBpa a la en ol en e ec angula
i e a i a de dos pun os que de M, pues la úl ima no es más que una ex ensión de la
p ime a. No es di ícil e la co ección del Algo i mo 2.1 pa a halla la en ol en e
ec angula i e a i a de los pun os de ExyBcuando sólo se cambia en és e el Paso 1,
haciendo Rigual al pa alelepípedo de cen o κ:= ((z+
1+z−
1)/2, ..., (z+
n+z−
n)/2) y
mi ad de la anchu a en cada coo denada OXk,ξk:= |κk−z+
k|=|κk−z−
k|, siendo
z+
k= m´axm∈M{(Exm)k}yz−
k= m´ınm∈M{(Exm)k},k= 1, ..., n.
Lema 3.1. Sean el conjun o de pun os de demanda Ex={Ex1, ..., ExM}y la unión
de los conjun os ba e a B=SN
i=1 Bidel P oblema 3.1, en onces, la solución óp ima
X∗del P oblema 3.1 es á con enida en la en ol en e ec angula i e a i a RBde los
pun os de ExyB.
Demos ación. Si X∗∈ RB, en onces, po el Lema 2.5 y po el Lema 2.7, exis e un
X∗-Exmcamino ec angula mínimo pe mi ido de longi ud dB(X∗, Exm)comple a-
men e con enido en RB, pa a odo m∈ M. Po an o, pa a azona po educción
al absu do, podemos asumi que no hay ba e as en Rn RB, pues o que es a asun-
ción sólo pod ía dec emen a el alo en la unción obje i o del P oblema 3.1 de los
pun os que no es án con enidos en RB, mien as que no iene e ec o sob e el alo en
la unción obje i o del P oblema 3.1 de los pun os que sí lo es án. Supongamos que
X∗/∈ RB. Sea QExmel X∗-Exmcamino ec angula mínimo pe mi ido de longi ud
dB(X∗, Exm)que da el Lema 2.5, m∈ M. Sea Zmel úl imo pun o de QExmen la
3. P oblema de la mediana ec angula en p esencia de pa alelepípedos ba e a 81
on e a de RBcuando QExmse eco e desde X∗has a Exm,m∈ M. Vamos a dis-
ingui dos casos.
Supongamos en p ime luga que P oyˆ
j(X∗)∈in (P oyˆ
j(RB)) pa a cie o j∈
{1, ..., n}. El índice jes único, de lo con a io se end ía que X∗∈ RB. Además, si
deno amos po (κ1, ..., κn) al cen o de RBy a la mi ad de su anchu a en cada coo de-
nada po ξi,i= 1, ..., n, en onces, x∗
j< κj−ξjox∗
j> κj+ξj, pues en caso con a io
nue amen e se end ía X∗∈ RB. Sea XJel pun o de Rncon odas sus componen es
iguales a las de X∗sal o la j-ésima, que es κj+sξj, siendo s∈ {−1,1} al que
|x∗
j−(κj+sξj)|es mínimo. El pun o XJpe enece a la on e a de X∗∈ RB, y po
an o, a F.
Como Zmes el úl imo pun o de QExmen la on e a de RBcuando QExmse e-
co e desde X∗has a Exm, conside a a RBcomo una ba e a, única pues con iene a
las demás, no a ec a al alo de dB(X∗, Zm), es deci , dB(X∗, Zm) = dRB(X∗, Zm),
m∈ M. A pa i del Lema 2.9 se deduce que, si X∗yZmson `1- isibles, en onces
XJyZm ambién lo son, y si X∗yZmno son `1- isibles, en onces XJyZm am-
poco lo son, pa a odo m∈ M. En cualquie caso, los sumandos de d`1(X∗, Zm)y
d`1(XJ, Zm), si X∗yZmson `1- isibles, o los de las exp esiones de dRB(X∗, Zm)y
dRB(XJ, Zm)que da el Lema 2.9, si X∗yZmno son `1- isibles, son los mismos sal o
|x∗
j−(Zm)j|y|xJ
j−(Zm)j|,m∈ M. Pe o |xJ
j−(Zm)j|<|x∗
j−(Zm)j|pa a odo
m∈ M, lo que signi ica que XJp opo ciona un meno alo obje i o que X∗en el
P oblema 3.1, ya que po la desigualdad iangula se iene que
dB(XJ, Exm)≤dB(XJ, Zm)+l(QExm
Zm,Exm)< dB(X∗, Zm)+l(QExm
Zm,Exm) = dB(X∗),
siendo el camino ec angula QExm
Zm,Exmla po ción del camino ec angula QExmque a
de ZmaExm,m∈ M. Que XJp opo cione un meno alo obje i o que X∗en el
P oblema 3.1 con adice que X∗sea la solución óp ima del P oblema 3.1.
Supongamos aho a que P oyˆ
j(X∗)∈in (P oyˆ
j(RB)) no se da pa a ningún j∈
{1, ..., n}. Nue amen e amos a usa que, como Zmes el úl imo pun o de QExmen la
on e a de RBcuando QExmse eco e desde X∗has a Exm, podemos conside a a
RBcomo única ba e a a la ho a de calcula dB(X∗, Zm),m∈ M. Como P oyˆ
j(X∗)∈
in (P oyˆ
j(RB)) no se da pa a ningún j∈ {1, ..., n}, en onces, u ilizando el Lema 2.9,
se deduce que X∗yExmson `1- isibles pa a odo m∈ M. Además, al menos uno
de las desigualdades x∗
j< κj−ξjox∗
j> κj+ξjse da pa a algún j∈ {1, ..., n}, de
lo con a io X∗pe enece ía a RB. Tomemos k∈ {1, ..., n}donde se dé alguna de las
desigualdades an e io es. Sea XKel pun o de Rncon odas sus componen es iguales a
las de X∗sal o la k-ésima, que es κk+sξk, siendo s∈ {−1,1} al que |x∗
k−(κk+sξk)|
es mínimo. Del Lema 2.9 se deduce que, como X∗yZmson `1- isibles, en onces XK
yZmson ambién `1- isibles, pa a odo m∈ M. Los sumandos de d`1(X∗, Zm)y
d`1(XK, Zm)son los mismos, sal o |x∗
k−(Zm)k|y|xK
k−(Zm)k|,m∈ M. Pe o
obsé ese que |xK
k−(Zm)k|<|x∗
k−(Zm)k|pa a odo m∈ M, lo que signi ica que
XKp opo ciona un meno alo obje i o que X∗en el P oblema 3.1, ya que po la
88 3.3. P oblema de la mediana bloque en p esencia de omboides ba e a
Teo ema 3.3. Sean el conjun o de pun os de demanda Ex={Ex1, ..., ExM}y el
conjun o de ba e as {B1, ..., BN}del P oblema 3.2, y sea Tla ans o mación lineal
de inida en (1.21). El pun o X∗∈R2es una solución óp ima del P oblema 3.2 si
y sólo si T(X∗)es una solución óp ima del P oblema 3.1 con pun os de demanda
T(Ex) = {T(Ex1), ..., T(ExM)}y ba e as {T(B1), ..., T(BN)}.
Demos ación. No ando que si Bes un γ- omboide en onces T(B)es un pa alele-
pípedo iso é ico en R2y que, po la linealidad de T, si {B1, ..., BN}es un conjun o
de complejos de γ- omboides disjun os dos a dos, en onces {T(B1), ..., T(BN)}es
un conjun o de complejos de pa alelepípedos iso é icos en R2disjun os dos a dos, el
esul ado se sigue di ec amen e del Lema 2.18.
Po an o, de acue do al Teo ema 3.3, pa a esol e el P oblema 3.2 podemos ans o -
ma lo median e Ten un p oblema del ipo del P oblema 3.1, y aplica a és e úl imo
cualquie a de los dos mé odos dados en el capí ulo pa a su esolución, la solución óp i-
ma del p oblema sin ans o ma es la ans o mada in e sa T−1de la solución óp ima
del p oblema ans o mado.

4
P uebas compu acionales
En es e capí ulo se ecogen algunos esul ados de endimien o compu acional ob eni-
dos con los modelos de p og amación lineal y en e a mix a pa a esol e el p oblema
del camino mínimo ec angula y el p oblema de la mediana ec angula en p esencia
de pa alelepípedos ba e a p esen ados en los capí ulos segundo y e ce o, espec i a-
men e.
4.1. Rendimien o de los modelos de p og amación li-
neal y en e a mix a
En p ime luga se an a compa a el endimien o de los modelos (2.6)-(2.30), (2.62)-
(2.88) y (2.102)-(2.121) a la ho a de esol e el p oblema del camino mínimo ec-
angula en p esencia de un pa alelepípedo iso é ico ba e a en Rn. Los esul ados
que se mues an en la Tabla 4.1 son la media del iempo en segundos ob enido pa a
diez ins ancias del p oblema. Los pun os XeYa uni se han omado de o ma que
P oyˆ
1(X),P oyˆ
1(Y)∈in (P oyˆ
1(B)) ym´ın{x1, y1}< κ1<m´ax{x1, y1}, siendo B
el pa alelepípedo iso é ico ba e a y κ1la p ime a coo denada de su cen o. Es deci , se
han omado pun os que no son `1- isibles, de acue do al Lema 2.9. Como co a supe io
pa a el núme o de codos u ilizados del modelo (2.62)-(2.88) se ha omado la que da el
Lema 2.12. En cuan o al modelo (2.102)-(2.121), se ha omado una descomponsición
en 2npa alelepípedos iso é icos de RB in (B)(núme o de ca as de dimensión n−1
de B), siendo RBla en ol en e ec angula i e a i a de X,YyB. Ni en la Tabla
4.1, ni en ninguna de las pos e io es, se añaden los iempos de la descomposición en
pa alelepípedos iso é icos de RB in (B)necesa ia pa a el modelo (2.102)-(2.121),
sólamen e el iempo necesa io pa a ob ene la solución óp ima del modelo.
89
90 4.1. Rendimien o de los modelos de p og amación lineal y en e a mix a
Modelo n
2 3 4 5 8 27
(2.6)-(2.30) 0 0 0.0016 0.003 0.0047 38.1341
(2.62)-(2.88) 0.0889 0.2016 2.8079 19.173 (*) -
(2.102)-(2.121) 0.0015 0.0076 0.0111 0.0169 0.0234 48.6149
Tabla 4.1: Tiempo medio en segundos pa a diez ins ancias ob enidos po los mode-
los (2.6)-(2.30), (2.62)-(2.88) y (2.102)-(2.121) pa a esol e el P oblema 2.1 en Rn
cuando B=B.
Con (*) no amos que pa a al menos es ins ancias se ha ob endio un iempo supe io
a 600 segundos. La esolución del p oblema con cualquie a de los es modelos es
p ác icamen e inmedia a has a R3. El modelo (2.62)-(2.88) es el que p esen a peo es
esul ados. Es o se debe a que el núme o de a iables bina ias que u iliza es un múl iplo
de la dimensión y del núme o de ba e as, en pa icula de la dimensión, es po ello
que al aumen a la dimensión se ob ienen peo es esul ados. En ocasiones, el óp imo
de (2.62)-(2.88) se alcanza pa a un núme o de codos in e io al que da la co a del
Lema 2.12, en es os casos, disminui el núme o de codos mejo a el endimien o del
modelo. Sin emba go, una educción de la co a del núme o de codos que da el Lema
2.12 a p io i sin que es o a ec e a la solución óp ima del p oblema no es posible. Los
modelos (2.6)-(2.30) y (2.102)-(2.121) esuel en el p oblema de o ma p ác icamen e
inmedia a has a dimensiones ele adas. Se ha omado R27 pa a ilus a has a donde
pueden los modelos an e io es esol e el p oblema en un iempo azonable.
Pa a los mismos modelos an e io es, se conside a el P oblema 2.1 cuando B=
B1∪B2, siendo B1yB2dos pa alelepípedos iso é icos disjun os. Los pun os XeY
a uni se han omado de o ma que P oyˆ
1(X)∈in (P oyˆ
1(B1)),x1< κ1
1, P oyˆ
1(Y)∈
in (P oyˆ
1(B2)) yκ2
1< y1, con κ1
1< κ2
1, deno ando κ1
1yκ2
1la p ime a coo denada del
cen o de B1yB2 espec i amen e. Los esul ados se mues an en la Tabla 4.2. Pa a
el modelo (2.102)-(2.121), se ha omado una descomponsición en 4npa alelepípedos
iso é icos de RB B, con B=B1∪B2.
Modelo n
2 3 4 5 7
(2.6)-(2.30) 0.0702 0.2528 0.7303 4.4195 53.416
(2.62)-(2.88) 1.10955 46.3977 (*) - -
(2.102)-(2.121) 0.0173 0.0593 0.1271 0.2103 0.5259
Tabla 4.2: Tiempo medio en segundos pa a diez ins ancias ob enidos po los mode-
los (2.6)-(2.30), (2.62)-(2.88) y (2.102)-(2.121) pa a esol e el P oblema 2.1 en Rn
cuando B=B1∪B2, con B1∩B2=∅.
Nue amen e el modelo (2.62)-(2.88) es el que p esen a peo es esul ados, pues co-
mo hemos dicho, el núme o de a iables bina ias que emplea es un ac o , además de
4. P uebas compu acionales 91
la dimensión, del núme o de obs áculos. Es a ez el modelo (2.102)-(2.121) pa ece
p esen a mejo es esul ados que el modelo (2.6)-(2.30) especí ico pa a el p oblema.
Es o puede debe se a que el núme o de a iables bina ias empleadas po el modelo
(2.6)-(2.30) es cuad á ico espec o a la dimensión, mien as que el de (2.102)-(2.121)
es cua o eces la de es a ( ecué dese que el núme o de a iables bina ias empleadas
po el modelo (2.102)-(2.121) es igual al núme o de pa alelepípedos en las que se des-
compone RB in (B)). A es o hay que suma que el núme o de a iables posi i as y
es icciones del modelo (2.102)-(2.121), las cuales dependen de las conexiones (a is-
as) en e los pa alelepípedos en los que se descompone RB in (B), no es muy ele ado
pa a las dimensiones conside adas y la descomposición hecha de RB in (B), de lo
con a io el iempo de esolución pod ía e se inc emen ado.
Po úl imo, se an a mos a los esul ados en R2yR3ob enidos con el modelo
(3.7)-(3.31) pa a esol e el p oblema de la mediana ec angula en p esencia de pa a-
lelepípedos ba e a. En la Tabla 4.3 se indica el núme o de pa alelepípedos Wconsi-
de ados en R2así como el núme o de complejos de pa alelepípedos Na los que dan
luga las in e secciones de es os. La descomposición en pa alelepípedos de RB in (B)
en R2se ha hecho u ilizando el Algo i mo 2.2. En R3se han omado pa alelepípedos
ba e a disjun os y una descomposición en pa alelepípedos de RB in (B)consis en e
en 6Wpa alelepípedos. Los esul ados en R3se ecogen en la Tabla 4.4.
Modelo (3.7)-(3.31) W= 5
pdd: 5 N= 2 N= 3 N= 5
Tiempo 0.7739 0.7941 3.11545
|C0|11.3 11.9 15.1
Modelo (3.7)-(3.31) W= 10
pdd: 10 N= 3 N= 4 N= 5 N= 6
Tiempo 14.3964 88.1551 88.3272 133.2273
|C0|16.7 20.2 20.1 22.3
Modelo (3.7)-(3.31) W= 4
pdd: 15 N= 2 N= 3 N= 4
Tiempo 2.779 9.6394 93.0912
|C0|10 10.4 12
Tabla 4.3: Tiempo medio en segundos y núme o medio de pa alelepípedos en los que se
descompone RB in (B)pa a diez ins ancias ob enidos po el modelo (2.102)-(2.121)
en R2. El núme o de pun os de demanda lo no amos po pdd.
92 4.1. Rendimien o de los modelos de p og amación lineal y en e a mix a
Modelo (3.7)-(3.31) pdd/N
3/4 5/3 10/2
Tiempo 56.5247 121.3554 32.7707
Tabla 4.4: Tiempo medio en segundos pa a diez ins ancias ob enidos po el modelo
(2.102)-(2.121) en R3. El núme o de pun os de demanda lo no amos po pdd.
El iempo de esolución del modelo aumen a con el núme o de complejos, aunque
el núme o de pa alelepípedos cons i uyen es sea el mismo. Es o se debe como puede
e se a que el núme o de pa alelepípedos en los que se descompone RB in (B)au-
men a con el núme o de complejos y, en consecuencia, aumen a el núme o de a iables
bina ias de (3.7)-(3.31). Los esul ados ob enidos con el modelo (3.7)-(3.31) pueden
cali ica se de modes o. Es posible que es o se deba a que la es a egia de educi el nú-
me o de a iables bina ias del modelo a cos a de aumen a el núme o de es icciones
no es é p opo cionando los esul ados deseados. Es a es a egia se aduce en un mayo
iempo de esolución del p oblema elajado en cada nodo del á bol que da el mé odo
de ami icación y aco ación, pe o educiendo la dimensión de dicho á bol. Se ía con e-
nien e compa a es os esul ados con los ob enidos al modi ica el modelo (3.7)-(3.31)
de o ma que las a iables que ep esen an a is as sean bina ias, desca ándose así las
es icciones necesa ias pa a la es a egia an es desc i a.
Conclusiones
En es e T abajo de Fin de Más e se han es udiado las unciones de dis ancia con ba e-
as y su aplicación a los p oblemas de camino mínimo y localización. La p esencia de
ba e as en es os p oblemas modi ica las ca ac e ís icas geomé icas y analí icas de los
mismos. La no con exidad de las unciones de dis ancia con ba e as da luga a p o-
blemas de op imización no con exos. La mayo ía de mé odos clásicos empleados pa a
los p oblemas de camino mínimo y localización con inua se basan undamen almen e
en la con exidad de la unción obje i o y po ello allan en es e con ex o. Po o o
lado, los mé odos gene ales de op imización global capaces de a a con p oblemas
no con exos igno an la geome ía ca ac e ís ica de es os p oblemas. La o ma de lidia
con es os p oblemas es, po an o, desa ollando nue os es udios eó icos y en oques
algo í micos que pe mi an supe a las di icul ades mencionadas y pode esol e los
e icien emen e.
En es a memo ia se han p opues o di e en es y no edosos mé odos pa a esol e
el p oblema del camíno mínimo ec angula y el p oblema de la mediana ec angula
en p esencia de complejos de hipe pa alelepípedos que ac úan como ba e as en cual-
quie espacio eal de dimensión ini a. Es os mé odos se apoyan en esul ados eó icos
y algo í micos que explo an la geome ía de los caminos mínimos ec angula es en
egiones ac ibles es ingidas po pa alelepípedos ba e a. Dichos mé odos son unda-
men almen e p oblemas de p og amación lineal y en e a mix a que pueden apoya se
en descomposiciones en pa alelepípedos de la egión ac ible. Una ex ensión al caso
n-dimensional del mé odo basado en la ob ención de un conjun o dominan e pa a el
p oblema de la mediana con ba e as conocido en el plano es o a de las apo aciones
del abajo.
Las p uebas compu acionales ob enidas indican que el endimien o de los modelos
p opues os debe mejo a se. Dicha mejo a, así como la e aluación del endimien o de
la ex ensión al caso n-dimensional del mé odo basado en un conjun o dominan e an es
mencionado, se ealiza á en una colabo ación más amplia con el di ec o del abajo.
En caso de no pode mejo a se los esul ados ob enidos con los modelos de p og ama-
ción ma emá ica, los esul ados desa ollados pa a su cons ucción pod ían u iliza se
pa a cons ui me aheu ís icos que combinen, po ejemplo, algo i mos gené icos y bús-
queda abú. La posible ex ensión del p oblema al uso de o as no mas es o o ema que
se end á en cuen a.
93

Bibliog a ía
[1] BISCHOFF, M., AND KLAMROTH, K. An e icien solu ion me hod o webe
p oblems wi h ba ie s based on gene ic algo i hms. Eu opean Jou nal o Ope-
a ional Resea ch 177, 1 (2007), 22–41.
[2] BUTT, S. E., AND CAVALIER, T. M. An e icien algo i hm o acili y loca ion
in he p esence o o bidden egions. Eu opean Jou nal o Ope a ional Resea ch
90, 1 (1996), 56–70.
[3] DEREZENDE, P. J., LEE, D.-T., AND WU, Y.-F. Rec ilinea sho es pa hs wi h
ec angula ba ie s. In P oceedings o he i s annual symposium on Compu-
a ional geome y (1985), ACM, pp. 204–213.
[4] DEARING, P., HAMACHER, H., AND KLAMROTH, K. Domina ing se s o ec-
ilinea cen e loca ion p oblems wi h polyhed al ba ie s. Na al Resea ch Lo-
gis ics (NRL) 49, 7 (2002), 647–665.
[5] HAMACHER, H. W., AND KLAMROTH, K. Plana loca ion p oblems wi h ba-
ie s unde polyhed al gauges.
[6] ICKING, C., KLEIN, R., MA, L., NICKEL, S., AND WEISSLER, A. On bisec o s
o di e en dis ance unc ions. Disc e e applied ma hema ics 109, 1 (2001),
139–161.
[7] KLAMROTH, K. A educ ion esul o loca ion p oblems wi h polyhed al ba-
ie s. Eu opean Jou nal o Ope a ional Resea ch 130, 3 (2001), 486–497.
[8] KLAMROTH, K. Single- acili y loca ion p oblems wi h ba ie s. Sp inge Scien-
ce & Business Media, 2006.
[9] LARSON, R. C., AND SADIQ, G. Facili y loca ions wi h he manha an me ic
in he p esence o ba ie s o a el. Ope a ions Resea ch 31, 4 (1983), 652–669.
[10] LOVE, R. F., AND MORRIS, J. G. A compu a ion p ocedu e o he exac solu-
ion o loca ion-alloca ion p oblems wi h ec angula dis ances. Na al Resea ch
Logis ics (NRL) 22, 3 (1975), 441–453.
95
96 Bibliog a ía
[11] MINKOWSKI, H. Gesammel e abhandlungen, zwei e band. sl]: Nabu P ess.-
2010-468 S (1967).
[12] NICKEL, S. Disc e iza ion o plana loca ion p oblems. Ve lag Shake , 1995.
[13] WARD, J. E., AND WENDELL, R. E. Using block no ms o loca ion modeling.
Ope a ions Resea ch 33, 5 (1985), 1074–1090.