Compu a ional Geome y 44 (2011) 135–147
Con en s lis s a ailable a ScienceDi ec
Compu a ional Geome y: Theo y and
Applica ions
www.else ie .com/loca e/comgeo
Fi ing a wo-join o hogonal chain o a poin se
J.M. Díaz-Báñez a,∗,1,M.A.López
b,M.Mo a
c,2, C. Sea a c,2, I. Ven u a a,1
aDepa amen o de Ma emá ica Aplicada II, Uni e sidad de Se illa, Spain
bDepa men o Ma hema ics, Uni e si y o Den e , 2360 Sou h Gaylo d S ee , Den e , CO 80208, USA
cDepa amen de Ma emà ica Aplicada II, Uni e si a Poli ècnica de Ca alunya, Spain
a icle in o abs ac
A icle his o y:
Recei ed 31 July 2009
Accep ed 28 July 2010
A ailable online 3 Augus 2010
Communica ed by J. Mi chell
Keywo ds:
Polygonal app oxima ion
Combina o ial op imiza ion
Cu e fi ing
Algo i hms
We s udy he p oblem o fi ing a wo-join o hogonal polygonal chain o a se So n
poin s in he plane, whe e he objec i e unc ion is o minimize he maximum o hogonal
dis ance om S o he chain. We show ha his p oblem can be sol ed in Θ(n) ime i he
o ien a ion o he chain is fixed, and in Θ(nlogn) ime when he o ien a ion is no a p io i
known. Mo eo e , ou algo i hm can be used o main ain he ec ilinea con ex hull o S
while o a ing he coo dina e sys em in O(nlogn) ime and O(n)space, imp o ing on a
ecen esul (Bae e al., 2009 [4]). We also conside some a ia ions o he p oblem in
h ee-dimensions whe e a polygonal chain is in e p e ed as a configu a ion o o hogonal
planes. In his case we ob ain O(n),O(nlogn),andO(n2) ime algo i hms depending on
which plane o ien a ions a e fixed.
©2010 Else ie B.V. All igh s ese ed.
1. In oduc ion and defini ions
Fi ing a cu e o a ce ain ype o a gi en poin se in he plane is a undamen al p oblem wi h applica ions in fields as
di e se as s a is ics, compu e g aphics, and a ificial in elligence. A special case o his p oblem is he so-called polygonal
app oxima ion p oblem o polygonal fi ing p oblem, whe e a polygonal chain wi h kco ne s o join s is fi ed o a da a se so
as o minimize he app oxima ion e o acco ding o some ag eed upon me ic. This p oblem is closely ela ed o ha o
app oxima ing a piecewise-linea cu e wi h nedges by one wi h ewe edges, excep ha he inpu is now also a chain.
Applica ions o his p oblem a ise in ca og aphy, pa e n ecogni ion, and g aphic design [5,9,25], and has ecei ed much
a en ion in compu a ional geome y [1,6,16,20,27].
In he Min–Max p oblem a polygonal chain wi h kjoin s is fi ed o a da a se wi h he goal o minimizing he maximum
e ical dis ance om he inpu poin s o he chain. This p oblem was fi s posed by Hakimi and Schmeichel [17] and
sol ed in O(n2logn) ime. The complexi y has since been imp o ed, fi s by Wang e al. [29] o O(n2) ime and hen by
Good ich [14] o O(nlogn) ime.
We conside he case in which he app oxima ing cu e is an o hogonal polygonal chain, i.e., a chain o consecu i e o -
hogonal line segmen s whe e he ex eme segmen s a e hal -lines wi h he same slope, he slope o he o hogonal polygonal
chain. The case in which his slope is gi en was fi s sol ed by Díaz-Báñez and Mesa [11] in O(n2logn) ime, and sub-
sequen ly imp o ed by Wang [28] o O(n2) ime, and by López and Mays e [24] o min{n2,nk logn} ime. Ve y ecen ly,
Fou nie and Vigne on [13] gi e an O(n) ime algo i hm i he poin s a e so ed by hei x-coo dina es, and an O(nlogn)
*Co esponding au ho .
E-mail add esses: [email p o ec ed] (J.M. Díaz-Báñez), [email p o ec ed] (M.A. López), [email p o ec ed] (M. Mo a), ca [email p o ec ed] (C. Sea a),
i [email p o ec ed] (I. Ven u a).
1Pa ially suppo ed by g an MTM2009-08625.
2Suppo ed by p ojec s MTM2009-07242 and Gen. Ca . DGR2009GR1040.
0925-7721/$ – see on ma e ©2010 Else ie B.V. All igh s ese ed.
doi:10.1016/j.comgeo.2010.07.005
136 J.M. Díaz-Báñez e al. / Compu a ional Geome y 44 (2011) 135–147
Fig. 1. A 6-o hogonal polygonal chain di iding he plane in o 6 s ips.
ime algo i hm o he unso ed case. These au ho s gi e an Ω(nlogk)lowe bound o he decision p oblem and hus p o e
he op imali y o hei algo i hm o he unso ed case when k=Θ(n).
Le S={p1,...,pn}be a se o npoin s in he plane in gene al posi ion, i.e., no h ee poin s on a line. When k⩾1 and
0◦⩽θ<180◦,ak-o hogonal polygonal chain wi h o ien a ion θ,Ok,θ , is a chain o 2k−1 consecu i e o hogonal segmen s
such ha he ex eme segmen s a e in ac hal -lines wi h slope an(θ).Thus,Ok,θ consis s o ksegmen s wi h slope an(θ)
and k−1segmen swi hslope an(θ +90◦)(Fig. 1). Clea ly, Ok,θ is always mono one wi h espec o i s o ien a ion.
We deal wi h he p oblem o fi ing a k-o hogonal polygonal chain Ok,θ o he se S. Fi ing Ok,θ o Smeans o loca e
θ-o ien ed segmen s si(θ),i=1,...,k, acco ding o a gi en op imiza ion c i e ion. We conside he Min–Max c i e ion,
illus a ed in Fig. 1 and defined as ollows. Le li(θ) be helinepassing h oughpi∈Swi h o ien a ion θ+90◦. The fi ing
dis ance be ween piand Ok,θ ,deno edbyd (pi,Ok,θ ),isgi enby
d (pi,Ok,θ )=min
p∈li(θ)∩Ok,θ
d(pi,p).
No ice ha d is no he Euclidean dis ance be ween he poin piand he polygonal chain. Howe e , we can assume ha
his dis ance is he Euclidean dis ance be ween piand a poin on a segmen wi h o ien a ion θin Ok,θ .Thee o ole ance
o Ok,θ wi h espec o S,deno edbyμ(Ok,θ ,S), is he maximum fi ing dis ance be ween he poin s o Sand Ok,θ , i.e.,
μ(Ok,θ ,S)=max
pi∈Sd (pi,Ok,θ ).
Defini ion 1. The k-fi ing p oblem o Swi h he Min–Max c i e ion consis s o finding an o hogonal polygonal chain Ok,θ
such ha i s e o ole ance μ(Ok,θ ,S)is minimized.
No ice ha i he o ien a ion o Ok,θ is fixed, o example θ=0◦, hen he k-fi ing p oblem consis s o finding an x-
mono one ec ilinea pa h o med by 2k−1 segmen s wi h minimum e o ole ance whe e he fi ing dis ance is jus he
e ical dis ance [11].
We ocus he e on he case whe e kis small, in ac k=2, and he poin s in Sa e no so ed. We s udy he 2-fi ing
p oblem o Swi h fixed o ien a ion ( he o ien ed 2-fi ing p oblem) and he p oblem o finding he bes o ien a ion o
fi ing a wo-join o hogonal polygonal chain o S( he un-o ien ed 2-fi ing p oblem). We also conside he ex ension o he
p oblem o h ee-dimensions whe e an o hogonal polygonal chain is a configu a ion o o hogonal planes. See Chen and
Wang [7,8] o ecen esul s on some a ian s o his p oblem including NP-ha dness esul s in h ee dimensions.
Ou line o he pape . In Sec ion 2 we s udy he o ien ed fi ing p oblem in he plane. In Sec ion 3 we s udy he un-o ien ed
2-fi ing p oblem in he plane. Finally, in Sec ion 4, we s udy he o ien ed 2-fi ing p oblem in h ee-dimensions.
2. The o ien ed fi ing p oblem
In his sec ion we conside he o ien ed k-fi ing p oblem o S, i.e., he case whe e he o ien a ion θo he k-o hogonal
chain ha fi s Sis fixed. Wi hou loss o gene ali y we assume ha θ=0◦. Thus, we a e looking o an x-mono one
ec ilinea pa h, Ok,0o Ok, consis ing o an al e na ing sequence o kho izon al and k−1 e ical segmen s wi h minimum
e o ole ance.
O en, he algo i hms p oposed in he li e a u e o hese kinds o fi ing p oblem assume ha he inpu poin s a e gi en
in so ed o de . Recen ly, Fou nie and Vigne on [13] gi e an O(nlogn) ime algo i hm o he o ien ed k-fi ing p oblem
when he poin s a e unso ed and p o e i s op imali y when k=Θ(n). The unning ime o he algo i hm om Lopez and
Mays e [24] is min{n2,nk logn}which is O(nlogn)when kis a cons an . Fo he so ed case, Fou nie and Vigne on [13]
J.M. Díaz-Báñez e al. / Compu a ional Geome y 44 (2011) 135–147 137
p esen an op imal O(n) ime algo i hm, and an Ω(nlogk) ime lowe bound o he decision p oblem o he unso ed
case. He e we conside he o ien ed k-fi ing p oblem o he case k=2 o he unso ed case.
Le S={p1,...,pn}, whe e pi=(xi,yi). We can compu e ymax =max{y1,...,yn}and ymin =min{y1,...,yn}in linea
ime. The o ien ed 1-fi ing p oblem hen is sol ed in O(n) ime by finding he ho izon al line y=(ymax +ymin)/2.
Le O2deno e an op imal solu ion o he o ien ed 2-fi ing p oblem o a se S.ThenO2consis s o wo ho izon al
hal -lines joined by a e ical segmen con ained in a e ical line ∗which pa i ions Sin o subse s S1and S2, namely he
poin s o S o he le and o he igh o ∗ espec i ely. Since ∗mus minimize he maximum e o ole ance o S1and
S2, he ollowing is appa en .
Lemma 1. Line ∗sepa a es he wo poin s in S wi h y-coo dina es ymin and ymax.
We ema k he e ha he e could be se e al poin s ha achie e ymax and ymin. All hese poin s can be compu ed in
linea ime. I is clea ha ∗has o sepa a e all he ymax poin s om all ymin poin s, since o he wise he solu ion is i ial.
This can be checked in linea ime. Thus, wi hou loss o gene ali y we can assume ha he ymax and ymin poin s a e
unique.
Linea ime algo i hm o o ien ed 2-fi ing. Any e ical line be ween wo poin s o Sinduces a candida e solu ion o he
o ien ed 2-fi ing p oblem whose cos is gi en by max{1,2}, whe e 1( esp. 2) deno es he ole ance o he subse o S
o he le ( esp. igh ) o . Ou algo i hm pe o ms a bina y sea ch based on he ollowing obse a ion:
Lemma 2. I is no op imal and 1<2( esp. 1>2) hen ∗lies o he igh ( esp. le )o .
We now ou line he algo i hm. Le deno e he e ical line h ough he median x-coo dina e o S. Pa i ion Sin o
subse s S1and S2 o he le and igh o , espec i ely. Compu e also he ole ances 1o S1and 2o S2, and s o e he
wo wi ness pai s o poin s esponsible o he ole ances. All his can be compu ed in O(n) ime [10]. I 1=2,s op he
algo i hm, as ∗=.I 1<2,inO(n/2) ime compu e he median o S2, ese as he e ical line a his median alue,
compu e he subse s S
2and S
2o he bipa i ion o S2p oduced by he new median, and compu e he ole ances 
2and

