Loca ing a Cen al Hun e on he Plane
M. Ce a · J.A. Mesa · F.A. O ega · F. Plas ia
Abs ac P o ec ion, su eillance o o he ypes o co e age se ices o mobile
poin s call o di e en , asymme ic dis ance measu es han he adi ional
Euclidean, ec angula o o he no ms used o ixed poin s. In his pape , he
des ina ions a e mobile poin s (p ey) mo ing a ixed speeds and di ec ions and he
acili y (hun e ) can cap u e hem using one o wo possible s a egies: ei he i is
sma , p edic ing he p ey’s mo emen in o de o minimize he ime needed o
cap u e i , o i is dumb, ollowing a pu sui cu e, by mo ing a any momen in he
di ec ion o he p ey. In ei he case, he hun e loca ion in a plane is sough in o de
o minimize he maximum ime o cap u e o any p ey. An e icien solu ion
algo i hm is de eloped ha uses he pa icula geome y ha bo h e sions o his
p oblem possess. In he case o unp e-dic able mo emen o p ey, a wo s -case ype
solu ion is p oposed, which educes o he well-known weigh ed Euclidean minimax
loca ion p oblem.
The wo k o he second and hi d au ho s was suppo ed in pa by a g an om Resea ch P ojec s
BFM2003-04062 and MTM2006-15054.
M. Ce a ()
Depa men o Applied Ma hema ics I, Ag icul u al Technical Enginee ing Uni e si y School,
Uni e si y o Se ille, Se ille, Spain
e-mail: [email p o ec ed]
J.A. Mesa
Depa men o Applied Ma hema ics II, Enginee ing Highe Technical School,
Uni e si y o Se ille, Se ille, Spain
F.A. O ega
Depa men o Applied Ma hema ics I. A chi ec u e Highe Technical Uni e si y School,
Uni e si y o Se ille, Se ille, Spain
F. Plas ia
Depa men o Ma hema ics, Ope a ional Resea ch, S a is ics and In o ma ion Sys ems
o Managemen , V ije Uni e si ei , B ussel, Belgium
Keywo ds Con inuous loca ion ·T a el ime ·Cen e p oblem ·Hun e dis ance ·
Skewed no m ·Ellip ic gauge ·Game heo y
1 In oduc ion
The plana cen e objec i e, in e ms o dis ance, a el ime o global anspo cos ,
is commonly used o loca ion decisions in eme gency se ice sys ems, in dis ibu ion
p oblems o in elecommunica ions. Typically he poin s o be p o ec ed, se iced o
co e ed in some o he way ha e a ixed and known posi ion, and he dis ance measu e
used is de i ed om some no m, e.g. he Euclidean, ec angula , o ano he no m,
acco ding o he pa icula ci cums ances o he p oblem ins ance [1].
Howe e , mobili y o des ina ion poin s is also ele an in many con ex s. P o ec -
ing mobile objec s, howe e , is a di e en ma e om p o ec ing ixed poin s, since
a en ion should be paid o he s a egy used by he pu suing acili y (hun e ) o he
cap u e o he mobile des ina ions (p ey).
Two phases a e commonly conside ed in o de o plan s a egies o cap u ing he
se o e ade s:
Phase 1 De e mine an ini ial in elligen loca ion o s a he po en ial cap u e o any
p ey.
Phase 2 Es ablish ac ical decisions o he hun e once di e en oles ha e been as-
signed o he p ey, such as being he i s p ey o be cap u ed among all he exis ing
op ions.
This pape explo es he i s phase: i deals wi h he ixed s a egic s a ing loca ion o
he pu suing acili y in o de o be e icien ly a ailable o se ing mobile des ina ions
a e hei cap u e.
When he ajec o y o an objec is ully p edic able i is possible o de e mine
in ad ance he way in which i may be eached in he sho es possible ime. This
s a egy calls, howe e , o analy ical capaci ies and da a p ocessing, which is why
we e e o i as a sma hun e , since i s beha io canno be achie ed by an au o-
ma ed o non- a ional acili y. Fo such a dumb hun e , ano he less e icien s a egy
should be applied: simply keep he a ge in iew a all imes du ing he pu sui and
always mo e head-on in ha di ec ion. This is he na u al s a egy ollowed by p eda-
o s and also he simples o p og am in o an au oma ed sys em wi h isual eedback.
This mo emen s a egy was al eady analy ically s udied by Leona do da Vinci. Fo
nice p ey, always ollowing a s aigh ajec o y a cons an eloci y, Geo ge Boole
e oneously de i ed ha i esul s in a pa abolic pa h o he hun e . Al hough ele-
men a y pa icula cases ha e been deal wi h be o e, he gene al case o analy ically
desc ibing he pu sui ajec o ies in 2D and 3D by means o di e en ial equa ions
was ob ained only ecen ly by Ba on and Elieze [2,3]. In a u he analysis o he
dynamics in ol ed, Ce a and O ega [4] de i ed a simple explici exp ession called
he hun e dis ance o he ime needed o cap u e a nice p ey unde his s a egy.
In his pape , we s udy cen e p oblems in such dynamic ci cums ances, conside -
ing bo h he dumb hun e and he sma hun e cases. We show ha he ideas based
on he classical algo i hms o sol ing he plana Euclidean cen e p oblem may be
adap ed o all he s udied cases. In some o hese, we may use he classical me hod
di ec ly a e a sui able ans o ma ion. Then, we also s udy wha o do in case p ey is
nas y and mo es in unp edic able ways (bu wi h known maximum speed). In Sec . 4,
we show ha he wo s -case s a egy o minimising he maximum possible cap u e-
ime o any p ey in any o i s mo emen s, may always be educed o a weigh ed
Euclidean cen e p oblem.
2 Hun e Dis ances
2.1 Dumb Hun e Dis ance
Le X(hun e ) be mobile wi h eloci y β, which is pu suing mobile A(p ey) mo ing
along a e ical line a eloci y α<β. I is assumed ha du ing he pu sui he dumb
hun e mo es a e e y momen in he di ec ion o he p ey’s cu en posi ion (pu sui
cu es, see [3]). In [4], he ime τ equi ed o he cap u e was shown o be he
ollowing linea combina ion o he Euclidean · and ‘ e ical’ dis ances be ween
he s a ing poin s a ime =0 o hun e (X=(x0,y0)) and p ey (A=(xA,yA)):
τ(A,X)=β
β2−α2A−X+ α
β2−α2(yA−y0). (1)
The gene al case, o a hun e s a ing om Xa speed β, and he p ey’s uni - ime
mo emen gi en by a gene al ec o pwi h p<β, is ob ained by a simple o a ion
o he axes, and using
λ2=β2−p2
yields he ollowing exp ession:
τ(A,X)=β
λ2A−X− 1
λ2p,A −X.(2)
This exp ession shows ha he dumb hun e dis ance τbelongs o he amily o
skewed no ms in oduced by Plas ia [5]. In gene al, o any no m N(·)on Rnwi h
dual N◦(·)and any ec o s∈Rnwi h N◦(s) < 1, he skewed no m (N,s) is de ined
by
(N,s) (X) =N(X)−s,X,
whe e ·,·deno es scala p oduc . He e,
N(X)=β
λ2Xand s=α
λ2p.
The isoch onic cu e o ime τ(se o all p ey’s s a ing poin s cap u ed a ime τ)
will he e o e be he (unique) ellipse wi h he ollowing p ope ies (see Fig. 1a): Xis
a ocal poin , he cen e o symme y is a poin X−τp and i has long axis pa allel
o pwi h hal -leng h βτ, and sho axis hal -leng h λτ. In e sely, o a p ey s a ing
om A, all hun e s a ing posi ions cap u ing i a ime τis ob ained as ollows: i s
cons uc he ellipse cen e ed a A, wi h long axis o hal -leng h βτ and pa allel o p,
and sho axis hal -leng h λτ ; secondly, shi i o e ec o τp (see Fig. 1b).
(a) Cap u e by hun e Xo any p ey (b) Cap u e o p ey A any hun e
wi hin he ellipse wi hin his ellipse
Fig. 1 Dumb hun e isoch onic ellipses (τ=1.5)
2.2 Sma Hun e Dis ance
A sma hun e s a ing om Xand able o mo e a speed βwill be able o each a
ime , all poin s o he Euclidean ci cle C(X,β ) cen e ed a Xand adius β .Fo
a p ey o be caugh by he sma hun e a ime , i should each his same ci cle
exac ly a ime . To his end, o a p ey s a ing om Aand mo ing linea ly wi h
uni -mo emen ec o p, we should ha e
A+ p ∈C(X,β ),
which is ei he exp essed as
A−X+ p=β
o as
A∈ (C(X,β)−p). (3)
The i s equa ion yields
λ2 2−2A−X, p −A−X2=0,
whe e as be o e λ2=β2−p2. In he coo dina e sys em wi h o igin X o a ed
so ha he p ey mo es downwa d a speed α,i.e.p=(0,−α), and deno ing he
coo dina es o Ain his sys em by (xA,yA), he p e ious equa ion educes o
λ2 2+2αyA −(x2
A+y2
A)=0,
whose only nonnega i e solu ion is
=(λxA)2+(βyA)2−αyA
λ2=T(A)+q,A,
wi h T he linea ope a o o ma ix
T=1
λ2λ0
0β
and
q=1
λ2p.
This shows ha he sma hun e dis ance is also a gauge om he skewed no m
amily. A gene al exp ession alid in any coo dina e sys em is gi en by
(A,X)=TR(A−X)+ 1
λ2p,A −X,(4)
whe e Tand λa e as abo e, and Rdeno es he o a ion b inging p o a downwa d
e ical posi ion. Mo eo e , (3) shows ha he uni ball o his skewed no m is a ci cle
o adius βwi h cen e displaced o e −p.
2.3 Compa ison o Hun e Dis ances
As shown in Fig. 2 he sma hun e dis ance uni -ball is he smalles ci cle con aining
he uni -ellipse o he dumb hun e dis ance wi h he same hun e speed and p ey
mo emen . This illus a es (and ollows om) he ollowing qui e e iden ac s:
•Dumb hun e dis ance is always la ge han sma hun e dis ance: any p ey cap-
u ed wi hin ime τby a dumb hun e is caugh by a sma hun e in ime ≤τ.
•Any p ey s a ing a Euclidean dis ance d om he hun e ’s s a ing posi ion, and
mo ing di ec ly owa ds his poin , will be cap u ed in ime d/(β +α) by bo h a
dumb hun e and a sma hun e because bo h s a egies coincide in his pa icula
case and use he same linea hun e ajec o y.
•Simila ly, any p ey s a ing a Euclidean dis ance d om he hun e ’s s a ing posi-
ion, and mo ing di ec ly away om his poin , will be cap u ed in ime d/(β −α)
by bo h a dumb hun e and a sma hun e .
Fig. 2 Uni balls o he dumb
and he sma hun e

