Sep embe 11, 2012 9:30 WSPC/Guidelines S0218195912500021
SEPARABILITY OF POINT SETS BY k-LEVEL LINEAR
CLASSIFICATION TREES∗
ESTHER M. ARKIN
Depa men o Applied Ma hema ics and S a is ics, S ony B ook Uni e si y
S ony B ook, New Yo k 11794, USA
es he .a kin@s onyb ook.edu
DELIA GARIJO†and ALBERTO M´
ARQUEZ‡
Depa amen o de Ma em´a ica Aplicada I, Uni e sidad de Se illa
A da. Reina Me cedes s/n, 41012 Se illa, Spain
†[email p o ec ed]
‡[email p o ec ed]
JOSEPH S. B. MITCHELL
Depa men o Applied Ma hema ics and S a is ics, S ony B ook Uni e si y
S ony B ook, New Yo k 11794, USA
joseph.mi chell@s onyb ook.edu
CARLOS SEARA
Depa amen de Ma em`a ica Aplicada II, Uni e si a Poli `ecnica de Ca alunya
Jo di Gi ona 1, 08034 Ba celona, Spain
ca los.sea [email protected]
Recei ed 6 Ap il 2011
Re ised 9 Janua y 2012
Communica ed by God ied Toussain
ABSTRACT
Le Rand Bbe se s o ed and blue poin s in he plane in gene al posi ion. We s udy he
p oblem o compu ing a k-le el bina y space pa i ion (BSP) ee o classi y/sepa a e R
and B, such ha he ee de ines a linea decision a each in e nal node and each lea
o he ee co esponds o a (con ex) cell o he pa i ion ha con ains only ed o only
blue poin s. Speci ically, we show ha a 2-le el ee can be compu ed, i one exis s, in
∗A p elimina y e sion o his wo k appea ed in he Abs ac s o he 26 h Eu opean Wo kshop on
Compu a ional Geome y, Do mund (Ge many), 2010, pp. 41–44. E. A kin and J. Mi chell a e
pa ially suppo ed by he Na ional Science Founda ion (CCF-0729019, CCF-1018388). D. Ga ijo
and A. M´a quez a e pa ially suppo ed by p ojec MTM2008-05866-C03-01. C. Sea a is pa ially
suppo ed by p ojec s MTM2009-07242, Gen. Ca . DGR2009GR1040, and he ESF EUROCORES
p og amme Eu oGIGA — ComPoSe IP04 — MICINN P ojec EUI-EURC-2011-4306.
143
In . J. Compu . Geom. Appl. 2012.22:143-165. Downloaded om www.wo ldscien i ic.com
by UNIVERSITY OF SEVILLE on 01/25/16. Fo pe sonal use only.
Sep embe 11, 2012 9:30 WSPC/Guidelines S0218195912500021
144 E. M. A kin e al.
ime O(n2). We show ha a minimum-le el (3 ≤k≤log n) ee can be compu ed in
ime nO(log n). In he special case o axis-pa allel pa i ions, we show ha 2-le el and
3-le el ees can be compu ed in ime O(n), while a minimum-le el ee can be compu ed
in ime O(n5).
Keywo ds: Red-blue sepa a ion; bina y space pa i ions; classi ica ion; decision ees;
machine lea ning.
1. In oduc ion
Conside a se o npoin s in he plane in gene al posi ion. Each poin is ei he
“ ed” o “blue”. Le Rdeno e he se o ed poin s and le Bdeno e he se o blue
poin s. We s udy he sepa abili y o Rand Bby a k-le el bina y space pa i ion
ee. Speci ically, a bina y space pa i ion ee Tis a oo ed ee; each node o T
co esponds o a (con ex, polygonal) egion o he plane, wi h each nonlea node
ha ing an associa ed pa i ion line, which pa i ions i s co esponding egion in o
he wo egions co esponding o i s child en. The oo o Tis associa ed wi h he
en i e plane; he oo node is a le el (o dep h) 0. The child en o he oo node a e
a le el 1; in gene al, nodes a le el ia e connec ed o he oo by a (unique) pa h
in To leng h i(i.e., ha ing iedges). A k-le el ee bina y space pa i ion ee T
has nodes a le els {0,1,...,k}. The egions associa ed wi h he lea es o T o m a
pa i ion o he plane in o con ex polygons.
We say ha Rand Ba e sepa a ed by a k-le el bina y space pa i ion ee, T,
i each egion associa ed wi h he lea es o Tis monoch oma ic (i.e., con ains only
poin s o Ro only poin s o B). The sepa a ing k-le el ee Tco esponds o a
ecu si e pa i ioning o he plane in o disjoin con ex egions using (up o) 2k−1
sepa a ing s aigh cu s. Such a ee To heigh k(i.e., wi h kle els) can be used as
a classi ica ion ee o ed/blue poin s; we can classi y, in ime O(k), a new poin
as “ ed” o “blue” based on he colo associa ed wi h he cell (co esponding o a
lea in he ee) in which i is loca ed. See Figu e 1.
Rela ed wo k. Sepa abili y o poin se s is undamen al o classi ica ion, clus e ing,
and machine lea ning. The sepa a ing k-le el ee gene alizes simple sepa abili y
c i e ia ha ha e been p e iously s udied. The mos basic sepa abili y c i e ia o
Rand Bis ha o linea sepa abili y, which co esponds o a sepa a ing 1-le el
B1
B2
B2
B1R2
R1
R2
R1
q
s/s
ℓ1
ℓ0
ℓ1ℓ2
ℓ0
ℓ2
p
q
Fig. 1. A sepa a ing 2-le el ee.
In . J. Compu . Geom. Appl. 2012.22:143-165. Downloaded om www.wo ldscien i ic.com
by UNIVERSITY OF SEVILLE on 01/25/16. Fo pe sonal use only.
Sep embe 11, 2012 9:30 WSPC/Guidelines S0218195912500021
Sepa abili y o Poin Se s by k-Le el Linea Classi ica ion T ees 145
ee: The e exis s a line sepa a ing Rand B. Linea sepa abili y can be decided
in linea ime.13 Fo se s Rand B ha a e no linea ly sepa able, gene aliza ions
include he ollowing sepa abili y c i e ia: A s ip ( wo pa allel lines, pa i ioning
he plane in o h ee egions), a wedge ( wo ays wi h common o igin, pa i ioning
he plane in o wo egions), a double wedge ( wo in e sec ing lines), o h ee pa allel
lines. All o hese c i e ia can be decided, and co esponding pa i ions compu ed,
in op imal Θ(nlog n) ime.1,2,11,12 (No e ha i Rand Ba e s ip sepa able, hen
hey a e also wedge sepa able.) S ip, wedge, double-wedge, o h ee pa allel lines
sepa abili y c i e ia a e special cases o sepa abili y by a 2-le el ee.
Sepa abili y by mul iple pa allel lines is a special case o sepa abili y by a k-le el
ee; in pa icula , m= 2k−1 pa allel lines can be a associa ed wi h a (heigh -
balanced) k-le el ee. The minimum numbe o pa allel lines needed o sepa a e
Rand Bcan be compu ed in O(n2log n) ime.2I Rand Ba e he e ices o a
egula n-gon, ⌊n/2⌋is a igh uppe bound o he numbe o pa allel lines, and,
gi en he minimum numbe o sepa a ing lines, hei common o ien a ion can be
compu ed in O(nlog n) ime.3
O he sepa abili y c i e ia ha e also been s udied. Gi en any disjoin poin se s,
Rand B, he e always exis s a sepa a ing polygonal chain, which can be compu ed
in O(nlog n) ime. Compu ing a minimum-link sepa a ing polygonal chain ha
u ns al e na i ely le and igh by a cons an angle α≥π/2 can be done in
O(nlog n) ime.11 Sepa abili y by mpa allel lines is a special case o sepa abili y
by a mono one m-link polygonal chain. The p oblem o de e mining a minimum-
link sepa a ing polygonal chain o Rand Bis NP-comple e.9Edelsb unne and
P epa a a8sol ed, in ime O(nlog n), he special case o compu ing a minimum-
edge con ex polygon sepa a ing Rand B(i a con ex sepa a o exis s); hei ime
bound was shown o be op imal in A kin e al.1
Ou mo i a ion is o conside na u al gene aliza ions o p e iously s udied sep-
a a ion and classi ica ion p oblems and, in pa icula , o conside classi ie s ha
a e e y as a que y ime. The speed o classi ica ion o a poin wi h espec o a
k-le el classi ica ion ee is p opo ional o k; hus, we a e mo i a ed o de e mine
classi ica ion ees ha ing he minimum numbe o le els.
Ou line o he pape . We ini ia e he s udy o sepa abili y by k-le el ees by con-
side ing i s he special case o k= 2, sepa abili y by a 2-le el ee. Sec ion 2is
de o ed o a special case o 2-le el sepa abili y, ha o sepa abili y by a zigzag,
which co esponds o 2-le el ee pa i ioning such ha monoch oma ic cells o he
same colo a e adjacen (Figu e 2). In Sec ion 3we s udy he gene al e sion o 2-
le el ee sepa abili y, including he gene aliza ions o h ee o ou dis inc colo s
o poin se s (ins ead o jus wo, ed and blue). In Sec ion 4we conside k-le el ee
sepa abili y and possible con igu a ions o poin s wi h O(log n)-le el ees. Sec ion 5
is de o ed o sepa abili y by k-le el ees whose pa i ioning cu s a e axis-pa allel.
(Such ees and pa i ions a e closely ela ed o kd- ee da a s uc u es, which a e
use ul o a ious ypes o ange que ies; see de Be g e al.,4chap e 5.)
In . J. Compu . Geom. Appl. 2012.22:143-165. Downloaded om www.wo ldscien i ic.com
by UNIVERSITY OF SEVILLE on 01/25/16. Fo pe sonal use only.
Sep embe 11, 2012 9:30 WSPC/Guidelines S0218195912500021
146 E. M. A kin e al.
2. Zigzag Sepa abili y
In his sec ion we conside he zigzag sepa abili y p oblem: De e mine whe he he
se s Rand Ba e sepa able by a zigzag Z= (ℓ1, s, ℓ2), ha is a simple, noncon ex
3-link polygonal chain o med by wo ays ℓ1,ℓ2and a segmen sjoining he o igins
o he ays (Figu e 2). Le ℓsbe he line con aining he segmen s, and le ℓ′
1(ℓ′
2) be
he line con aining he ay ℓ1(ℓ2). Le CH(X) deno e he con ex hull o a poin se
X. We can assume ha he simple known special cases o sepa abili y ha e al eady
been es ed; speci ically, we assume ha Rand Ba e no sepa able by a line, s ip,
wedge, o con ex polygonal chain, each o which can be decided in O(nlog n) ime.
Thus, unde his condi ion, he ollowing lemma is s aigh o wa d.
B1
B2
B2
B1R2
R1
R2
R1
q
s/s
ℓ1
ℓ1ℓ2
ℓ2
s
ℓs
ℓs
......................................................
Fig. 2. A sepa a ing zigzag.
Lemma 1. Le Rand Bbe zigzag sepa able bu no sepa able by a con ex polygon.
Then, CH(R)con ains a leas one blue poin , and CH(B)con ains a leas one
ed poin .
The e a e h ee ypes o zigzags depending on he alues o he angles αand β
o med by ℓsand ℓ1, and by ℓsand ℓ2, espec i ely (Figu e 3). A sepa a ing zigzag
Z= (ℓ1, s, ℓ2) de ines ou wedges ha pa i ion Rin o R1and R2, and Bin o B1
and B2, all ou subse s a e non-emp y, since Rand Ba e no wedge sepa able.
Since sepa a ing zigzags a e no necessa ily unique, we make he choice spe-
ci ic by conside ing wo op imal sepa a ing zigzags: Ei he a zigzag maximizing
min{α, β}, called he mos con ex sepa a ing zigzag (app oxima ing linea sepa a-
bili y), o a zigzag ha minimizes max{α, β}(app oxima ing sepa abili y by h ee
pa allel lines).
Lemma 2. Le Z= (ℓ1, s, ℓ2)be he mos con ex sepa a ing zigzag o Rand
B. Then each o he wo ays, and he segmen o Zpass h ough wo poin s o
di e en colo s. Mo eo e , ei he ℓ′
1is an inne common angen line o CH(R2)
and CH(B), o ℓ′
2is an inne common angen line o CH(B2)and CH(R).
P oo . The key idea is o s e ch he sepa a ing zigzag un il each pa o he
s uc u e ouches wo poin s o di e en colo s. Mo eo e , o each o he ypes o
zigzag in Figu e 3, ei he ℓ′
2in e sec s ℓ1o ℓ′
1in e sec s ℓ2. In he i s case ℓ′
1is an
In . J. Compu . Geom. Appl. 2012.22:143-165. Downloaded om www.wo ldscien i ic.com
by UNIVERSITY OF SEVILLE on 01/25/16. Fo pe sonal use only.
Sep embe 11, 2012 9:30 WSPC/Guidelines S0218195912500021
Sepa abili y o Poin Se s by k-Le el Linea Classi ica ion T ees 147
(a) (b) (c)
α
ββ
β
αα
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
ℓ1
ℓ2
s
ℓ1ℓ1
ℓ2ℓ2
ssR1
R2
B1
R1
B1B1
R2R2
B2
B2
B2
R1
ℓs
ℓsℓs
Fig. 3. (a) 0 < α, β < π/2, (b) 0 < α < π/2, π/2≤β < π, and (c) π/2≤α, β < π.
inne common angen line o CH(R2) and CH(B), and in he second case ℓ′
2is an
inne common angen line o CH(B2) and CH(R). No ice ha bo h s a emen s
hold i ℓ′
1and ℓ′
2a e pa allel.
Le IX,Y be he numbe o in e sec ions be ween pai s o edges o he con ex
hulls o wo poin se s Xand Y.
Lemma 3. Le Rand Bbe zigzag sepa able. Then IR,B ∈ {0,2,4,6}.
P oo . Because he con ex hulls a e closed Jo dan cu es, IR,B is e en. I CH(R)
and CH(B) a e nes ed polygons, IR,B = 0 (Figu e 4(a)). Assume ha IR,B ≥2.
By Lemma 2, ei he CH(B) in e sec s CH(R1) bu no CH(R2), o CH(R) in-
e sec s CH(B1) bu no CH(B2). Mo eo e , CH(R1) and CH(B) a e wedge
sepa able; hus, IR1,B ≤4. Analogously, IB1,R ≤4 (Figu es 4and 5). Since
CH(R) = CH(R1∪R2), he e a e wo b idge-edges be ween CH(R1) and CH(R2).
An analogous s a emen holds o CH(B1) and CH(B2). Hence, IR,B ≤4 + 2 = 6,
co esponding o he a mos six al e na ions o colo s in CH(B∪R) (Figu e 5).
Le RI(BI) be he subse o ed (blue) in e io poin s o CH(B) (CH(R)). By
Lemma 1,|RI| ≥ 1 and |BI| ≥ 1. I IR,B = 6, le R′
1,R′
2, and R′
3(B′
1,B′
2, and B′
3)
be he h ee disjoin subse s o ed poin s (blue poin s) ha a e no con ained in
CH(B) (CH(R)) de ined acco ding o he 6 in e sec ions o he edges o CH(B)
and CH(R). These eigh subse s and hei espec i e con ex hulls can be compu ed
in O(nlog n) ime (Figu e 5).
Lemma 4. Le Z= (ℓ1, s, ℓ2)be he mos con ex sepa a ing zigzag o Rand B.
Then ℓsis a suppo ing line o some o he ollowing eigh con ex polygons: CH(RI),
CH(BI),CH(R′
1),CH(R′
2),CH(R′
3),CH(B′
1),CH(B′
2), and CH(B′
3).
P oo . We i s p o e ha ei he RIis sepa able om Bby he wedge (ℓs, ℓ2), o
BIis sepa able om Rby he wedge (ℓ1, ℓs), and bo h cases do no always occu
(Figu es 4(a) and 4(c)). By Lemma 2, i R2and Ba e line sepa able, hen R1is
In . J. Compu . Geom. Appl. 2012.22:143-165. Downloaded om www.wo ldscien i ic.com
by UNIVERSITY OF SEVILLE on 01/25/16. Fo pe sonal use only.

