Minimizing he e o o linea sepa a o s on linea ly insepa able da a
Bo is A ono a, Delia Ga ijo b, Yu ai Núñez-Rod íguez c, Da id Rappapo d, Ca los Sea a e,∗,
Jo ge U u ia
a Depa men o Compu e Science and Enginee ing, Poly echnic Ins i u e o NYU, USA
b Dep . de Ma emá ica Aplicada I, Uni e sidad de Se illa, Spain
c Lakes En i onmen al So wa e, 60 Ba hu s D . Uni 6, Wa e loo, ON, N2V2A9, Canada
d School o Compu ing, Queen’s Uni e si y, Kings on, Canada
e Dep . de Ma emà ica Aplicada II, Uni e si a Poli ècnica de Ca alunya, Spain
Ins i u o de Ma emá icas, Uni e sidad Nacional Au ónoma de México, Mexico
Keywo ds: Linea ly
insepa able
Classi ie s
E o minimize s
abs ac
Gi en linea ly insepa able se s Ro ed poin s and Bo blue poin s, we conside se e al
measu es o how a hey a e om being sepa able. In ui i ely, gi en a po en ial sepa a o
(‘‘classi ie ’’), we measu e i s quali y (‘‘e o ’’) acco ding o how much wo k i would ake
o mo e he misclassi ied poin s ac oss he classi ie o yield sepa a ed se s. We conside
se e al measu es o wo k and p o ide algo i hms o ind linea classi ie s ha minimize
he e o unde hese di e en measu es.
1. In oduc ion
Cu en massi e da a collec ion me hods ha e p o ided esea che s wi h a weal h o da a, oge he wi h he challenge
o making sense o i . Pa i ioning o clus e ing da a as a me hod o da a analysis is an impo an ool in p o iding meaning
o la ge amoun s o da a. Pe o ming his ype o analysis is mul i ace ed, and can ange om applica ions in geog aphy and
land use, pa e n ecogni ion, medical heal h s udies, economics, de ec ing simila i y be ween gen es o music, and da a
mining o assis in a ge ed ma ke ing s a egies, o name bu a ew.
Pa i ioning da a using sepa a o s o classi ie s o pe o m clus e analysis on aining se s is a s anda d echnique, o
example i is used in pa e n ecogni ion applica ions [22]. Thus he p oblem o de e mining i wo disjoin poin se s a e
sepa able has been widely s udied in he li e a u e. See o ins ance Megiddo [35] o he seminal ixed dimension linea
p og amming me hod o linea sepa abili y. Elizondo [24] su eys a a ie y o echniques and discusses he applica ion
o linea sepa abili y o machine lea ning. O’Rou ke e al. [36] and Boissonna e al. [7] conside algo i hms o ci cula
sepa abili y, and Hu ado e al. [30] and A kin e al. [3] examine a a ie y o sepa abili y c i e ia.
In some applica ions he aining da a may con ain some poin s ha ha e been misclassi ied esul ing in he si ua ion
whe e no na u al1pa i ion scheme classi ies he da a. In his case classi ica ion is a emp ed whe e some amoun o e o
is ole a ed. Wi hin ha con ex , A ono and Ha -Peled [4] s udied he ollowing p oblem: gi en a bicolo ed poin se , ind
a ball ha con ains he maximum numbe o ed poin s wi hou con aining any blue poin s. Co és e al. [18] add ess he
∗Co esponding au ho .
E-mail add esses: [email p o ec ed] (B. A ono ), [email p o ec ed] (D. Ga ijo), [email p o ec ed] (Y. Núñez-Rod íguez), [email p o ec ed]
(D. Rappapo ), [email p o ec ed] (C. Sea a), [email p o ec ed] (J. U u ia).
1He e by a na u al pa i ion we mean a pa i ion gi en by a simple classi ie like disk, squa e, o a hal plane.
p oblem o inding wo boxes SRand SBsuch ha he numbe o ed and blue poin s in SRand SB espec i ely is maximized,
while igno ing he poin s in SR∩SB. Ma hema ical p og amming echniques ha e been used in he ope a ions esea ch
communi y o sol e simila p oblems [5,19,31,40].
In his pape we p esen algo i hms ha minimize he e o when using a linea sepa a o . Gi en wo linea ly insepa able
poin se s we a emp o ind a hype plane which spli s he union o he se s in o disjoin subse s in such a way ha some
e o unc ions a e minimized. We call such hype planes op imal classi ie s. The no ion o op imali y is le in en ionally in o -
mal as he p ecise p ope ies ha should be op imized a e applica ion dependen . We will examine se e al di e en c i e ia
o choosing an op imal classi ie . We will p oceed on he assump ion ha he dimension do he p oblem is a small cons an
and be mos ly conce ned abou he asymp o ic dependence o he speed o ou algo i hms on he size no he poin se s.
Le Rbe a se o ed poin s and Ba se o bblue poin s in Rd. Le n:= +bbe he o al numbe o poin s and assume
ha he poin se s a e disjoin and in gene al posi ion, ha is, no d+1 o he poin s lie in he same hype plane in Rd. We say
ha Rand Ba e (linea ly) sepa able i he e exis s a (linea ) sepa a o , which is an o ien ed hype plane so ha he ed poin s
lie o i s le and he blue poin s lie o i s igh . (Fo mally, each side o he hype plane is a closed hal space delimi ed by i ,
so poin s on he hype plane a e conside ed o lie on bo h sides simul aneously.) I he e is no sepa a o o Rand B, hen we
say ha he se s a e insepa able.
Le P= {p1, . . . , pn} := R∪B. Le hbe a hype plane x1a1+ ··· + xdad=a0, and le h−be he hal plane con aining
he poin s (x1,...,xd)such ha x1a1+ ··· + xdad≤a0, and h+be he hal space ha con ains he poin s sa is ying
x1a1+ ··· + xdad≥a0. We will say ha h−lies o he le o h, while h+lies o he igh o h. I hwe e a sepa a o o
P, we would ha e R⊂h−and B⊂h+. As i is no , i misclassi ies he ed poin s R(h):= R h−and he blue poin s
B(h):= B h+. We use Ξ=Ξ(h):= R(h)∪B(h) o deno e he se o poin s misclassi ied by h. We use s(h) o ep esen
he quali y o has a classi ie ; i depends on hand Ξ=Ξ(h). Ou goal is o ind a hype plane ha minimizes he cos unde
one o he ollowing ou measu es, whe e d(·,·)deno es he Euclidean dis ance be ween poin s in Rdand d(p,X)deno es
he Euclidean dis ance om a poin p o a se X:
MinMax: Maximum Euclidean dis ance om h o a poin in Ξ, i.e.,
s∞(h):= max
p∈Ξ(h)
d(p,h)=max{max
p∈Rd(p,h−), max
p∈Bd(p,h+)}.
MinSum: Sum o he Euclidean dis ances om h o poin s in Ξ, i.e.,
s1(h):= 
p∈Ξ(h)
d(p,h)=
p∈R
d(p,h−)+
p∈B
d(p,h+).
MinSum2: Sum o squa es o he Euclidean dis ances om h o poin s in Ξ, i.e.,
s2(h):= 
p∈Ξ(h)
d2(p,h)=
p∈R
d2(p,h−)+
p∈B
d2(p,h+).
MinMis: Jus he ca dinali y o Ξ, i.e., he numbe o misclassi ied poin s,
s0(h)= |R h−|+|B h+|.
We a e in e es ed in inding an op imal classi ie , which we de ine o be a hal space hOp minimizing he quan i y s(h);
i is no always unique. No ice ha since d(p,h±)is a con inuous unc ion o h, so a e s∞(h), s1(h), and s2(h).
We will use a s anda d duali y ans o m. I maps a poin p∈Rd o a non- e ical hype plane p∗⊂Rd, and ice e sa,
ha is, i maps a non- e ical hype plane h o he poin h∗such wi h (h∗)∗=hand (p∗)∗=p; mo eo e pis abo e hi and
only i h∗is abo e p∗.
Ou line o he pape . We p esen algo i hms o ind op imal classi ie s using he ou measu es desc ibed abo e. In
Sec ion 2we p esen solu ions o he one-dimensional p oblem, as his will p o ide some illumina ing in ui ion o
p oceeding o p oblems o highe dimension. We de o e Sec ion 3 o desc ibing some c ucial obse a ions ha ela e he
sepa abili y p oblems in one dimension o hose in highe dimensions. In Sec ions 4–7 we s udy each o he measu es
in a bi a y dimension. The algo i hms a e based on exis ing echniques om he compu a ional geome y li e a u e. We
show ha inding an op imal classi ie using he MinMax measu e is equi alen o de e mining he pene a ion dep h
be ween wo con ex polyhed a, and can he e o e be sol ed using exis ing me hods. Fo op imizing classi ie s using he
MinSum,MinSum2, and MinMis measu es we use duali y and le els in a angemen s o sys ema ically enume a e candida e
solu ions. The compu a ional complexi ies o he algo i hms a e summa ized in he ollowing Table 1.
2. One dimension
We i s conside he one-dimensional case o ou se o p oblems. The inpu se s Rand Blie on he eal line. Then a
classi ie is a poin h. We will assume ha h+is he hal -line [h,+∞)and h−is he hal -line (−∞,h]; he e e se case is
handled by a symme ic a gumen . Fo simplici y, we will omi he symme ic cases in he s a emen o ou lemmas. We
seek he poin (o poin s) hOp minimizing s(h).
No ice ha d(p,h+)is con ex as a unc ion o h, as is i s squa e ((p−h)2 o h≥p, and 0 o h<p); he same holds o
d(p,h−). Since he i s h ee e o measu es a e de ined as he maximum, sum, and he sum o squa es o hese unc ions
Table 1
Summa y o he ime complexi ies.
Dimension MinMax MinSum MinSum2MinMis
d=1Θ(n)Θ(n)Θ(n)Θ(nlog n)
d=2Θ(nlog n)O(n4/3log1+ϵn)O(n2)O(n2)
O(n4/3)*
d=3O(n2)O(n5/2log6n)*O(n3)O(n3)
d>4O(n⌈d/2⌉)O(nd)O(nd)O(nd)
*Randomized expec ed ime.
o e all p∈P, in each case s(h)is a con ex unc ion o h. The e o e i a ains i s minimum a a unique closed in e al. In
ac , only s1may a ain i s minimum on a non-ze o-leng h in e al.
2.1. MinMax
Recall ha s∞(h)is he poin wise maximum o piecewise-linea con ex unc ions and hus piecewise-linea and con ex.
I is easily checked ha i is nowhe e cons an , since Rand Ba e insepa able, and hence has a unique minimum.
Obse a ion 1. The op imal MinMax classi ie hOp is he mean o he le mos blue poin and he igh mos ed poin and can
be compu ed in Θ(n) ime.
Indeed, by de ini ion, he cos s∞(h)is ealized by he misclassi ied poin s u hes om hand hus can be educed by a
small change o hin he app op ia e di ec ion, unless i is midway be ween ex eme misclassi ied poin s, as claimed.
2.2. MinSum
Recall ha s(h):= s1(h)is a sum o npiecewise-linea con ex unc ions and hus piecewise-linea and con ex. The e o e
i achie es i s minimum a a unique poin o a closed in e al, whe e i is cons an . Speci ically, be ween consecu i e poin s
o P,s(h)=p∈R(h)d(p,h−)+p∈B(h)d(p,h+)=p∈R(h)(p−h)+p∈B(h)(h−p)is a linea unc ion wi h slope
−|R(h)|+|B(h)|. I has b eakpoin s a poin s o P. The e o e, we ha e
Theo em 2. In one dimension, op imal MinSum is achie ed a any poin wi h he p ope y ha he numbe o ed and blue
misclassi ied poin s is equal. Mo e p ecisely, hOp lies in he closed in e al be ween he h and ( +1)s poin o P, coun ing
om he le , o be ween he b h and (b+1)s poin , coun ing om he igh . This in e al can be compu ed in op imal linea
ime.2
P oo . The i s s a emen ollows om p e ious discussion, while he second can be deduced by coun ing he numbe o
poin s o he le o hOp , when i does no coincide wi h a poin o P: since he numbe o ed poin s o he igh o hOp is
equal o he numbe o blue poin s o he le o i , he o al numbe o poin s o i s le is p ecisely , as claimed. Since he
minimum mus be achie ed on a closed in e al, his mus be he in e al delimi ed by he h and ( +1)s poin s om
he le ; such an in e al always exis s, as −|R(h)|+|B(h)|s a s a − , ends a band sh inks by exac ly one e e y ime h
c osses a poin o P. Since he o al numbe o poin s is n= +b, he claim ollows. The desi ed in e al can be compu ed
by using a linea - ime selec algo i hm [6]. 
2.3. MinSum2
Uniqueness o he op imum ollows om ou p e ious obse a ions. Indeed, d2(p,h+)and d2(p,h−)a e bo h con ex,
con inuous, e e ywhe e di e en iable unc ions; each is composed o a quad a ic and s ic ly con ex po ion and an
iden ically ze o po ion. The sum o nsuch unc ions is con ex. Mo eo e , i s minimum can be a ained along a non-ze o-
leng h in e al only i all he cons i uen unc ions a e ze o wi hin i , which is no possible o insepa able poin se s.
To ind he unique minimum, conside a candida e sepa a o h. Then MinSum2e o is gi en by
s2(h)=
p∈R
d2(p,h−)+
p∈B
d2(p,h+)=
p∈R(h)
d2(p,h)+
p∈B(h)
d2(p,h)
=
p∈Ξ(h)
(p−h)2=h2·|Ξ(h)|−2h·
p∈Ξ(h)
p+
p∈Ξ(h)
p2,
which is a piecewise quad a ic unc ion. Pu Σ(h):= p∈Ξ(h)p. By p e ious discussion, s2(h)is s ic ly con ex and
di e en iable e e ywhe e, hence i s minimum alue mus occu in ha in e al be ween consecu i e poin s o Pwhe e
2A esul simila o Theo em 2 is p o ed by Simon [42] bu in he con ex o he suppo ec o machines and he algo i hmic lea ning heo y.
hOp := Σ(h)/|Ξ(h)|occu s wi hin he in e al; his alue has a geome ic in e p e a ion: hOp is he a i hme ic mean (i.e.,
he cen oid) o he misclassi ied poin s.
Thus i emains o explain how o ind his unique minimum. An O(nlog n)algo i hm is clea : a e so ing P, we compu e
|Ξ(−∞)|and Σ(−∞), and hen inc emen ally upda e hem, main aining Σ(h)and Ξ(h), and e alua ing Σ(h)/|Ξ(h)| o
e e y in e al be ween consecu i e poin s o P, un il we ind he unique in e al con aining he local (and, he e o e, global)
minimum. In ac , he op imum can be iden i ied in linea ime by a p une-and-sea ch p ocedu e; e e o algo i hm 1,
whe e Σ ep esen s he sum o he coo dina es o he poin s we know will be misclassi ied in he op imal solu ions and
N ep esen s he numbe o such poin s. I s co ec ness ollows om he con exi y o s2(h)and he abo e discussion. I s
unning ime is linea , as i obeys a ecu ence o he o m T(n)≤cn +T(n/2). Thus we ha e shown
Theo em 3. The one-dimensional MinSum2p oblem has a unique solu ion which can be ound in op imal linea ime.
Inpu : Insepa able se s Ro ed poin s and Bo blue poin s on a line, wi h a o al o npoin s.
Ou pu : The alue hOp a which he MinSum2e o measu e s2(h)is minimized.
Ini ializa ion: Σ←0; N←0;
epea
De e mine pand q, he poin s ha s addle he median ank in P;
ΣB← he sum o he coo dina es o he blue poin s o he le o pin P;
ΣR← he sum o he coo dina es o he ed poin s o he igh o qin P;
NB← he numbe o blue poin s o he le o pin P;
NR← he numbe o ed poin s o he igh o qin P;
h←ΣB+ΣR+Σ
NB+NR+N;
swi ch hdo
case p<h<q
e u n h;
end
case h<p
P←subse o P o he le o h;
Σ←Σ+ΣR;
N←N+NR;
end
case h>q
P←subse o P o he igh o h;
Σ←Σ+ΣB;
N←N+NB;
end
end
un il ;
Algo i hm 1:A e ageO Misclassi ied.
2.4. MinMis
Conside insepa able poin se s Rand B. A di e en way o achie e sepa abili y is by emo ing misclassi ied poin s.
The MinMis p oblem o R∪Bis equi alen o compu ing an op imal classi ie o Band R ha minimizes he numbe o
misclassi ied poin s (see [25] o he p oblem in wo dimensions).
In o de o compu e a classi ie hOp yielding he minimum numbe o misclassi ied poin s, i.e., he classi ie hOp ha
minimizes s:= s0(h)= |Ξ(h)|, we so he poin s in O(nlog n) ime, ob aining a linea numbe o in e als delimi ed by
consecu i e poin s. Any poin in an in e al gi es he same alue o s. Scanning he poin s le o igh , while main aining he
numbe o misclassi ied poin s o ei he colo , one can de e mine he alue o sin each in e al, and he e o e he minimum
alue, in linea ime. We hus ob ain an o e all O(nlog n) ime algo i hm o compu ing he op imal classi ie (ei he a poin
o an in e al).
Nex we see ha his algo i hm is op imal. Conside he ollowing ε-dis ance p oblem o poin s on a line [3]:
The ε-dis ance p oblem. Gi en a se o npoin s x1,...,xnon a line and a eal alue ε > 0, decide whe he |xi−xj|> ε,
o all i,j∈ {1,...,n},i= j.
The ε-dis ance p oblem has an Ω(nlog n)- ime lowe bound in he algeb aic compu a ion ee model [3]. Now we educe
he ε-dis ance p oblem o ou MinMis p oblem as ollows.
We a e gi en x1,...,xnand ε > 0. Fo each xiwe add i=xi−ε/2 o Rand bi=xi+ε/2 o B. In addi ion, we c ea e 10n
ed poin s o he le o all poin s conside ed so a and 10nblue poin s o he igh o all o hem. This can be easily done in
linea ime. This ensu es ha he le side o he classi ie is conside ed ed and he igh is blue, o he op imal classi ie .
Re e o Fig. 1.
Fig. 1. Lowe bound cons uc ion.
Fig. 2. P ojec ing an op imal solu ion.
Now, i |xi−xj|> ε, o all i,j∈ {1,...,n},i= j, hen he ed and blue poin s coming om poin s xial e na e along he
line: ed, ollowed by blue, ollowed by ed, e c. Thus o a sepa a o hlying be ween hese poin s, he numbe o misclassi ied
poin s oscilla es be ween nand n−1. In pa icula , i is easy o check ha he numbe o misclassi ied poin s is a leas n−1
o any posi ion o hand he minimum is n−1.
On he o he hand, i he e exis iand j= i, such ha |xi−xj| ≤ ε, hen he e is a leas one poin common o he in e als
[ i,bi]and [ j,bj], o i= j. Such a poin misclassi ies no mo e han n−2 poin s. Thus we ha e p o ed
Theo em 4. The one-dimensional MinMis p oblem can be sol ed in O(nlog n) ime and his is he bes possible in he algeb aic
compu a ion ee model.
3. F om one o highe dimensions
Be o e p oceeding wi h he highe -dimensional e sions o ou p oblem, we make he ollowing simple bu c ucial
obse a ion which ollows om he ac ha signed Euclidean dis ances o a hype plane a e p ese ed unde an o hogonal
p ojec ion o a line o hogonal o he hype plane ( e e o Fig. 2):
Obse a ion 5. Le hOp be an op imal classi ie o insepa able se s R,B⊂Rd,d>1, o any o ou e o measu es. Le ℓbe
he line pe pendicula o hOp and passing h ough he o igin, and le R⊥,B⊥, and h⊥
Op be he espec i e o hogonal p ojec ions o
R,B, and hOp o ℓ. Then h⊥
Op is an op imal classi ie o he one-dimensional p oblem R⊥,B⊥ o he same e o measu e.
We ind he ollowing gene al app oach o ob ain an op imal classi ie use ul o se e al di e en e o measu es. Gi en
a non- e ical candida e classi ie hype plane h, we aim o place ed poin s o he le o i and blue poin s o he igh o
i ( e ical classi ie s can o en be handled by an ex ension o he ollowing discussion, o di ec ly, as a p oblem o inding
an op imal classi ie in one lowe dimension). Classi ie s wi h ed poin s o he igh o hem and blue poin s o he le a e
handled by a symme ic a gumen .
Gi en a se P=B∪Ro poin s, and a candida e classi ie h, he exac analy ical o m o he e o measu e s(h)depends on
he se Ξ(h)o misclassi ied poin s, which in u n is de e mined by he way in which hpa i ions P; in ac , o all measu es
bu s∞ he analy ical o m is comple ely de e mined by his bipa i ion. We now conside he si ua ion in he dual: le
A:= A(P∗)be he a angemen o he planes dual o poin s o P[23]. The a ious bipa i ions o Pby hco espond p ecisely
o he a ious cells o A ha may con ain he poin h∗dual o h. As we will see in ollowing sec ions, he analy ical o m o
s(h) o MinSum and MinSum2is no only comple ely de e mined by he cell Ccon aining h∗, bu can also (1) be upda ed
om cell o neighbo ing cell in cons an ime and (2) be used o compu e a g minh∗∈Cs(C)in cons an ime, unde ce ain
assump ions on ou model o compu a ion; see below o de ails. An analogous s a emen holds o MinMis, wi h ‘‘cells’’
eplaced by ‘‘ aces o any dimension’’, as his e o measu e is no con inuous. This implies
Theo em 6. Le R and B be insepa able poin s se s in Rd,d>1. An op imal classi ie acco ding o MinSum,MinSum2, o MinMis
e o measu e can be compu ed in O(nd) ime.
We de o e he nex sec ion o MinMax, which equi es sepa a e ea men . We u he discuss he emaining measu es
and ela ed exis ing wo k in Sec ions 5–7.