•Fo any p ey s a ing a Euclidean dis ance d om he hun e ’s s a ing posi ion,
we ha e
d
β+α≤ ≤τ≤d
β−α.
• =τ, i.e. sma and dumb hun e dis ances a e equal, i and only i α=0o p ey
mo es in he hun e ’s di ec ion, o opposi e o i .
3 Cen al Hun e P oblem wi h Nice P ey
3.1 Gene al Case
Le
A={A1,A2,...,An}
be a ini e se o poin s (n>1) on he plane ep esen ing he ini ial posi ions o
p ey, each mo ing linea ly as gi en by he uni -mo emen ec o s pi(i=1,...,n).
A single hun e is conside ed able o mo e a cons an speed β>pi o all i.I is
equi ed o de e mine a s a ing posi ion o he hun e , minimising he ime needed
o cap u e any o hese p ey.
Deno ing he s a ing posi ion o he hun e by X, he op imal loca ion o a cen al
hun e is ob ained by sol ing he ollowing minimax op imiza ion p oblem:
(PA)min
X∈R2F(X):=max
i i(X),
whe e i(X) is he ime o cap u e o p ey Aiby a hun e s a ing om X. In case o
a dumb hun e , i(X) is calcula ed as τ(Ai,X)gi enby(2) wi h p=pi, while o a
sma hun e , he exp ession (Ai,X)in (4), sui ably adap ed, should be used.
As a di ec consequence o he esul s o Peleg ín, Michelo and Plas ia [6] and
D ezne [7], we ob ain he ollowing p oposi ion.
P oposi ion 3.1 The unc ions i(X) a e con inuous,di e en iable anywhe e excep
a Ai,con ex and ha e s ic ly con ex and bounded le el se s,which a e all ellipses,
so a e s ongly quasicon ex.P oblem (PA)has a unique op imal solu ion and he e
exis s a subse A⊂Aei he ha ing 2o 3elemen s,so ha he op imal solu ion X∗
o p oblem (PA)is also he op imal solu ion o p oblem (PA).
Al hough in p inciple sol able by any gene al pu pose non-di e en iable con ex
op imisa ion me hod, by P oposi ion 3.1, he gene al p oblem may also be sol ed by
conside ing all subp oblems limi ed o only 2 o 3 p ey sepa a ely. We conside each
case in u n.
Fo wo p ey wi h A1=A2, he op imal solu ion o (PA) is e iden ly eached a
X=A1=A2. In case A1=A2, we ha e he ollowing p oposi ion.
P oposi ion 3.2 Le A={A1,A2}wi h A1=A2, hen he unique op imal solu ion
o p oblem (PA)consis s o he solu ion o he equa ion sys em in wo a iables
1(X) = 2(X), (5)
∇ 1(X) =−∇ 2(X). (6)
P oo Conside any poin Xwi h 1(X) > 2(X). Since 1(·)is con inuous, by mo -
ing Xclose o A1, 1s ic ly dec eases, and hus also F, showing ha Xcanno be
op imal. Simila ly any Xwi h 1(X) < 2(X) canno be op imal. The e o e (5) holds
o any op imal X∗. Since A1=A2, we canno ha e 1(X∗)= 2(X∗)=0. Hence
a any poin Xwhe e 1(X) = 2(X) bo h unc ions a e di e en iable. Equa ion (6)
hen exp esses he s anda d op imali y condi ion o F(X)=max( 1(X), 2(X)). 
The (by P oposi ion 3.1 unique) solu ion o he sys em (5,6) will be deno ed by
X(A1,A2)and he co esponding unc ion alue ob ained in (5)byF(A1,A2).This
case is illus a ed in Fig. 3.
The ollowing wo p oposi ions a e now e iden , desc ibing he case o a h ee-
p ey subse ei he educible o a wo-p ey subse o no .
P oposi ion 3.3 Fo a h ee-p ey se A={A1,A2,A3} he op imal solu ion o (PA)
is de e mined by i s subse {A1,A2}i and only i we ha e 3(X(A1,A2)) ≤
F(A
1,A2).
P oposi ion 3.4 Le A={A1,A2,A3}be such ha no s ic subse o Ayields an
op imal alue o (PA), hen he unique op imal solu ion o his p oblem (PA)consis s
o he solu ion o he sys em o wo equa ions in wo a iables gi en by
1(X) = 2(X) = 3(X), (7)
which yields he lowes alue o i .
In his las case he op imal solu ion will be deno ed by X(A1,A2,A3)and he
co esponding unc ion alue by F(A1,A2,A3).
In he sequel we conside ha sol ing he wo o h ee p ey se p oblems may
be done e icien ly, e.g. by way o some s anda d equa ion sol ing ools a ailable
in ma hema ical so wa e. Since his may in ol e ela i ely in ensi e calcula ions, in
o de o cons uc he cen al hun e posi ion e icien ly he numbe o such subp ob-
lems o be sol ed should be educed as much as possible. This may be ob ained using
s a egies simila o hose de eloped o he Euclidean (weigh ed and/o unweigh ed)
minmax p oblem like Elzinga and Hea n [8], Cha alambous [9], Hea n and Vijay [10]
o Welzl [11]. The algo i hm p oposed below ollows he gene al ideas o Elzinga and
Hea n [8]. Below we gi e a p ocedu al desc ip ion ollowing he gene al lines used
in [1]. No e ha i explici ly implemen s he idea o wo s poin selec ion a each
s ep as sugges ed by Elzinga and Hea n [8] and ad oca ed by many la e au ho s: his
ule is o pa icula in e es he e in o de o educe he numbe o subp oblems o be
sol ed.
(a) Dumb hun e (b) Sma hun e
Fig. 3 Two-p ey op imal solu ions
Algo i hm A1 (Gene al Algo i hm)
S ep 0 Ini ialize. Pick any wo-p ey se A={Ai,Aj}and de e mine X(Ai,Aj)and
F(Ai,Aj). Handle he wo-p ey se A.
S ep 1 Handle Two-P ey Se . De e mine k=i,j maximizing k(X(Ai,Aj)).
S ep 1a I k(X(Ai,Aj)) ≤F(Ai,Aj), hen X(Ai,Aj)is he op imal solu ion o
(PA). S op.
S ep 1b O he wise, add Ak o Aand p oceed o handle his h ee-p ey se (S ep 2
below).
S ep 2 Handle Th ee-P ey Se .
S ep 2a De e mine X(Ai,Ak)and F(Ai,Ak).I j(X(Ai,Ak)) ≤F(Ai,Ak)d op
Aj om Aand p oceed o handle his wo-p ey se .
O he wise, de e mine X(Aj,Ak)and F(Aj,Ak).I i(X(Aj,Ak)) ≤
F(A
j,Ak),d opAi om Aand p oceed o handle his wo-p ey se .
S ep 2b O he wise, de e mine X(Ai,Aj,Ak)and F(Ai,Aj,Ak)and he m=
i,j,k maximizing m(X(Ai,Aj,Ak)).
–I m(X(Ai,Aj,Ak)) ≤F(Ai,Aj,Ak), hen X(Ai,Aj,Ak)is he op i-
mal solu ion o (PA). S op.
– O he wise, de e mine F(Ai,Ak,Am)and F(Aj,Ak,Am). In case
F(Ai,Ak,Am)≤F(Aj,Ak,Am), eplace Ajby Amin A, o he wise
eplace Aiby Amin A. In any case, p oceed by handling his new
h ee-p ey se .
Using P oposi ions 3.2 and 3.4 i is easy o see ha he consecu i e calcula ed
unc ion alues F(Ai,Ak)and F(Ai,Aj,Ak)s ic ly inc ease a each s ep. So his
algo i hm canno cycle and, since he e a e a ini e numbe o wo-p ey and h ee-p ey
subse s o A, i will s op. By P oposi ion 3.1 he alue and solu ion ob ained a ha
poin is he op imal cen al hun e posi ion sough .
3.2 Easily Sol able Pa icula Case: Homogenous P ey
When all p ey mo e in exac ly he same way, as gi en by uni -mo emen ec o
pi=p, he p oblem is simpli ied conside ably, because all sys ems o equa ions o
be sol ed ha e analy ic solu ions. Howe e , i is much easie o use he ollowing
geome ic a gumen s.
Since all balls o each ime o cap u e a e hen simila ellipses, he minimax
p oblem is equi alen o co e ing he se Ao ini ial posi ions o p ey by means o
he enclosing ellipse wi h minimal a ea, and hen he co esponding hun e posi ion
a i s ocal poin mus be de e mined (compa e wi h [12]).
Sma Hun e Fo a sma hun e all he isoch one ellipses a e al eady ci cles. So
we ob ain he ollowing algo i hm.
Algo i hm A2 (Homogenous P ey, Sma Hun e )
S ep 1 Cons uc he smalles adius ci cle co e ing all p ey s a ing posi ions. Call
i s adius and midpoin M.
S ep 2 The minimax cap u e ime is hen gi en by T= /β.
S ep 3 The cen al hun e ’s posi ion hen lies a poin M+Tp.
Dumb Hun e Fo a dumb hun e all balls will be ellipses wi h long axis pa allel o
p, and a same shape, gi en by a long axis β/λ imes longe han i s sho axis (he e
λ2=β2−p2, as be o e). Fo simplici y, we desc ibe wha ollows in he coo dina e
sys em wi h second axis opposi e o p. Scaling he e ical coo dina e down o make
he axes o equal leng h by di iding by his ac o β/λ, ans o ms hese ellipses all o
ci cles. The e o e he p oblem may be educed o a smalles co e ing ci cle p oblem,
yielding he ollowing algo i hm.
Algo i hm A3 (Homogenous P ey, Dumb Hun e )
S ep 1 Rescale he e ical axis by mul iplying all e ical coo dina es o all p ey
poin s by λ/β. This s ep p oduces he new poin s Bi.
S ep 2 Find he smalles ci cle enclosing all Bi. Call i s cen e QBand i s adius B.
S ep 3 Scale back he e ical coo dina e o poin QBby mul iplying by β/λ.This
yields he symme y cen e QAo he smalles co ec ly shaped ellipse E
con aining he o iginal p ey poin s Ai.
S ep 4 I s sho axis hal -leng h equals Band co esponds o λτ. So he minimax
cap u e ime is ound as τ= B/λ.
S ep 5 The lowe ocus poin X∗o he ellipse Eis hen ound a dis ance pτ
below QAand co esponds o he op imal loca ion o he cen al hun e .
Figu e 4illus a es his simpli ied p ocedu e. In Fig. 4a se en een p ey wi h
p=(0,−1)a e shown. The cen al hun e has speed β=1.5. Figu e 4bshows he
poin s a e scaling and hei smalles co e ing ci cle. A e scaling back we ob ain
he smalles co e ing ellipse in Fig. 4c. I s lowe ocus gi es he cen al hun e posi-
ion.