Sep embe 11, 2012 9:30 WSPC/Guidelines S0218195912500021
148 E. M. A kin e al.
ℓs
........................................................
R2
R1
B2
B1
ℓ1
ℓ2
(a) (b) (c)
ℓsℓ1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..............................................
R2
ℓ1
ℓ2
ℓ2
R2
R1R1
B1
B1
B2
B2
ℓs
Fig. 4. (a) IR,B = 0, (b) IR,B = 2, and (c) IR,B = 4.
ℓ1
ℓ2
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
R′
1
R′
2
B′
1
B′
2
s
.....................................................................................................................
............
.....................................
......................................
............................
ℓ′
1
ℓ′
2
ℓs
RI
BI
B′
3
R′
3
Fig. 5. Subse s o ed and blue poin s o IR,B = 6.
sepa able om Bby he wedge (ℓs, ℓ2), and so RI⊆R1is sepa able om Bby he
same wedge. By analogous easoning, i B2and Ra e line sepa able, hen BIand
Ra e wedge sepa able.
I IR,B ∈ {0,2,4}, hen ℓsis a suppo ing line o CH(RI), because, o he wise,
he e a e no ed poin s inside CH(B) and hen Bis wedge sepa able om R, since
Zis he mos con ex sepa a ing zigzag. Analogously, i B2and Ra e line sepa able
and IR,B ∈ {0,2,4}, hen ℓsis a suppo ing line o CH(BI).
Assume ha IR,B = 6 and ecall he second s a emen o Lemma 2. Le i s ly
assume ha R2is line sepa able om B, and ℓsis no a suppo ing line o CH(RI).
One o he subse s R′
1,R′
2,R′
3has o be R2(say, R′
3=R2) because, by con exi y
o CH(B), ℓ′
1does no sepa a e wo o hese subse s om CH(B). Thus, R′
1and
R′
2a e con ained in R1and, since ℓsis no a suppo ing line o CH(RI), hen
ℓsis a suppo ing line o ei he CH(R′
1) o CH(R′
2) (Figu e 5). We can p oceed
analogously, i we assume ha B2and Ra e line sepa able, IR,B = 6, and ℓsis no
a suppo ing line o CH(BI).
Lemma 4p o ides he key ool o design he ollowing O(nlog n) ime algo i hm
o compu ing a sepa a ing zigzag Z= (ℓ1, s, ℓ2) o Rand B(i i exis s). The
algo i hm looks o ℓsand checks he linea sepa abili y o CH(R2) and CH(B1)
by ℓ′
1and he linea sepa abili y o CH(R1) and CH(B2) by ℓ′
2. The e a e a linea
numbe o candida es ℓs ha a e suppo ing lines o he eigh con ex polygons
abo e.
In . J. Compu . Geom. Appl. 2012.22:143-165. Downloaded om www.wo ldscien i ic.com
by UNIVERSITY OF SEVILLE on 01/25/16. Fo pe sonal use only.
Sep embe 11, 2012 9:30 WSPC/Guidelines S0218195912500021
Sepa abili y o Poin Se s by k-Le el Linea Classi ica ion T ees 149
Zigzag-algo i hm
Inpu : Poin se s R( ed) and B(blue)
Ou pu : A sepa a ing zigzag Z= (ℓ1, s, ℓ2), o epo ha none exis s
(1) Compu e CH(R), CH(B), RI,BI,CH(RI), CH(BI), and IB,R. Check whe he
IR,B ∈ {0,2,4,6}, and compu e he in e sec ing edges o CH(R) and CH(B).
Check ha CH(RI) o CH(BI) is monoch oma ic. Fo RI={ 1}and
BI={b1}, do as ollows: I 1∈CH(R) and b1∈CH(B), hen Rand B
a e zigzag sepa able as shows Figu e 6(a) and i is easy o see how o compu e
he sepa a ing zigzag. Analogously i 1∈CH(R) and b1is in e io o CH(B)
o ice e sa (Figu e 6(b)). F om now on, assume ha |RI| ≥ 2 o |BI| ≥ 2.
1
b1
b1
1
(a) (b)
Fig. 6. Zigzag sepa abili y wi h |RI|= 1 and |BI|= 1.
(2) Le Pbe any o he polygons: CH(RI), CH(BI), CH(R′
1), CH(R′
2), CH(R′
3),
CH(B′
1), CH(B′
2), o CH(B′
3), wi h hei in e io poin s. Do he ollowing:
(a) So he poin s in (R∪B)−Pby a coun e clockwise o a ional sweep o e
Pwi h an o ien ed suppo ing line ℓsacco ding o Lemma 4.
(b) Do a second o a ional sweep o e P. Each ime ℓsencoun e s a ed o
blue poin o (R∪B)−P, main ain and upda e he con ex hulls CH(R2),
CH(B1) (CH(R1), CH(B2)) o he ed and blue poin s on he le ( igh )
side o ℓsin O(log n) ime.14 In O(log n) ime, check he linea sepa abili y
be ween CH(R2) and CH(B1), and be ween CH(R1) and CH(B2), and
compu e hei espec i e inne common angen lines (Figu e 7). In he
a i ma i e case, a sepa a ing zigzag is ound.
Analysis o he algo i hm. Each s ep can be done in O(nlog n) ime. In s ep 2, a
o a ional sweep is done o e eigh di e en con ex polygons, spending O(nlog n)
ime on each.
To p o e he Ω(nlog n) ime lowe bound o deciding he zigzag sepa abili y,
we educe he s ip sepa abili y p oblem1 o he zigzag sepa abili y p oblem. The
eade is e e ed o A kin e al.1 o he cons uc ion o he educ ion. We place
ed and blue poin s on wo concen ic ci cles wi h app op ia e adii. A modi ica ion
om he cons uc ion in A kin e al.1is needed: We place blue poin s a ound he
smalle , uni - adius ci cle and ed poin s a ound a la ge ci cle o adius d > 1,
and wo addi ional ed poin s, 1and 2, as in Figu e 8. (Speci ically, adius dis
In . J. Compu . Geom. Appl. 2012.22:143-165. Downloaded om www.wo ldscien i ic.com
by UNIVERSITY OF SEVILLE on 01/25/16. Fo pe sonal use only.
Sep embe 11, 2012 9:30 WSPC/Guidelines S0218195912500021
150 E. M. A kin e al.
ℓ1
B1
R2
ℓs
ℓ2
B2
R1
...........................................................................................................
...................
.
.
.
......
...................................
.
..
..
.
..
..........................
.
.
.
.
.
.
.
.
.......
.
.
.
.
.
.
.
.
.
.
.
.
..........
............................................
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
..................................
......
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
...
.
..
..
.
.
.
......................
.........................
Fig. 7. Suppo ing lines be ween monoch oma ic con ex hulls.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.................
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
b1
b2
ǫ
a
2ad
ǫ
1
2
Fig. 8. Cons uc ion o he lowe bound o zigzag sepa abili y.
selec ed so ha a gap o size ǫbe ween wo consecu i e blue poin s on he uni ci cle
de e mines a line, ℓ, h ough hese wo poin s, and a line, ℓ′, h ough he symme ic
pai o blue poin s, such ha ℓand ℓ′pass h ough he co esponding ed poin s on
he ci cle o adius d(Figu e 8). Le ing adeno e he dis ance om he o igin o ℓ
o ℓ′, an app op ia e choice o dis d= 2a/ǫ =√4−ǫ2
ǫ.) Addi ionally, we place wo
blue poin s, b1and b2, a enough away om he la ge ci cle, a posi ions indica ed
in Figu e 8. Now i is clea ha he e exis s a sepa a ing zigzag o he se s o ed
and blue poin s i and only i he same se s o ed and blue poin s wi hou b1and
b2a e s ip sepa able. The las s a emen is educed o de e mining whe he he e
exis wo consecu i e blue poin s in he i s quad an o he smalles ci cle, such
ha hei Euclidean dis ance is g ea e han a gi en ǫ > 0, speci ied in he inpu o
he p oblem.
Theo em 1. Compu ing a sepa a ing zigzag o Rand B equi es Θ(nlog n) ime.
Rema k. An O(n3log n) ime algo i hm o de e mining he sepa abili y o Rand
Bby a mono one (wi h espec o some di ec ion) (k≤7)-polygonal chain is as
ollows: A mid-segmen o he polygonal chain is de ined by a line ℓgoing h ough
wo poin s. Then, we apply an O(nlog n) ime algo i hm o he line, wedge o
zigzag sepa abili y o he poin subse s on bo h sides o ℓ.
In . J. Compu . Geom. Appl. 2012.22:143-165. Downloaded om www.wo ldscien i ic.com
by UNIVERSITY OF SEVILLE on 01/25/16. Fo pe sonal use only.
Sep embe 11, 2012 9:30 WSPC/Guidelines S0218195912500021
Sepa abili y o Poin Se s by k-Le el Linea Classi ica ion T ees 151
3. Sepa abili y by a 2-Le el T ee
We u n now o he p oblem o compu ing a sepa a ing 2-le el ee T= (ℓ1, ℓ0, ℓ2)
o Rand B, whe e ℓ0,ℓ1, and ℓ2a e he o ien ed line, he ay on he le side o ℓ0,
and he ay on he igh side o ℓ0, espec i ely ( ecall Figu e 1). Le ℓ′
1(ℓ′
2) be he
line con aining ℓ1(ℓ2). Deno e by m(ℓ) he slope o ℓ. Le p(q) be he in e sec ion
poin o ℓ0and ℓ1(ℓ2). Tspli s he plane in o ou con ex egions. Recall ha R
and Ba e sepa a ed by a 2-le el ee i he e exis s a pa i ion o R∪Bin o ou
monoch oma ic subse s and a 2-le el ee, T, whose pa i ion o he plane espec s
he pa i ion o R∪B.
C i e ia. The ollowing c i e ia p o ide a sys ema ic classi ica ion o possible
sepa a ing 2-le el ees: (1) m(ℓ0)>0, m(ℓ0)<0, o ℓ0is ho izon al o e ical. (2)
Rela i e posi ion o pand qalong ℓ0:pqo qp. (3) Slopes o ℓ1and ℓ2wi h
espec o ℓ0. (4) Di e en colo assignmen s o he con ex egions.
Classi ica ion. We do case analysis acco ding o he ollowing classi ica ion c i-
e ia: (1) The slope o ℓ0: We only conside he m(ℓ0)≥0 case; he case in which
m(ℓ0)<0 can be analyzed by o a ing he con igu a ion by 90 deg ees and applying
he co esponding m(ℓ0)>0 case. The i s ow o Figu e 9illus a es all possible
cases o m(ℓ0)≥0 acco ding o he di e en ela i e posi ions o he ays ℓ1and
ℓ2. (2) The ela i e posi ion o pand q: We only s udy he case qp. By apply-
ing symme y wi h espec o a e ical line, ollowed by a 90-deg ee o a ion, we
ob ain he case pq; his is seen by compa ing he second ow wi h he i s ow
in Figu e 9. (3) I wo egions ha a e consecu i e (in he o de in which he ci cle
a in ini y mee s he egions) ha e he same colo , he con igu a ion co esponds
o one o he ollowing special cases: Linea , zigzag (p6=q), o wedge sepa abili y
(p=q), each o which can be sol ed in Θ(nlog n) ime.1,11,12 Thus, we assume ha
he colo s al e na e, ℓ0has nonnega i e slope, and qp.
Fo an easie analysis o he poin con igu a ions o he design o algo i hms,
we expand he ou cases o qpin he i s ow o Figu e 9( om le o igh )
in o he se en cases in Figu e 10 as ollows: The i s case is jus he case (a) o
Figu e 10; he second case is expanded in o he cases (b) and (c) in Figu e 10
acco ding o he slope o ℓ1; he hi d case is expanded in o he cases (d) and (e)
..........
............
..........
............
..........
............
..........
............
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
m(ℓ0)>0ℓ0ℓ0ℓ0ℓ0
ℓ0ℓ0ℓ0ℓ0
ℓ1ℓ1
ℓ1ℓ1
ℓ1
ℓ1
ℓ1
ℓ1
ℓ2
ℓ2
ℓ2
ℓ2
ℓ2ℓ2
ℓ2ℓ2
ppp p
pppp
qqq
q
qqqq
pq
qp
Fig. 9. m(ℓ0)>0.
In . J. Compu . Geom. Appl. 2012.22:143-165. Downloaded om www.wo ldscien i ic.com
by UNIVERSITY OF SEVILLE on 01/25/16. Fo pe sonal use only.
Sep embe 11, 2012 9:30 WSPC/Guidelines S0218195912500021
158 E. M. A kin e al.
(b) S a ing a b′
nand ollowing he o de abo e, in O(n) ime compu e
he loca ion o he blue poin s in ℓ+
no ℓ−
n. Le b′
ibe he las blue
poin in ℓ+
n∩ℓ−
R. I he e exis s an app op ia e bipa i ion {B1, B2}, hen
{b′
i, b′
i−1, . . . , b′
1} ⊆ B2.
(c) Le B1={b′
n,...,b′
i+1}and B2={b′
i, b′
i−1,...,b′
1}. By cons uc ion, R1
and B1a e line sepa able by ℓn. In O(n) ime, check i R2and B2a e line
sepa able, and i R1∪B1is line sepa able om R2∪B2. O he wise, he e
does no exis a sepa a ing 2-le el ee o he bipa i ion {R1, R2}. In he
a i ma i e case, cons uc a sepa a ing 2-le el ee T o Rand B.
B1B2
CH(R1)
ℓn
ℓ+
n
ℓ−
n
b′
n
CH(R2)
b′
1
.......................
ℓR
ℓ+
R
ℓ−
R
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...
....
...
....
....
...
.. .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Fig. 15. Illus a ing s ep 3 o he algo i hm o a 2-le el ee o ype (2).
Theo em 2. Compu ing all o he sepa a ing 2-le el ees o Rand Bcan be done
in O(n2) ime and space.
P oo . The algo i hm abo e spends O(n2) ime and space cons uc ing he dual
a angemen A. Fo each pa i ion {R1, R2}o R, he algo i hm decides whe he
he e exis s a sepa a ing 2-le el ee and compu es i in O(n) ime. Lemma 8ensu es
he exis ence o an app op ia e bipa i ion o Ra some s ep, i he e exis s a sepa-
a ing 2-le el ee o Rand B. By Lemma 6we can assume ha ℓis a suppo ing
line o CH(R1) and p oceed analogously o ℓbeing a suppo ing line o CH(R2).
By he same lemma we can assume ha ℓnis a suppo ing line o CH(R1) and
CH(B1).
Rema k. I is easy o see ha all o he combina o ially di e en 2-le el ees o
a se o n ed and blue poin s in Rdcan be compu ed in O(nd+1) ime. Fo d= 2,
he abo e heo em shows ha an imp o ed ime bound o O(n2) is possible. I
emains an open p oblem o de e mine i a sepa a ing 2-le el ee o Rand Bcan
be compu ed in o(n2) ime.
In . J. Compu . Geom. Appl. 2012.22:143-165. Downloaded om www.wo ldscien i ic.com
by UNIVERSITY OF SEVILLE on 01/25/16. Fo pe sonal use only.