abcd
Fig. 3. An ipodal pai s om CH(B)and CH(R)a e shown in ou ep esen a i e con igu a ions.
4. Highe dimensions: MinMax
Recall ha we ha e assumed ha Rand Ba e insepa able, so ha he con ex hulls CH(R)and CH(B)p ope ly in e sec .
Combining Obse a ions 1 and 5, we no ice ha an op imal classi ie hin any ixed di ec ion, o he MinMax measu e,
occu s hal -way be ween he le suppo ing hype plane o Band he igh suppo ing hype plane o Rpa allel o h. The
e o s(h)is p ecisely hal he dis ance be ween hese hype planes. Hence minimizing s(h)is equi alen o minimizing his
dis ance, o e all o ien a ions o h. I is no di icul o see ha he smalles such dis ance, o e all possible o ien a ions o h,
is p ecisely he minimum dis ance by which one needs o ansla e CH(R) o sepa a e i om CH(B). This quan i y has been
s udied in he pas , unde he names in e sec ion dep h and pene a ion dep h [2,8,15,21,32,33].
In he ligh o he p e ious discussion, he wo-dimensional e sion o he p oblem can be sol ed in linea ime by he
o a ing-calipe s me hod [44], once he con ex hulls o Rand Bha e been compu ed. (Recall ha he con ex hull o a se o n
poin s in wo dimensions can be compu ed op imally in O(nlog n) ime, using O(n)space [23].) See Fig. 3 o an illus a ion.
Thus we ha e
Theo em 7. The wo-dimensional MinMax p oblem can be sol ed in O(nlog n) ime, using O(n)space. This canno be imp o ed
in he algeb aic compu a ion ee model.
To show ha he algo i hm is wo s -case op imal, we use a educ ion om he Max–Gap p oblem o poin s on he i s
quad an o he uni ci cle which is known o ha e an Ω(nlog n)lowe bound in he algeb aic compu a ion ee model [3].
An ins ance o Max–Gap o poin s on he i s quad an o he uni ci cle is a se o poin s Z, oge he wi h he ques ion:
Wha is he maximum Euclidean dis ance be ween consecu i e poin s?
The educ ion is as ollows. Le a se Zo npoin s on he open i s quad an o he uni ci cle be an ins ance o Max–Gap.
Pu R1:= Z= { 1,..., n}, whe e ia e numbe ed in hei x-o de (which is no gi en). Re lec R1 h ough he o igin o
ob ain a se B1= {b1,...,bn}o blue poin s in he hi d quad an , as illus a ed in Fig. 4. Cons uc h ee addi ional ed
poin s ′
iand symme ically loca ed blue poin s b′
i; e e o Fig. 4. We d aw e ical and ho izon al lines a dis ance 2 om
he o igin. The poin ′
2lies a he bo om le co ne o he esul ing 4 ×4 squa e; ′
1is chosen on he le edge o he squa e
so ha 1 ′
1is angen o he ci cle. The emaining addi ional poin s a e cons uc ed analogously. Pu R:= R1∪{ ′
1, ′
2, ′
3}
and B:= B1∪{b′
1,b′
2,b′
3}.
Now conside he esul ing MinMax op imiza ion p oblem o Rand B. Obse e ha he smalles dis ance be ween
pa allel suppo lines o CH(R)and o CH(B)occu s when he lines pass h ough poin s ha gi e he Max–Gap o Z, as
indica ed in he igu e.
Thus he solu ion o he MinMax p oblem would yield a line h om which one can, in linea ime, iden i y Max–Gap in
Z, comple ing he p oo .
In h ee dimensions, he MinMax p oblem (also known as pene a ion dep h) can be sol ed by examining all pai s o
po en ial con ac s made by wo suppo ing planes wi h opposi e o ien a ions, one o CH(R)and one o CH(B). (Recall ha
he con ex hull o a se o npoin s in h ee dimensions can be compu ed op imally in O(nlog n) ime.) The p oblem wi h
his app oach is ha he numbe mo such pai s o con ac s is quad a ic in he wo s case, as in he wid h p oblem [29]. Any
algo i hm ha e alua es all such pai s o con ac s will un in wo s -case ime Ω(n2). By using he echniques de eloped by
Houle and Toussain [29] we can ob ain an op imal app oxima e MinMax sepa a o in O(m+nlog n) ime, bu his is no
he bes possible. The e exis s ex ensi e li e a u e on wid h compu a ion and pene a ion dep h, as men ioned abo e. In
pa icula , in [2] i was shown how o compu e he pene a ion dep h in expec ed ime O(n3/2+δ), o any δ > 0. (In ac , he
expec ed unning ime o he algo i hm is ac ually O(m1/2+δn1/2+n1+δ), so i will un signi ican ly as e when m≪n2.)
As o he wid h p oblem, o d≥4, an O(n⌈d/2⌉) ime algo i hm can be achie ed by ealizing he solu ion space as a
con ex poly ope in Rd+1, applying an op imal hal space in e sec ion algo i hm, iangula ing he esul ing se , and explici ly
op imizing s∞(h) unc ion o e each simplex sepa a ely [10,16]. (Recall ha he con ex hull o a se o npoin s, o he
in e sec ion o nhal spaces, in any ixed dimension d≥4 can be compu ed op imally in O(n⌈d/2⌉) ime [14].)
Fig. 4. The cons uc ion o he se s Rand B om Zis shown illus a ing he lowe bound a gumen .
5. Highe dimensions: MinSum
As ou lined a he end o Sec ion 3, one can ind he op imal classi ie o he MinSum measu e by e ec i ely examining
all candida e classi ie s h, o equi alen ly, enume a ing all possible placemen s o he poin h∗dual o hin he a angemen
A. In his sec ion we explain he de ails o his p ocess and simpli y i a g ea deal by p o ing he ollowing heo em, which
implies ha only he e ices o he dual a angemen Aneed o be examined.
Theo em 8. Le R and B be insepa able poin s se s in Rd,d>1. Then he e is an op imal classi ie hOp o R and B ha con ains
d a inely independen poin s o R ∪B. Equi alen ly, h∗
Op lies a a e ex o A. The e ex mus belong o a cell o he -le el o A.
P oo . We will make a sligh no a ional adjus men , jus o he du a ion o his sec ion. We will be discussing ways in
which a hype plane hpa i ions a poin se P. This is unambiguous as long as hdoes no pass h ough any o he poin s. In
he dual, as long as h∗s ays o he hype planes o P∗, he e is a clea no ion o which hype planes lie below i and which lie
abo e. S a ing wi h a poin h∗in an open cell co A, conside he se Ξ(c)=Ξ(h)o misclassi ied poin s. Now ix his se
Ξ(c)and le h∗ a y o e he closed cell ¯
c: in he ollowing discussion we ea jus he poin s o Ξ(c)as misclassi ied, and
none o he . This a ies om ou o iginal de ini ion in ha some poin s con ained in hwill now be conside ed misclassi ied.
This does no a ec ou measu e o e o , as he con ibu ion o a poin on h o s(h)is ze o, whe he o no i is conside ed
misclassi ied.
The e ec o his adjus men in he dual is as ollows: o a gene ic poin h∗∈c, we de e mine which hype planes o P∗
lie abo e and which below, and hen ex end his con en ion o poin s h∗lying on he bounda y o c.
Recall ha ansla ing a candida e classi ie hpa allel o i sel co esponds o mo ing h∗along a line pa allel o he xd-axis.
Applying Theo em 2 and Obse a ion 5 o he bes classi ie in his amily o hype planes, we conclude ha he e mus be
p ecisely hype planes abo e h∗and p ecisely bhype planes below i , i.e., h∗mus lie in a (closed) cell on he -le el o A.
(A ull-dimensional cell lies on he -le el o A, o is an -le el cell, when p ecisely hype planes pass below i .) Addi ionally,
pu ing ρ=ρ(h):= |R(h)|and β=β(h):= |B(h)|, we mus ha e ρ=β o an op imal classi ie . We obse e ha
s(h)=
p∈R(h)
d(p,h)+
p∈B(h)
d(p,h)=ρd(h,C(R(h))) +βd(h,C(B(h)))
=ρ(d(h,C(R(h))) +d(h,C(B(h)))),
whe e we ha e used C(·) o deno e he cen oid o a se . Fix a closed -le el cell ¯
c. Since (wi h ou adjus ed con en ion) ρis
a cons an o e ¯
c, o minimize s(h)o e ¯
c, i is su icien o minimize he exp ession H(h):= d(h,C(R(h))) +d(h,C(B(h)))
o e ¯
c. We now a gue ha his la e exp ession can a ain i s minimum only a a e ex o ¯
c.
In sho , he unc ion we a e minimizing is he sum o he dis ances o cen oids o he ed and he blue misclassi ied
poin s, which by de ini ion lie on he opposi e sides o h. I he e we e no es ic ions on posi ioning he hype plane
h, he unc ion would achie e i s minimum alue o ze o when hpassed h ough he wo cen oids. Minimizing H(h),
while cons aining h∗ o lie in ¯
c, is equi alen o es ic ing ou a en ion o hose hype planes h ha sepa a e CH(R(h))
and CH(B(h)). We a gue ha among all such hype planes h, none can minimize s(h)wi hou passing h ough d(a inely
independen ) poin s o P. Indeed, H(h)= |s|sin α, whe e αis he angle be ween hand he segmen s:= C(R(h))C(B(h))
and |s|is he leng h o s;H(h)canno achie e i s minimum o ze o, since he endpoin s o slie on opposi e sides o hand
ha ing slie wi hin hwould imply ha Rand Ba e sepa able, con adic ing ou assump ions.
We i s a gue ha hmus be a sepa a ing angen o CH(R(h)) and CH(B(h)). I hs ic ly sepa a es he wo se s, i can
be o a ed (say, a ound s∩h) o dec ease αand hus h. Hence hmus ouch a leas one o he se s. I hmisses he o he se ,
i can be shi ed pa allel o i sel wi hou a ec ing H(h) o s ic ly sepa a e he wo se s, yielding a con adic ion, as abo e.
Thus his a angen o he wo se s and passes h ough a leas wo o hei e ices.
As long as he a ine dimension o h∩Pis less han d−1, we can o a e ha ound h∩P. I is easy o check ha a leas
one ‘‘di ec ion’’ o his o a ion educes αand hus H(h). (Fo speci ici y, pick any d−2- la πcon aining h∩Pand o a e
ha ound i : he e is a one-dimensional amily o hype planes con aining π, so his o a ion is well-de ined. By assump ion,
i o a ed by a su icien ly small amoun in ei he di ec ion, hcon inues o be an inne angen o CH(R(h)) and CH(B(h)). In
a leas one di ec ion, howe e , he angle αdec eases. Hence he o iginal hcould no minimize H(h), as claimed.)
The e o e, as long as hcon ains ewe han dpoin s o P, he e is a leas one di ec ion in which i can be in ini esimally
o a ed a ound he poin s h∩P, while main aining angency o CH(R(h)) and CH(B(h)) and educing α. Thus any such
choice o a hype plane canno be a minimum, o a gi en bipa i ion. In o he wo ds, he a ine hull o hOp ∩P, o an
op imal classi ie hOp , mus ha e dimension d−1, o h∗
Op mus be a e ex o A, as claimed. 
5.1. MinSum o d =2
Le hbe a candida e classi ie line o Rand Bacco ding o he MinSum c i e ion, wi h h+(h−)deno ing he closed
hal plane o he igh (le ) o h.
Le h:ax +y+e=0. Deno e by px,py he coo dina es o a poin p. The con ibu ion o p∈R(h) o s(h):= s1(h)is
apx+py+e
√a2+1,
while he con ibu ion o p∈B(h)is gi en by a simila exp ession, wi h a nega i e sign. Summing he con ibu ions o all
poin s and using he ac ha |B(h)|=|R(h)|(see p oo o Theo em 8), we ob ain
s(h)=s(a)=A1a+A2
√a2+1,
whe e A1=A1(h):= p∈R(h)px−p∈B(h)pxand A2=A2(h):= p∈R(h)py−p∈B(h)py;A1and A2depend only on he
bipa i ion o Pby hand no on he p ecise placemen o h; he unc ion, o a ixed Ξ, depends only on a, he slope o h.
As no ed abo e, he op imum mus be achie ed a a e ex o an -le el cell in A(see Fig. 5). Tigh bounds on he maximum
complexi y (i.e., numbe o edges and e ices) o he -le el cells in an a angemen o nlines a e no known—de e mining
he o de o magni ude o his quan i y as a unc ion o nis a long-s anding open p oblem in disc e e geome y. Fo =Θ(n)
i is known o be neΩ(√log n)[43] and O(n4/3)[20]. The e is ex ensi e li e a u e o cons uc ing le els in line a angemen s.
The bes known de e minis ic algo i hm is due o Chan [9] and uns in O(n4/3log1+εn) ime and O(n)space. Chan [9,13]
p esen ed a andomized algo i hm ha gua an ees O(n4/3)expec ed ime o cons uc ing he -le el in an a angemen o
nlines in he plane; he bounds imp o e somewha i ≪n.
Once he -le el cells ha e been compu ed, he emaining compu a ions can be ca ied ou in ime p opo ional o he
size o he le el. Hence we ha e a de e minis ic O(n4/3log1+εn) ime algo i hm and a andomized O(n4/3)expec ed unning
ime algo i hm o inding he se o all op imal classi ie s minimizing he MinSum e o measu e in he plane.
Theo em 9. The wo-dimensional MinSum p oblem can be sol ed de e minis ically in ime O(n4/3log1+εn) o an a bi a ily
small cons an ε > 0o in O(n4/3)expec ed ime.
5.2. MinSum o d ≥3
The o egoing discussion ex ends o h ee and highe dimensions. We illus a e he calcula ions in h ee dimensions. Le
h:ax +ey +z+ =0 be a plane wi h no mal ec o (a,e,1). Le p=(px,py,pz)∈P, hen d(p,h)is gi en by
d(p,h)= ±apx+epy+pz+
√a2+e2+1,
wi h he sign chosen acco ding o whe he p∈h+o p∈h−. Since, by Theo em 2 and Obse a ion 5,|B(h)| = |R(h)|, we
ha e
s(h)=aA1+eA2+A3
√a2+e2+1,
whe e A1=A1(h):= p∈R(h)px−p∈B(h)px,A2=A2(h):= p∈R(h)py−p∈B(h)py, and A3=A3(h):= p∈R(h)pz−
p∈B(h)pz. These alues a e cons an s o a ixed bipa i ion, i.e., o h∗in a ixed cell o A. Hence, hese quan i ies and
he exac analy ic exp essions o s(h)can be main ained in cons an ime, when mo ing om a le el- cell o an adjacen
le el- cell.
The o al complexi y o he cells on he -le el is he numbe o hei e ices, edges, and aces. Unde gene al posi ion
assump ions, i is p opo ional o he numbe o e ices o he cells in ol ed. The numbe o e ices o he -le el is a
Fig. 5. A se o 8 poin s in he plane (le ). The le el-4 cells in he dual a angemen o he 8 lines ( igh ).
mos O(n 3/2)[41]; he exac maximum complexi y o he -le el is a long-s anding open p oblem in disc e e geome y.
Chan [12] gi es an O(nlog n+n 3/2log6 )expec ed ime algo i hm o cons uc ing he -le el in an a angemen o n
planes. As be o e, gi en he se o -le el cells, we a e se hese cells in a, say, dep h- i s -sea ch o de o he g aph o
hei adjacencies, going om cell o neighbo ing cell c, upda ing he quan i ies A1(c), A2(c)and A3(c)in cons an ime and
ob aining he exac closed- o m equa ion o he unc ion s(c) o he cu en cell. By Theo em 8, e alua ing s(h)on all
e ices o -le el cells is su icien o loca e he op imal classi ie (s). Each such e alua ion is done in cons an ime, apa
om some ini ializa ion cos , so he unning ime is domina ed by he complexi y o compu ing he -le el.
Theo em 10. The h ee-dimensional MinSum p oblem can be sol ed in O(n5/2log6n)expec ed ime.
In highe dimensions, he same app oach s ill applies. Namely he op imum is achie ed by hdual o a e ex o an -le el
cell o A. Thus i is su icien o e alua e he unc ion a hese e ices. This can be done in cons an ime pe e ex, a e
some linea - ime se -up. The bo leneck again is compu ing he said e ices.
Again, de e mining he o de o magni ude o he maximum numbe o such e ices is a long-s anding open p oblem
in disc e e geome y. I is asymp o ically he same as he complexi y o he -le el. Fo dimension d≥4, he bes known
uppe bound o he size o he -le el is only sligh ly be e han he On⌊d/2⌋ ⌈d/2⌉[16]. Mo e speci ically, i is O(nd−αd)
o a e y small cons an αd=1/(4d−3)d. As Aga wal e al. [1] obse ed, he bound can be made sensi i e o , namely
O(n⌊d/2⌋ ⌈d/2⌉−αd). Ma oušek e al. [34] gi e an O(n4−2/45)uppe bound o d=4.
Fo an a bi a y ixed dimension d, he -le el in an a angemen o nhype planes in Rdcan be cons uc ed
de e minis ically (see Chan [13]) in ime
On⌊d/2⌋ ⌈d/2⌉log n
log O(1).
To summa ize, we ha e p o en
Theo em 11. The d-dimensional MinSum p oblem can be sol ed de e minis ically in ime
On⌊d/2⌋ ⌈d/2⌉log n
log O(1)=O(nd).
6. Highe dimensions: MinSum2
We p oceed o implemen he plan ou lined a he end o Sec ion 3 o MinSum2. Namely, we conside he dual
a angemen Aand e alua e s2(h) o h∗ anging o e all cells co A. This co esponds o ixing he se s R(h)=R(c)and
B(h)=B(c)and he e o e he exp ession o s2(h)in e ms o he coo dina es o h∗. The unc ion is a quad a ic exp ession
whose minimum can be compu ed in cons an ime, in cons an dimension; his assumes he abili y o compu e oo s o a
sys em o O(d)equa ions in dunknowns, which is no an uncommon assump ion in compu a ional geome y; in d=2 he
minima can be compu ed explici ly in adicals. We ill in some o he de ails below.
6.1. MinSum2 o d =2
Le hOp :ax +y+e=0 be he op imal classi ie line acco ding o he MinSum2c i e ion. The squa ed dis ance be ween
a poin pand he line his gi en by
d2(p,h)=(apx+py+e)2
a2+1.