2o S
2and S
2. The nex mo e o (le o igh ) is de e mined based on he maximum o 
2and whe e is he e o
ole ance o all poin s o he le o , which can be ob ained in cons an ime by he wo wi ness poin s o 1and he wo
wi ness poin s o 
2. S o e he ole ance alues and he co esponding wi ness pai s as empo a y alues. Nex compu e
and upda e he ole ances once we know he nex mo e o .(I 1>2we p oceed in a symme ic way.) Compa e he
new ole ance alues and con inue ecu si ely ansla ing he line le o igh by compu ing he new median o a subse
wi h hal o he poin s and upda ing he new ole ance alues (le and igh ) om he old ones. A all imes we ha e wo
unions a he ex emes and an unknown zone in be ween con aining a mos wo s ips. The poin s in he zone a e known
bu , in gene al, a e no so ed.
Clea ly, he ime complexi y o he algo i hm is T(n)=T(n/2)+O(n)=O(n), using a linea ime median finding algo-
i hm [10]. By Lemma 1 he op imal line ∗will be loca ed be ween he wo poin s in Swi h y-coo dina es ymin and ymax.
The algo i hm s ops when ei he he ole ance alues 1and 2a e equal, o when ansla ing le and igh he bigge o
he wo ole ances swi ches sides and he unknown zone con ains no poin s. In his las case he solu ion will be he bes
o he wo. Since he algo i hm pe o ms a bina y sea ch on a unimodal unc ion, he me hod is co ec . No ice ha he
solu ion (posi ion o line o bipa i ion o S) is no unique because in an op imal solu ion some poin s can belong o S1
o S2wi hou changing he solu ion. No ice also ha ou algo i hm does no so he inpu poin s. We ha e he ollowing
esul .
Theo em 1. The o ien ed 2-fi ing p oblem can be sol ed in Θ(n) ime and space.
By he Ω(nlogk)lowe bound o he decisional o ien ed k-fi ing p oblem [13] in he unso ed case, i is clea ha i
k=ω(1) he e is no linea ime algo i hm. Thus, we aise he ollowing open ques ion mo e om a heo e ical han om a
p ac ical poin o iew.
Open p oblem 1. Fo which alues o k⩾3 does he e exis a linea ime algo i hm o he o ien ed k-fi ing p oblem?
2.1. An O(nlogn)- ime algo i hm
We now desc ibe an O(nlogn)- ime algo i hm o he o ien ed 2-fi ing p oblem whose in e es de i es no om i s
ime complexi y bu om he ac ha i will be used as a p ep ocessing s ep in he O(nlogn)- ime algo i hm o he
un-o ien ed 2-fi ing p oblem discussed in Sec ion 3. We s a by in oducing a basic ool.
In [21,26] he maxima p oblem o a poin se Sin he plane is conside ed. Conc e ely, gi en wo poin s pi,pj∈S, he
ollowing dominance ela ion is es ablished: pidomina es p j(pj≺pi),i xj⩽xiand y j⩽yi.The ela ion≺is a pa ial o de
in S.Apoin pi∈Sis called maximal i he e does no exis pj∈Ssuch ha i= jand pi≺pj. The maxima p oblem
138 J.M. Díaz-Báñez e al. / Compu a ional Geome y 44 (2011) 135–147
Fig. 2. A ec ilinea con ex hull o S o med by he maximal poin s o S.
consis s o finding all he maximal poin s o Sunde dominance. One can o mula e maxima p oblems o each quad an in
heplane.Wea ein e es edin hese o maximalpoin s o Swi h espec o he ou quad an s which o m he ec ilinea
con ex hull o S, also known as o hogonal con ex hull (Fig. 2). Each se o maximal poin s has a o al o de ing ha can be
s o ed in a heigh balanced sea ch ee [26].
Theo em 2. (See [21].) The maxima p oblem o S wi h espec o any o he ou quad an s can be sol ed op imally in Θ(nlogn) ime
and O(n)space.
O(nlogn)- ime algo i hm o o ien ed 2-fi ing
1. Le xmax,xmin,ymax, and ymin deno e he espec i e maximum and minimum o he x- and y-coo dina es o he poin s
in S. Wi hou loss o gene ali y assume xmin =ymin =0, xmax =c, and p1=(0,y1),pn=(c,yn),pi=(xi,ymax), and
pj=(xj,0)(Fig. 2), i.e., he ec angle wi h co ne s a (0,0)and (c,ymax)is he axis-pa allel bounding box o S.
Assume u he ha piis s ic ly o he le o pjand hus, by Lemma 1, he e ical line ∗lies be ween piand pj.(I
bo h ha e he same x-coo dina e he solu ion is i ial.)
By Theo em 2, in O(nlogn) ime we can compu e he ec ilinea con ex hull o S o med by he s ai cases s uc u e as
in Fig. 2. No ice ha s ai cases o opposi e quad an s can in e sec . Since piis o he le o pj, hen he hi d quad an
s ai case gi es he lowe poin on he le o ∗and he fi s quad an s ai case gi es he uppe poin on he igh o ∗.
2. By Lemma 1 he e ical line ∗:= (x=a)is be ween xiand xj. In o de o find i s co ec loca ion we do a bina y
sea ch o e he poin s in he s ai case s uc u e (fi s and hi d quad an s) in O(logn) ime ge ing he bes balance
be ween he e o ole ance on he le and on he igh sides o ∗, i.e.,
min
xi⩽a<xj
asubjec o max
xk⩽a{ymax −yk}⩾max
xm>aym(1)
o
max
xi<a⩽xj
asubjec o max
xk⩽a{ymax −yk}⩽max
xm>aym.(2)
Fo a leas one o Eqs. (1) o (2) he e exis s a solu ion. In case (1), he e o ole ance o Sis gi en by he poin s o
he le o ∗and, in case (2), by he poin s o he igh o ∗. In cons an ime compu e his e o ole ance gi en by
he di e ence be ween he bigge and smalle y-coo dina es o he poin s o he le o igh o line ∗.
I piis o he igh o pj, hen he algo i hm is simila wi h he ob ious changes: he second quad an s ai case gi es
he uppe poin o he le o ∗and he ou h quad an s ai case gi es he lowe poin o he igh o ∗.
No ice ha once he ec ilinea con ex hull o Sis ob ained, he o ien ed 2-fi ing p oblem can be sol ed in O(logn)
ime; his is a key componen o he algo i hm o Sec ion 3.
The abo e s ai case s uc u e can be used o design O(nlogn) ime algo i hms o he o ien ed 3-fi ing and 4-fi ing
p oblems as well. We conside 3-fi ing fi s . Le 1and 2deno e, espec i ely, he wo e ical lines con aining he wo
e ical segmen s o he solu ion. By Lemma 1, a leas one o 1and 2mus lie be ween ymax and ymin. Assume ha 1
is o he le o 2. The e a e a mos a linea numbe o loca ions o 1be ween wo consecu i e poin s o he s ai case
s uc u e. Fo each o hese loca ions a bina y sea ch o e he s ai case s uc u e o he igh o 1yields he op imal
loca ion o 2in O(logn) ime. De ails a e omi ed bu he bina y sea ch depends on whe he he loca ion o 2is ei he
be ween ymax and ymin o o he igh o ymin.
I is clea ha o he o ien ed 4-fi ing p oblem wi h h ee e ical lines 1,2, and 3, we can p oceed in a simila
way, fi s fixing he loca ion o he median line, say 2, in each o he linea numbe o possible loca ions, and hen finding
he loca ions o 1( o he le o 2) and 3( o he igh o 2) by bina y sea ch on he s ai case s uc u e.
As a consequence o he discussion abo e, bo h he o ien ed 3- and 4-fi ing p oblems can be sol ed in O(nlogn) ime
and O(n)space. The same esul bu using di e en echniques can be achie ed by he p oposals in [13,15,24].
J.M. Díaz-Báñez e al. / Compu a ional Geome y 44 (2011) 135–147 139
Fig. 3. Un-o ien ed Θ-maximum wi h espec o S.
3. The un-o ien ed 2-fi ing p oblem
In his sec ion we conside he p oblem o fi ing Susing an un-o ien ed 2-o hogonal polygonal chain O2,θ wi h ee
o ien a ion θ. No ice ha he un-o ien ed 1-fi ing p oblem o Sis equi alen o he p oblem o compu ing he wid h o S.
I we know he con ex hull o S, his p oblem can be sol ed in O(n) ime using o a ing calipe s [19]. O he wise, compu ing
he wid h o Shas an Ω(nlogn)- ime lowe bound [23]. The e o e he un-o ien ed 1-fi ing p oblem o Scan be sol ed
op imally in Θ(nlogn) ime.
Be o e s udying he un-o ien ed 2-fi ing p oblem we in oduce some no a ion and ools which will be use ul la e . We
s a by e iewing some defini ions and esul s om A is e al. [2] conce ning he compu a ion o un-o ien ed Θ-maximal
poin s o a plana poin se S.
Defini ion 2. (See [2].) A ay om a poin p∈Sis called a maximal ay i i passes h ough ano he poin q∈S. A cone is
defined by a poin pand wo ays Cand Demana ing om p.Apoin p∈Sis an un-o ien ed Θ-maximal wi h espec o
Si and only i he e exis wo maximal ays, Cand D, emana ing om pwi h an angle a leas Θbe ween hem so ha
he poin s o Slie ou side he (Θ-angle) cone defined by p,Cand D(Fig. 3(a)).
Theo em 3. (See [2].) All un-o ien ed Θ-maximal poin s o S o Θ⩾90◦can be compu ed in O(nlogn) ime and O(n)space, and
he algo i hm is op imal o fixed alues o Θ.
Fo Θ=90◦, he ou pu o he algo i hm o Theo em 3 is he lis o all he un-o ien ed 90◦-maximal poin s ha a e
apices o he wedges ha ha e bounding ays (c ossing an edge o CH(S)) wi h ape u e angle a leas 90◦.Fo e e ysuch
maximal poin p he ou pu also con ains he wo ays Lpand Rpbounding he wides emp y wedge on he le and on
he igh , espec i ely (Fig. 3(b)). Since he ape u e angle is a leas 90◦, hen each maximal poin pcan ha e a mos h ee
disjoin wedges. In cons an ime we can compu e he se o o ien a ions o he bisec o s o he (90◦-angle) cones wi h
apex pcon ained in he wedge defined by p,Lpand Rp: compu e he ay R
p( esp. L
p) ompwhich is pe pendicula
o Lp( esp. Rp), he bisec o s o he (90◦-angle) cones o med by Rp,p,L
pand by R
p,p,Lpa e he ex emes o he se
o o ien a ions o bisec o s (Fig. 3(b)). This se o o ien a ions can be ansla ed in o an o ien a ion in e al in S1(see
oo no e 3 o defini ion). Thus, each maximal poin p∈Scan ha e a mos h ee disjoin o ien a ion in e als in S1such
ha o each o ien a ion inside hese in e als he poin pis 90◦-maximal. No ice ha all he poin s in he bounda y o he
con ex hull o Sa e 90◦-maximal, and ha he o al numbe o o ien a ion in e als is linea .
Now we conside he un-o ien ed 2-fi ing p oblem. An op imal solu ion o his p oblem is gi en by an o hogonal
polygonal chain O2,θ wi h o ien a ion θsuch ha he e o ole ance o Swi h espec o O2,θ is minimum. Clea ly, his
is equi alen o he p oblem o de e mining a line θwi h slope an(90◦+θ) ha spli s Sin o subse s Slθand S θ, whe e
eu
lθand eb
lθ(eu
θand eb
θ) a e he poin s esponsible o he e o ole ance o Slθ(S θ) and such ha O2,θ minimizes he
e o ole ance o So e all alues o θ. Acco dingly, he e o ole ance is gi en by he ollowing o mula, whe e dθ(p,q)
deno es he dis ance be ween pa allel lines h ough pand qwi h o ien a ion θ.
μ(O2,θ ,S)=max
pi∈Sd(pi,O2,θ )=maxdθeu
lθ,eb
lθ,dθeu
θ,eb
θ.
Le ymin,θ and ymax,θ be he minimum and maximum y-coo dina es o he poin s in Swhen he coo dina e sys em is
o a ed by angle θ. The ollowing lemma is a gene aliza ion o Lemma 1.
3By Sd−1,d⩾2, we deno e he uni sphe e cen e ed a he o igin o he coo dina e sys em defined by he ips o he uni no mal ec o s o he
o ien a ions in Rd.