Sep embe 11, 2012 9:30 WSPC/Guidelines S0218195912500021
Sepa abili y o Poin Se s by k-Le el Linea Classi ica ion T ees 159
3.2. Th ee o ou colo ed poin se s
The 2-le el ee p oblem o poin se s ha ing h ee o ou dis inc colo s can be
sol ed as ollows. The ou colo s case can be sol ed in O(n) ime by checking he
linea sepa abili y be ween pai s o poin se s. The h ee colo s case, wi h poin se s
R,Band G, can be iewed ei he as a zigzag o Rand G∪B, o as a sepa a ion
wi h a 2-le el ee o Rand G∪B es ic ed o ha e linea sepa abili y be ween G
and B(Figu e 16). Bu , in bo h cases, we ha e as addi ional in o ma ion he linea
sepa abili y o Gand B, which can be checked in ad ance in O(n) ime. We use
his in o ma ion o compu e he co esponding 2-le el ee. Thus, his p oblem can
be sol ed in O(nlog n) ime. This ime bound is op imal, as can be seen om he
zigzag sepa abili y o R,Band G, wi h an easy adap a ion o he lowe bound
cons uc ion in Theo em 1.
R1
R2
B
G
Y
R
B
G
R1
R2
B
G
Fig. 16. 2-le el ees o h ee and ou colo ed poin se s.
Theo em 3. A sepa a ing 2-le el ee o h ee-colo ed se s o npoin s can be
compu ed in O(nlog n) ime, which is wo s -case op imal. Fo ou -colo ed se s o
npoin s a 2-le el ee can be compu ed in O(n) ime.
4. k-Le el T ees
We now conside sepa a ing (k≥3)-le el ees o Rand B. A sepa a ing O(log n)-
le el ee o Rand Bcan be compu ed as ollows: Appealing o he Ham-Sandwich
heo em, we can compu e a line ha gi es an equi able bipa i ion B1∪R1,B2∪R2
o B∪R, hen p oceed ecu si ely on each pa un il we ob ain monoch oma ic
subse s. In he end, we ob ain a k-le el ee o n≤2kpoin s.
No e ha a k-le el ee p oduces a subdi ision o he plane in o monoch oma ic
con ex cells, each one bounded by a mos klines. We can use a dynamic p og am-
ming algo i hm o compu e a minimum-le el ee o Rand Bin (quasi-polynomial)
nO(log n) ime. In pa icula , a subp oblem is speci ied by a con ex polygon Pha -
ing a mos k=O(log n) sides, each de ined by one o he n
2lines de e mined by
poin pai s o R∪B. The op imiza ion o a subp oblem selec s among he ≤n
2
possible cu s, ℓ, and ecu si ely sol es he minimum-le el ee p oblem on each side
o ℓ.
Theo em 4. A sepa a ing k-le el ee o Rand Bexis s wi h k≤ ⌈log n⌉. Fu -
he mo e, a minimum-le el ee can be compu ed in nO(log n) ime.
In . J. Compu . Geom. Appl. 2012.22:143-165. Downloaded om www.wo ldscien i ic.com
by UNIVERSITY OF SEVILLE on 01/25/16. Fo pe sonal use only.
Sep embe 11, 2012 9:30 WSPC/Guidelines S0218195912500021
160 E. M. A kin e al.
On he o he hand, he e exis con igu a ions o poin s o which he dep h k∗o
a minimum-le el ee is Ω(log n). In pa icula , le Sbe a se o npoin s in gene al
posi ion. Replace each poin pi∈Sby a s uc u e o ou ( e y close) poin s, wo
ed and wo blue, as in Figu e 17, ob aining he se s Rand Bo 2n ed and 2nblue
poin s, espec i ely. Any k-le el ee o Rand Bhas o sepa a e each pai o ed
and blue poin s o he pis uc u e and mus , he e o e, ha e k= Ω(log n) le els.
j
pi
pi
p1p2pn
pi
6
O(log n)
Fig. 17. An example (le ) o a con igu a ion o R∪B equi ing an Ω(log n)-le el sepa a ing ee.
I is unlikely ha a subs an ially mo e e icien algo i hm exis s o compu ing
sepa a ing k-le el ees in gene al. In ac , in ela ed wo k, G igni e al.10 conside ed
he p oblem o designing a nea -op imal linea decision ee T o classi y wo gi en
poin se s Rand Bin Rn, so ha Tde ines a linea decision a each in e nal node,
such ha o each lea o T, ei he only ed o only blue poin s lead he algo i hm
o . The au ho s conside ed wo measu es o such a classi ie , he numbe o in e nal
nodes and he dep h o he ee, and p o e a e y s ong nega i e esul on high-
dimensional classi ica ion ees: Unless NP=ZPP, no polynomial- ime algo i hm o
op imizing he dep h o a classi ie can ha e app oxima ion a io be e han any
ixed cons an . Fu he , Das and Good ich7showed ha he ollowing p oblem is
NP-comple e: Gi en a se So npoin s in R3, pa i ioned in o wo concep classes,
ed and blue, decide i he e exis s a decision ee Twi h a mos knodes ha
sepa a es he ed poin s om he blue poin s.
5. Sepa abili y wi h Axis-Pa allel Pa i ions
In his sec ion, we conside k-le el ees de ined by axis-pa allel lines. Fi s we show
how o compu e a 2-le el ee as in Figu e 18(a). We conside he case in which
ℓ0is e ical and ℓ1,ℓ2a e ho izon al; o he cases, which also depend on he colo
assigned o he ec angles p oduced by he 2-le el ee s uc u e, can be handle
analogously. A key obse a ion is ha , i he e exis s a sepa a ing 2-le el ee, hen
du ing a sweep wi h a e ical line ℓ om le o igh he se s o ed and blue poin s
on he le o ℓmus be sepa able by a ho izon al line a leas un il he momen
when ℓ eaches ℓ0. This obse a ion is u ilized in he ollowing O(n) ime algo i hm.
Axis-pa allel 2-le el ee algo i hm. Le T(n) deno e he unning ime o an inpu
o size n. Fi s , compu e (in O(n) ime6) he median Mo he x-coo dina es o he
poin s. Le ℓbe he e ical line h ough M. Le R1and B1( esp., R2and B2) be he
In . J. Compu . Geom. Appl. 2012.22:143-165. Downloaded om www.wo ldscien i ic.com
by UNIVERSITY OF SEVILLE on 01/25/16. Fo pe sonal use only.
Sep embe 11, 2012 9:30 WSPC/Guidelines S0218195912500021
Sepa abili y o Poin Se s by k-Le el Linea Classi ica ion T ees 161
B1B2
ℓ0
..........................................
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...........................................
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
ℓ1
ℓ2
R1
R2
(a) (b)
p
q
ℓ0
..........................................
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...........................................
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
ℓ1
ℓ2
ℓ3
ℓ4
ℓ5
ℓ6
(c)
ℓ0
..........................................
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...........................................
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
ℓ1
ℓ2
ℓ3
ℓ5
ℓ4
ℓ6
Fig. 18. (a) Axis-pa allel 2-le el ee, (b) and (c) axis-pa allel 3-le el ees.
subse s o ed and blue poin s on he le ( esp., igh ) side o ℓ. Check, in ime O(n),
whe he R1and B1( esp., R2and B2) a e line sepa able wi h a ho izon al line. I
he wo answe s a e nega i e, he algo i hm concludes ha he e is no sepa a ing 2-
le el ee. I he wo answe s a e posi i e, he algo i hm concludes wi h a sepa a ing
2-le el ee, wi h ℓ0=ℓ. O he wise, assume ha he posi i e answe is on he le
o ℓ; compu e and s o e he y-in e al o ho izon al sepa a o s o poin s (R1,B1)
le o ℓ. Now, p oceed ecu si ely, in ime T(n/2), o he n/2 poin s on he igh
o ℓ. Speci ically, we compu e he median M′o he x-coo dina es o he poin s
in R2∪B2, and de e mine he y-in e al o ho izon al sepa a o s (i any exis )
o he ed and blue poin s o R2∪B2on each side o a e ical line, ℓ′, h ough
M′, in e sec ing he y-in e al o poin s in R2∪B2le o ℓ′wi h he y-in e al o
poin s (R1∪B1) le o ℓ. The ecu si e sea ch con inues, ei he on he le o on he
igh o each successi e median e ical line, acco ding o he exis ence o ho izon al
sepa a o s ( ecu sing on he side ha has no sepa a o ). The sea ch concludes when
we disco e a e ical sepa a o such ha he e ei he exis ho izon al sepa a o s on
bo h sides (yielding he desi ed 2-le el sepa a ing ee), o we disco e ha he e is
no possible ho izon al sepa a o on bo h sides (showing ha no 2-le el sepa a ing
ee exis s). The unning ime, T(n), sa is ies T(n) = T(n/2)+O(n), implying ha
T(n) = O(n).
Theo em 5. A sepa a ing axis-pa allel 2-le el ee o Rand Bcan be compu ed
in O(n) ime.
Ac ossing 2-le el ee is a 2-le el ee o Rand Bde ined by wo axis-pa allel
pe pendicula lines (p=q). A sepa a ing c ossing 2-le el ee is also a sepa a ing
ho izon al/ e ical double-wedge o Rand B. In A kin e al.,1 he au ho s showed
an Ω(nlog n) ime lowe bound o he ho izon al/ e ical double-wedge sepa abili y
p oblem; his lowe bound applies also o he c ossing 2-le el ee p oblem. An
O(nlog n) ime algo i hm o he sepa abili y by a c ossing 2-le el ee can be
ob ained by i s so ing he poin s o R∪Bby bo h x- and y-coo dina e and hen
applying an easy modi ica ion o he linea - ime algo i hm abo e.
In . J. Compu . Geom. Appl. 2012.22:143-165. Downloaded om www.wo ldscien i ic.com
by UNIVERSITY OF SEVILLE on 01/25/16. Fo pe sonal use only.
Sep embe 11, 2012 9:30 WSPC/Guidelines S0218195912500021
162 E. M. A kin e al.
Axis-pa allel 3-le el ee algo i hm. A key obse a ion is ha i he e exis s a 3-le el
ee o Rand Bwi h a con igu a ion as in Figu e 18(b), hen o any e ical line
ℓ0c ossing he axis-pa allel bounding box o R∪B, ei he (i) he subse o poin s
o R∪Bon he le o ℓ0is sepa able by a 2-le el ee o (ii) he subse o poin s
o R∪Bon he igh o ℓ0is sepa able by a 2-le el ee.
Thus, analogous o he sea ch desc ibed abo e o he 2-le el ee p oblem, we
can do a bina y sea ch o a possible e ical line ℓ0such ha bo h subse s o
poin s o R∪Bon he le and on he igh o ℓ0a e sepa able by a 2-le el ee, o
he conclusion ha no such ℓ0exis s. The esul is an O(nlog n) ime algo i hm.
(O he con igu a ions, as in Figu e 18(c), can be handled analogously.) We now
show, howe e , ha he e is a linea - ime algo i hm o he axis-pa allel 3-le el
ee p oblem.
Conside he case in Figu e 18(b); o he cases a e simila . In O(n) we compu e
he e ical line ℓ′
3con aining he ay ℓ3using he median echnique abo e such
ha he poin s on he le o ℓ′
3a e sepa able by a ho izon al line (say, ℓ′
1); we
also compu e a e ical in e al I1whe e his ho izon al line ℓ′
1can be loca ed.
Then we p oceed analogously (using he median echnique) wi h he poin s on
he igh o he compu ed ℓ′
3un il we ind a e ical line ℓ′
4con aining a ay ℓ4
such ha he poin s be ween ℓ′
3and ℓ′
4a e monoch oma ic, spending O(n) ime
in his second p ocess. Then we p oceed analogously wi h he poin s on he igh
o ℓ′
4un il we ind a e ical line ℓ0such ha he poin s be ween ℓ′
4and ℓ0a e
sepa able by a ho izon al line loca ed in he compu ed e ical in e al I1; again
we spend O(n) ime in his hi d p ocess. Thus, he compu a ion o he line ℓ0
and he 2-le el ee on he le o ℓ0 akes O(n) ime. Simila ly, in addi ional O(n)
ime we check ha he poin s on he igh o he compu ed ℓ0a e sepa able by a
2-le el ee.
No ice ha depending on he e ical/ho izon al choices o ℓ0,ℓ1,ℓ2,ℓ3,ℓ4,
ℓ5,ℓ6, and he colo s assigned o each egion, he numbe o di e en ypes o
axis-pa allel 3-le el ees is 223−1. So he o e all algo i hm akes O(n) ime.
Theo em 6. A sepa a ing axis-pa allel 3-le el ee o Rand Bcan be compu ed
in O(n) ime.
Rema k. The linea - ime me hod o de e mining he exis ence o an axis-pa allel
3-le el ee implies ha , using he bina y sea ch p e iously discussed, we can sol e
he 4-le el ee p oblem in ime O(nlog n), and, mo e gene ally, he k-le el ee
p oblem in ime O(nlogk−3n), o ixed k, wi h a huge dependence on khidden
in he big-Oh no a ion. In ac , he linea - ime me hod we ga e o 3-le el ees
can be ex ended o 4 o mo e le els, yielding a linea - ime me hod o any ixed k;
howe e , he dependence on k e lec s he ac ha he e a e 22k−1k-le el ees,
leading o a e y high (O(22kn)) ime bound in e ms o nand k. Below, we ob ain
polynomial ime in bo h nand k o compu ing a minimum-le el axis-pa allel ee,
using dynamic p og amming.
In . J. Compu . Geom. Appl. 2012.22:143-165. Downloaded om www.wo ldscien i ic.com
by UNIVERSITY OF SEVILLE on 01/25/16. Fo pe sonal use only.
Sep embe 11, 2012 9:30 WSPC/Guidelines S0218195912500021
Sepa abili y o Poin Se s by k-Le el Linea Classi ica ion T ees 163
Minimum-le el axis-pa allel ee algo i hm. The gene al p oblem consis s o compu -
ing a minimum-le el axis-pa allel ee o poin s Rand B, in gene al posi ion. We
can assume ha each o he ho izon al/ e ical lines de ining he ee pass h ough
he inpu poin s, R∪B; we conside a poin p ha lies on a ho izon al ( esp.,
e ical) line ℓ o lie in he (closed) egion o he le ( esp., below) ℓ.
Ou algo i hm employs dynamic p og amming. Le x1< x2<···< xndeno e
he x-coo dina es o he ninpu poin s R∪B, indexed in so ed o de ; simila ly,
le y1< y2<··· < yndeno e he y-coo dina es. A subp oblem is speci ied by a
ec angle, R= (xi, xj]×(yk, yl]. Thus, he e a e O(n4) subp oblems. The alue
o a subp oblem R, (R), is he minimum numbe o le els in an axis-pa allel
classi ica ion ee o he poin s o R∪Bwi hin R. I Ris monoch oma ic (i.e., has
poin s only o Ro only o Bwi hin i ), (R) = 0; his o ms he base case o he
dynamic p og amming ecu sion. In gene al, o subp oblem Rwe ha e
(R) = (0 i Ris monoch oma ic
1 + minℓmax{ (R≤ℓ), (R>ℓ)}o he wise,
whe e he minimiza ion is o e all ho izon al/ e ical cu s ℓ ha pass h ough
poin s o R∪Band in e sec R, and R≤ℓ( esp., R>ℓ) deno es he sub ec angle
o R ha is on o below/le ( esp., s ic ly abo e/ igh ) ho izon al/ e ical line ℓ.
The algo i hm abula es he alues (R) in o de o inc easing alues o j−iand
l−k, in he s anda d way. Since he e a e O(n) candida e cu s ℓ o conside o each
R, he o e all unning ime is O(n5), using a able o size O(n4). We hus conclude
wi h he ollowing heo em.
Theo em 7. A minimum-le el sepa a ing axis-pa allel ee o Rand Bcan be
compu ed in O(n5) ime, using O(n4)space.
Rema k. A minimum-le el sepa a ing ee using only e ical (o only ho izon al)
lines can easily be compu ed in O(nlog n) ime by conside ing colo ansi ions in
he x-so ed (y-so ed) lis o poin s R∪B.
6. Conclusion
We ha e ini ia ed a s udy o k-le el linea classi ica ion ees. Table 1summa izes
he ime and space complexi ies o he algo i hms p esen ed. (As we ema ked a e
Theo em 6, we no e ha he me hod we p esen ed o axis-pa allel 2- and 3-le el
ees can be ex ended o yield a linea (in n) ime algo i hm o any cons an
numbe , k, o le els, bu he dependence on kis p ohibi i e (O(22kn)).)
In u u e wo k, we hope o conside o he k-le el ees de ined by cu s o he han
lines o hype planes, e.g., ci cles o axis-aligned boxes; see Figu e 19. Mul ile el ees
based on sepa a ion by ci cles o axis-aligned boxes ha e po en ial applica ions in
bounding olume hie a chies, which a e use ul o in e sec ion de ec ion and shape
app oxima ion.
In . J. Compu . Geom. Appl. 2012.22:143-165. Downloaded om www.wo ldscien i ic.com
by UNIVERSITY OF SEVILLE on 01/25/16. Fo pe sonal use only.

Sep embe 11, 2012 9:30 WSPC/Guidelines S0218195912500021
164 E. M. A kin e al.
Table 1. Summa y o he ime and space complexi ies.
Classi ica ion ees Time Space
Zigzag Θ(nlog n)O(n)
2-le el ee O(n2)O(n2)
Minimum-le el ee (3 ≤k≤log n)nO(log n)nO(log n)
Axis-pa allel 2-le el ee O(n)O(n)
Axis-pa allel 3-le el ee O(n)O(n)
Minimum-le el axis-pa allel ee O(n5)O(n4)
c0c1
c2
(b)
(a)
B1
B2
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..........................................
........................................
R1
R2
s0
s1
s2
R1
B1
R2
B2
Fig. 19. Example o 2-le el ees based on (a) axis-aligned boxes and (b) ci cles.
Acknowledgmen s
We hank o wo anonymous e e ees o hei many use ul sugges ions and com-
men s, which helped imp o e he pape subs an ially.
Re e ences
1. E. M. A kin, F. Hu ado, J. S. B. Mi chell, C. Sea a and S. S. Skiena, Some lowe
bounds on geome ic sepa abili y p oblems, In . J. Compu . Geom. Appl. 16(1) (2006)
1–26.
2. E. M. A kin, F. Hu ado, J. S. B. Mi chell, C. Sea a and S. S. Skiena, Some sepa abili y
p oblems in he plane, Abs ac s o he 16 h Eu opean Wo kshop on Compu a ional
Geome y, Eila , Is ael (2000), pp. 51–54.
3. T. Asano, J. He shbe ge , J. Pach, E. Son ag, D. Sou aine and S. Su i, Sepa a ing bi-
ch oma ic poin s by pa allel lines, P oc. 2nd Canadian Con . Compu a ional Geome y
(1990), pp. 46–49.
4. M. de Be g, O. Cheong, M. an K e eld and M. O e ma s, Compu a ional Geome y:
Algo i hms and Applica ions, 3 d edn. (Sp inge -Ve lag, 2008).
5. G. B odal and R. Jacob, Dynamic plana con ex hull, P oc. 43 d Symp. Founda ions
o Compu e Science, IEEE Compu e Socie y (2002), pp. 617–626.
6. T. H. Co men, C. E. Leise son, R. L. Ri es and C. S ein, In oduc ion o Algo i hms
(MIT P ess, 2001).
7. G. Das and M. T. Good ich, On he complexi y o op imiza ion p oblems o con ex
polyhed a and decision ees, Compu . Geom.: Theo . Appl. 8(1997) 123–137.
8. H. Edelsb unne and F. P. P epa a a, Minimum polygonal sepa a ion, In o . Compu .
77 (1988) 218–232.
9. S. Feke e, On he complexi y o min-link ed-blue sepa a ion p oblem (1992).
In . J. Compu . Geom. Appl. 2012.22:143-165. Downloaded om www.wo ldscien i ic.com
by UNIVERSITY OF SEVILLE on 01/25/16. Fo pe sonal use only.
Sep embe 11, 2012 9:30 WSPC/Guidelines S0218195912500021
Sepa abili y o Poin Se s by k-Le el Linea Classi ica ion T ees 165
10. M. G igni, V. Mi elli and C. H. Papadimi iou, On he di icul y o designing good
classi ie s, SIAM J. Compu . 30(1) (2000) 318–323.
11. F. Hu ado, M. Mo a, P. A. Ramos and C. Sea a, Sepa abili y by wo lines and by
nea ly-s aigh polygonal chains, Disc . Appl. Ma h. 144 (2004) 110–122.
12. F. Hu ado, M. Noy, P. A. Ramos and C. Sea a, Sepa a ing objec s in he plane by
wedges and s ips, Disc . Appl. Ma h. 109 (2000) 109–138.
13. N. Megiddo, Linea - ime algo i hms o linea p og amming in R3and ela ed
p oblems, SIAM J. Compu . 12(4) (1983) 759–776.
14. F. P. P epa a a and M. I. Shamos, Compu a ional Geome y, An In oduc ion
(Sp inge -Ve lag, 1988).
In . J. Compu . Geom. Appl. 2012.22:143-165. Downloaded om www.wo ldscien i ic.com
by UNIVERSITY OF SEVILLE on 01/25/16. Fo pe sonal use only.