140 J.M. Díaz-Báñez e al. / Compu a ional Geome y 44 (2011) 135–147
Fig. 4. Sweeping he o ien a ion in e als o he 90◦-maximal poin s o S.
Lemma 3. Gi enano ien a ionθ, an op imal solu ion o he un-o ien ed 2-fi ing p oblem wi h o ien a ion θis defined by a line θ
passing h ough a poin o S which sepa a es he poin s o S wi h y-coo dina es ymin,θ and ymax,θ .
Desc ip ion o he un-o ien ed 2-fi ing algo i hm. The goal o ou app oach is o adap he O(nlogn)- ime algo i hm o he
o ien ed 2-fi ing p oblem desc ibed ea lie o accoun o con inuous changes in he o ien a ion θ, looking o he op imal
O2,θ chain in he p ocess. To do his we upda e he s ai case s uc u e as θ a ies and use Lemma 3 o look o an op imal
solu ion.
•Ini ializa ion: The s a ing si ua ion is he s ai case s uc u e o med by he ou se s o maximal poin s wi h espec o
he ou quad an s o he coo dina e sys em when θ=0◦. Analogously o [21,26], we use a heigh -balanced sea ch ee o
s o e and compu e each o he ou se s o maximal poin s wi h inse ions o dele ions in op imal O(nlogn) ime. Thus, we
compu e he s ai case s uc u e and i s co esponding op imal solu ion in O(nlogn) ime as we did o he o ien ed case.
•Upda e as θsweeps o e [0◦,90◦]: As we o a e he coo dina e sys em acco ding o he o ien a ion θin disc e e s eps
om θ=0◦ o θ=90◦ o compu e he un-o ien ed op imal solu ion, we iden i y he ou quad an s by hei o ien ed
bisec o s, i.e., by he o ien ed lines wi h slopes an(θ +45◦), an(θ +135◦), an(θ +225◦), and an(θ +315◦). The s ai cases
a e o med by he ou se s o maximal poin s in Swi h espec o he bisec o s o he cu en ou quad an s. No ice ha
o any θ, a poin is in he s ai cases i and only i i is a 90◦-maximal poin o some o he ou o ien a ions abo e, i.e.,
when a leas one o hese ou o ien a ions lies in he o ien a ion in e als defined by he poin .
The main idea o he algo i hm is o o a e he coo dina e sys em by θ, and upda e he s ai case s uc u e by inse ing
o dele ing poin s o each o he s ai cases as he o ien a ion θchanges. To do his we main ain ou o de ed lis s o he
cu en un-o ien ed 90◦-maximal poin s o Swi h espec o he bisec o s wi h o ien a ions θ+45◦,θ+135◦,θ+225◦,
and θ+315◦. The lis s co espond o he sequences o poin s in he ou s ai cases. Mo e p ecisely, he s ai case s uc u e
will be main ained wi h inse ions and dele ions o poin s induced by he changes in θ. No ice ha o any o ien a ion θ
he s ai case s uc u e has linea size, and upda ing a poin on i can be done in O(logn) ime as in he θ=0◦case [21,26].
As θchanges, he ou s ai cases can be modified because ei he a new poin o Sbecomes 90◦-maximal o some cu en
90◦-maximal poin o Shas o be dele ed. To de e mine he sequence o e en s, as θchanges, we use Theo em 3 o p e-
compu e in O(nlogn) ime he se o all un-o ien ed 90◦-maximal poin s o S oge he wi h hei espec i e o ien a ion
in e als in S1. These o ien a ion in e als a e he in e als whe e each poin is an un-o ien ed 90◦-maximal poin o S.
No ice ha a poin can be 90◦-maximal o a mos 3 (disjoin ) o ien a ion in e als and, consequen ly, he o al numbe o
changes in he s ai case s uc u e is linea .
To know in ad ance he sequences o e en s, i.e., he alues o θwhe e inse ions o dele ions o poin s occu , we
p oceed as ollows. Suppose ha we ha e compu ed he o ien a ion in e als o each poin pi∈S. Fig. 4 ep esen s he se
o hese o ien a ion in e als. A poin p∈Scan ha e a mos 3 disjoin o ien a ion in e als. We sweep he se o hese
in e als om 0◦ o 360◦, keeping ack, o each o ien a ion θ,o hese o 90
◦-maximal poin s o ha o ien a ion which
is he se o in e als in e sec ed by he sweep line.
Thus, he algo i hm pe o ms a sweep o hese in e als om θ=0◦ o θ=90◦by e ical lines co esponding o
o ien a ions θ,θ+90◦,θ+180◦, and θ+270◦, s opping a each e en (in e al endpoin ) and upda ing he s ai case
s uc u e. Since he poin s in Sa e in gene al posi ion, only a cons an numbe o upda es can occu a each e en . We
compu e he op imal solu ion o he s ai case s uc u e be ween wo consecu i e e en s by compu ing a line θwi h slope
an(θ +90◦), as explained below. In o de o co e all he o ien a ions o he plane, we also un he algo i hm as θchanges
om 90◦ o 180◦, which can be handled analogously.
Conside consecu i e e en s θ1and θ2. Lemma 3 implies ha o a fixed alue θ∈[θ1,θ
2], he line θ ha gi es he
op imal solu ion has o sepa a e he poin s wi h he cu en y-coo dina es ymin,θ and ymax,θ . Thus, he op imal solu ion is
de e mined by wo pai s o poin s, ei he (i) (ymax,θ ,eb
lθ)and (eu
θ,ymin,θ )i ymax,θ is o he le o ymin,θ , o (ii) (eu
lθ,ymin,θ )
and (ymax,θ ,eu
θ)i ymax,θ is o he igh o ymin,θ , gi ing he e o ole ance in Slθ, he le e o ole ance, and he e o
J.M. Díaz-Báñez e al. / Compu a ional Geome y 44 (2011) 135–147 141
Fig. 5. (a) and (b) Va ia ion o he le e o ole ance depending on whe he pkis on he igh o le side o θ,i, (c) and (d) a ia ion o he igh e o
ole ance depending on whe he pmison hele o igh sideo θ,j.
Fig. 6. Va ia ions o he le and igh e o ole ances.
ole ance in S θ, he igh e o ole ance, espec i ely. To compu e he op imal solu ion be ween wo consecu i e e en s we
use he ollowing lemma.
Lemma 4. Le [θ1,θ
2]be an o ien a ion in e al co esponding o consecu i e e en s. The op imal solu ion o he un-o ien ed 2-fi ing
p oblem in his in e al occu s a an endpoin , i.e., a θ1o θ2,o a ano ien a ionθ0∈[θ1,θ
2]whe e he le and igh e o ole ances
a e equal.
P oo . Le θ0∈[θ1,θ
2]be he o ien a ion o he op imal solu ion in [θ1,θ
2]. Assume ha he le and igh e o ole ances
o he op imal solu ion o θ0a egi enby hepoin pai s(pi,pk)and (pj,pm), espec i ely. Le piand pjbe he poin s
wi h maximum and minimum y-coo dina e, espec i ely, o any o ien a ion in [θ1,θ
2]. The iden i y o hese poin s does
no change in he in e al, as o he wise we would ge a new o ien a ion in e al. Assume ha piis o he le o pj.O he
cases can be handled analogously.
The le e o ole ance can be w i en as a unc ion w1(θ) =d(pi,pk)cos(θik −θ), whe e θik is he o ien a ion o he
line passing h ough piand pk, and θis he cu en o ien a ion in he o a ion p ocess. This unc ion is a con inuous and
unimodal unc ion o he angle θ. Thus, ei he w1(θ) always inc eases as in Fig. 5(a), o i always dec eases as in Fig. 5(b),
o he unique inc easing/dec easing change occu s i , du ing he o a ion, pkpasses om one side o he o he side o line
θ,iwi h o ien a ion θgoing h ough piwhich is a p edic able e en . An en i ely analogous si ua ion occu s wi h he igh
e o ole ance wi h he unc ion w2(θ) =d(pj,pm)cos(θ jm −θ) (Figs. 5(c) and 5(d)).
I bo h unc ions w1(θ) and w2(θ) inc ease, he op imal solu ion is ound a he endpoin θ1, as o he wise we can o-
a e clockwise, dec easing bo h e o ole ances in he p ocess (Fig. 6(a)). I bo h unc ions w1(θ) and w2(θ) dec ease, he
op imal solu ion is ound a he endpoin θ2as a coun e clockwise o a ion dec eases bo h e o ole ances (Fig. 6(c)). Anal-
ogous is he case when w1(θ) inc eases and w2(θ) dec eases, o ice e sa, bu bo h unc ions do no in e sec . O he wise,
he in e sec ion o bo h unc ions gi es he op imal solu ion in an o ien a ion θ0when he le and igh e o ole ances
a e equal (Fig. 6(b)). This can be de ec ed because he e is a change o he maximum e o ole ance om he igh e o
ole ance in θ1 o he le e o ole ance in θ2o ice e sa. 2
As a consequence o Lemma 4, he op imal solu ion o a (non-s a ing) in e al o ien a ion [θ1,θ
2]can be compu ed
in O(logn) ime. Summa izing: (1) he numbe o e en s o he s ai case s uc u e as θchanges om 0◦ o 90◦is linea ,
(2) any upda e can be done in O(logn) ime, (3) o a fixed alue o θan O(logn) ime bina y sea ch p oduces he op imal
loca ion o he line θ, i s co esponding e o ole ance, and allows us o main ain he minimum one. We conclude ha
he un-o ien ed 2-fi ing p oblem can be sol ed in O(nlogn) ime and O(n)space.
The un-o ien ed-2-fi ing-algo i hm. We assume ha o he cu en o ien a ion θ he poin wi h y-coo dina e ymax,θ is o
he le o he poin wi h y-coo dina e ymin,θ ; o he wise, we only upda e he changes in he s ai case s uc u e wi hou
compu ing he op imal solu ion. We epea he algo i hm o he al e na i e case.
1. Use he algo i hm om A is e al. [2] o compu e in O(nlogn) ime he lis o he un-o ien ed 90◦-maximal poin s
o Sand hei o ien a ion in e als in S1whe e each poin is un-o ien ed 90◦-maximal. So he a angemen o he
o ien a ion in e als acco ding o hei endpoin s in such a way ha when we sweep he a angemen we know which
90◦-maximal poin s a e ac i e in a cu en sweeping o ien a ion, and which is he nex incoming endpoin (Fig. 4).
142 J.M. Díaz-Báñez e al. / Compu a ional Geome y 44 (2011) 135–147
Fig. 7. Cons uc ion in he p oo o he lowe bound o he un-o ien ed 2-fi ing p oblem.
2. In O(nlogn) ime compu e he ho izon al/ e ical s ai case s uc u e o Sand he op imal solu ion as we did in he
o ien ed 2-fi ing p oblem. The s ai case s uc u e is o med by he 90◦-maximal poin s o Swi h o ien a ions 0◦+45◦,
90◦+45◦, 180◦+45◦, and 270◦+45◦.
3. Sweep he a angemen o he o ien a ion in e als wi h he ou e ical lines. Each ime ha we each an endpoin ,
ei he (1) a new un-o ien ed 90◦-maximal poin en e s he s ai case s uc u e, o (2) an ac i e un-o ien ed 90◦-maximal
poin is dele ed om he s ai cases. We upda e he changes in he s ai cases in O(logn) ime, including also he possible
changes o he poin s wi h minimum and maximum y-coo dina es o he cu en o ien a ion. Since we conside he
poin s in gene al posi ion, a mos wo aligned poin s a e upda ed a he same ime p oducing a cons an numbe o
changes. We use bina y sea ch o compu e he sepa a ing line o he new op imal solu ion in O(logn) ime, and s o e
and upda e he in o ma ion o he op imal solu ion.
No ice ha a poin en e s one o he s ai cases a mos once, so a poin is upda ed a cons an numbe imes and he
o e all unning ime o upda ing changes is O(nlogn) ime. The unning ime o he algo i hm is O(nlogn)and he space
is O(n)since he lis s and he a angemen o o ien a ion in e als ha e linea size.4
Nex , we show a educ ion o he un-o ien ed 2-fi ing p oblem om a MAX-GAP p oblem o poin s on he fi s quad-
an o he uni ci cle [23], es ablishing in he p ocess an Ω(nlogn)- ime lowe bound. We educe he MAX-GAP p oblem
o poin s on he fi s quad an o he uni ci cle cen e ed a he o igin o he coo dina es sys em o ou p oblem. This MAX-
GAP p oblem has an Ω(nlogn) ime lowe bound in he algeb aic decision ee model [23]. Le P={(x1,y1),...,(xn,yn)}
be he se o poin s o an ins ance o MAX-GAP. Conside a symme ic copy o poin s in he hi d quad an and new copies
o he o e all ci cle in o he posi ions as in Fig. 7. I is easy o see ha he op imal un-o ien ed 2-fi ing o hogonal chain
defines he maximum gap o Pand ice e sa. This cons uc ion can be gene alized o wo k wi h he un-o ien ed k-fi ing
p oblem, k⩾3, using k−1 copies o he ini ial ci cle wi h he cen e s loca ed wi h adequa e dis ances be ween hem.
Theo em 4. The un-o ien ed 2-fi ing p oblem can be sol ed in op imal Θ(nlogn) ime and O(n)space.
4. The o ien ed 2-fi ing p oblem in 3D
In his sec ion we conside he o ien ed 2-fi ing p oblem in h ee-dimensions whe e a polygonal chain is in e p e ed as
a configu a ion o wo pa allel hal -planes, joined wi h an o hogonal s ip. Fi s , we gi e a sho discussion o he 1-fi ing
p oblem.
To sol e he o ien ed 1-fi ing p oblem o Sin R3we p oceed acco ding o how much in o ma ion abou he solu ion
plane we ha e, dis inguishing be ween wo cases:
Case i:The o ien a ion o he solu ion plane is fixed. Assume ha he solu ion plane has no mal 
u=(0,0,1)∈S2.Wesol e
his p oblem in Θ(n) ime by compu ing he poin s wi h maximum and minimum z-coo dina es.
Case ii:The o ien a ion o he solu ion plane has one deg ee o eedom. Assume ha he solu ion plane has no mal 
uwhich is
o hogonal o 
=(0,1,0)∈S2. We sol e his p oblem by p ojec ing he poin s on o a plane wi h no mal 
and compu ing
he wid h o he con ex hull o he p ojec ed poin s wi h a o a ing calipe . The o al unning ime is Θ(nlogn).The
Ω(nlogn) ime lowe bound comes om he compu a ion o he wid h o a se o poin s in wo-dimensions.
The o ien ed 2-fi ing p oblem can be defined by h ee consecu i e o hogonal planes. We e e o he plane Πp oducing
he bipa i ion o Sas he sepa a ing plane and o he wo pa allel planes ha induce he e o ole ances on ei he side o Π
as he suppo ing planes. We dis inguish among h ee cases depending on how he o ien a ion o he solu ion is cons ained:
4No ice ha he algo i hm can main ain he ec ilinea con ex hull o Sdu ing he o a ion in O(nlogn) ime and O(n)space, imp o ing on a ecen
esul by Bae e al. [4] who p esen an O(n2) ime and O(n)space algo i hm o his p oblem. In hei pape , he au ho s de i e a space/ ime ade-o :
O(n3/2log7/3(n)) ime and O(n3/2logn)space a e also possible.
J.M. Díaz-Báñez e al. / Compu a ional Geome y 44 (2011) 135–147 143
Fig. 8. Sample configu a ion o case (2).
(1) he o ien a ions o bo h he sepa a ing plane and he pa allel suppo ing planes a e fixed; (2) he o ien a ion o he
sepa a ing plane is fixed; and (3) he o ien a ion o he pa allel suppo ing planes is fixed. Nex , we conside he h ee
cases.
Case (1): The o ien a ions o bo h he sepa a ing plane and he pa allel suppo ing planes a e fixed. Assume ha he sepa a ing
plane has no mal 
u1=(0,1,0)and ha he pa allel suppo ing planes ha e no mal 
u2=(0,0,1). We educe he p oblem
o wo-dimensions as ollows. Le 
u3=
u1×
u2, whe e ×deno es he c oss p oduc . We p ojec he poin s in Son o a plane
wi h no mal 
u3=(1,0,0)and sol e i op imally in O(n) ime using he algo i hm o Sec ion 2.
Theo em 5. The o ien ed 2-fi ing p oblem in 3D can be sol ed in Θ(n) ime and space i he o ien a ions o bo h he sepa a ing plane
and he pa allel suppo ed planes a e fixed.
Case (2): The o ien a ion o he sepa a ing plane is fixed. Assume ha he sepa a ing plane has no mal 
u=(0,1,0).In
O(nlogn) ime, so he poin s in Salong 
u, i.e., by 
u·piwhe e ·deno es he do p oduc (e.g., by y-coo dina e). Le
p1,...,pnbe he sequence o he poin s o Swi h his o de . Acco ding o his o de , le Sl,i={p1,...,pi}and S ,i=
{pi+1,...,pn},i=1,...,n−1, be he bipa i ion o Sgi en by he sepa a ing plane passing h ough pi. In o de o compu e
he pa allel suppo ing planes o Sl,iand S ,i o de e mining which bipa i ion o Sgi es he op imal solu ion, we p ojec
he poin s o Sl,iand he poin s o S ,ion o wo planes pa allel o he sepa a ing plane. We wo k wi h he con ex hulls o
he p ojec ed poin s. Le S
l,iand S
,ibe he p ojec ed poin s o Sl,iand S ,i espec i ely, and le CH(S
l,i)and CH(S
,i)be
hei espec i e con ex hulls (Fig. 8).
To find he op imal 2-fi ing solu ion o a bipa i ion Sl,iand S ,i, we use wo clockwise o a ing calipe s which o a e
simul aneously o e CH(S
l,i)and CH(S
,i)in disc e e s eps. Each s ep is defined by he minimum o a ing angle o he wo
calipe s on an ipodal pai s. Suppose ha a some s ep, he o a ing calipe o e CH(S
l,i)( esp. CH(S
,i)) has an ipodal poin s
q1and q2( esp. q3and q4). Le α1( esp. α2) be he angle o o a ion wi h espec o he pa allel suppo ing lines passing
h ough q1and q2( esp. q3and q4). Le w1( esp. w2) be he wid h unc ion o CH(S
l,i)( esp. CH(S
,i))in he o a ion
in e al and d1=d(q1,q2)( esp. d2=d(q3,q4)). The con inuous and mono one wid h unc ion w1( esp. w2) depends on
d1( esp. d2) and cos(α1)( esp. cos(α2)). The minimum o he maximum o he wo wid h alues is a minimum o he
uppe en elope o he wo unc ions w1and w2. We compu e he minimum o he uppe en elope in he o a ion in e al
and he co esponding wid h (a mos a linea numbe o in e als) and main ain he bes solu ion.
Algo i hm o case (2).We can upda e he con ex hulls CH(S
l,i)and CH(S
,i)in O(logn) ime when a poin pichanges om
S ,i−1 o Sl,i[3]. We use linea ime o he ask o compu ing an op imal solu ion o each bipa i ion and upda e he
op imal. Thus, he o al unning ime is O(n2).
Nex , we show a educ ion om he MAX-GAP p oblem o poin s on he fi s quad an o he uni ci cle [23] o case (2)
o he o ien ed 2-fi ing p oblem.
Since MAX-GAP has an Ω(nlogn) ime lowe bound in he algeb aic decision ee model [23], his es ablishes he same
bound o ou p oblem. The educ ion is as ollows. Le P={p1,...,pn}be an ins ance o he MAX-GAP p oblem o
poin s on he fi s quad an o he uni ci cle Cin he XZ-plane cen e ed a he o igin o he coo dina e sys em, whe e
pi=(xi,0,zi), o i=1,...,n.InO(n) ime compu e he fi s , he second, he penul ima e, and he las poin s o Pin
he x-coo dina e o de ; wi hou loss o gene ali y, assume ha p1,p2,pn−1, and pna e hese poin s o P, espec i ely.
Fu he mo e, we can assume ha p1=(0,0,1). Make h ee copies o Pon Cby o a ing clockwise he poin s o Pby
π/2, π, and 3π/2, espec i ely. Le P1={p1
1,...,p1
n},P2={p2
1,...,p2
n},andP3={p3
1,...,p3
n}be he poin s o he h ee
copies. No ice ha he o a ion o each poin can be done in cons an ime. We pu a poin aa he in e sec ion poin o
he line passing h ough he poin s pn−1and pn, and he line passing h ough he poin s p1
1and p1
2.Wepu apoin b
a he in e sec ion poin o he line passing h ough he poin s p1
n−1and p1
n, and he line passing h ough he poin s p2
1
and p2
2.Wepu apoin ca he in e sec ion poin o he line passing h ough he poin s p2
n−1and p2
n, and he line passing
h ough he poin s p3
1and p3
2. Finally, we pu a poin da he in e sec ion poin o he line passing h ough he poin s
p3
n−1and p3
n, and he line passing h ough he poin s p1and p2.Nowle S1be he se o hese 4n+4poin sinC, i.e.,
S1=P∪P1∪P2∪P3∪{a,b,c,d}.The ou poin s{a,b,c,d} o ce ha he minimum wid h o S1(o equi alen ly he
MAX-GAP o P) is defined by wo consecu i e poin s o Pand he co esponding o a ed poin s in P2(simila ly o P1