Separability of Point Sets by k-Level Linear Classification Trees

September 11, 2012 9:30 WSPC/Guidelines S0218195912500021 SEPARABILITY OF POINT SETS BY k-LEVEL LINEAR CLASSIFICATION TREES∗ ESTHER M. ARKIN Department of Applied Mathematics and Statistics, Stony Brook University Stony Brook, New York 11794, USA [email protected] DELIA GARIJO†and ALBERTO M´ ARQUEZ‡ Departamento de Matem´atica Aplicada I, Universidad de Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain †[email protected] ‡[email protected] JOSEPH S. B. MITCHELL Department of Applied Mathematics and Statistics, Stony Brook University Stony Brook, New York 11794, USA [email protected] CARLOS SEARA Departament de Matem`atica Aplicada II, Universitat Polit`ecnica de Catalunya Jordi Girona 1, 08034 Barcelona, Spain [email protected] Received 6 April 2011 Revised 9 January 2012 Communicated by Godfried Toussaint ABSTRACT Let Rand Bbe sets of red and blue points in the plane in general position. We study the problem of computing a k-level binary space partition (BSP) tree to classify/separate R and B, such that the tree defines a linear decision at each internal node and each leaf of the tree corresponds to a (convex) cell of the partition that contains only red or only blue points. Specifically, we show that a 2-level tree can be computed, if one exists, in ∗A preliminary version of this work appeared in the Abstracts of the 26th European Workshop on Computational Geometry, Dortmund (Germany), 2010, pp. 41–44. E. Arkin and J. Mitchell are partially supported by the National Science Foundation (CCF-0729019, CCF-1018388). D. Garijo and A. M´arquez are partially supported by project MTM2008-05866-C03-01. C. Seara is partially supported by projects MTM2009-07242, Gen. Cat. DGR2009GR1040, and the ESF EUROCORES programme EuroGIGA — ComPoSe IP04 — MICINN Project EUI-EURC-2011-4306. 143 Int. J. Comput. Geom. Appl. 2012.22:143-165. Downloaded from www.worldscientific.com by UNIVERSITY OF SEVILLE on 01/25/16. For personal use only. September 11, 2012 9:30 WSPC/Guidelines S0218195912500021 144 E. M. Arkin et al. time O(n2). We show that a minimum-level (3 ≤k≤log n) tree can be computed in time nO(log n). In the special case of axis-parallel partitions, we show that 2-level and 3-level trees can be computed in time O(n), while a minimum-level tree can be computed in time O(n5). Keywords: Red-blue separation; binary space partitions; classification; decision trees; machine learning. 1. Introduction Consider a set of npoints in the plane in general position. Each point is either “red” or “blue”. Let Rdenote the set of red points and let Bdenote the set of blue points. We study the separability of Rand Bby a k-level binary space partition tree. Specifically, a binary space partition tree Tis a rooted tree; each node of T corresponds to a (convex, polygonal) region of the plane, with each nonleaf node having an associated partition line, which partitions its corresponding region into the two regions corresponding to its children. The root of Tis associated with the entire plane; the root node is at level (or depth) 0. The children of the root node are at level 1; in general, nodes at level iare connected to the root by a (unique) path in Tof length i(i.e., having iedges). A k-level tree binary space partition tree T has nodes at levels {0,1,...,k}. The regions associated with the leaves of Tform a partition of the plane into convex polygons. We say that Rand Bare separated by a k-level binary space partition tree, T, if each region associated with the leaves of Tis monochromatic (i.e., contains only points of Ror only points of B). The separating k-level tree Tcorresponds to a recursive partitioning of the plane into disjoint convex regions using (up to) 2k−1 separating straight cuts. Such a tree Tof height k(i.e., with klevels) can be used as a classification tree for red/blue points; we can classify, in time O(k), a new point as “red” or “blue” based on the color associated with the cell (corresponding to a leaf in the tree) in which it is located. See Figure 1. Related work. Separability of point sets is fundamental to classification, clustering, and machine learning. The separating k-level tree generalizes simple separability criteria that have been previously studied. The most basic separability criteria for Rand Bis that of linear separability, which corresponds to a separating 1-level B1 B2 B2 B1R2 R1 R2 R1 q s/s ℓ1 ℓ0 ℓ1ℓ2 ℓ0 ℓ2 p q Fig. 1. A separating 2-level tree. Int. J. Comput. Geom. Appl. 2012.22:143-165. Downloaded from www.worldscientific.com by UNIVERSITY OF SEVILLE on 01/25/16. For personal use only. September 11, 2012 9:30 WSPC/Guidelines S0218195912500021 Separability of Point Sets by k-Level Linear Classification Trees 145 tree: There exists a line separating Rand B. Linear separability can be decided in linear time.13 For sets Rand Bthat are not linearly separable, generalizations include the following separability criteria: A strip (two parallel lines, partitioning the plane into three regions), a wedge (two rays with common origin, partitioning the plane into two regions), a double wedge (two intersecting lines), or three parallel lines. All of these criteria can be decided, and corresponding partitions computed, in optimal Θ(nlog n) time.1,2,11,12 (Note that if Rand Bare strip separable, then they are also wedge separable.) Strip, wedge, double-wedge, or three parallel lines separability criteria are special cases of separability by a 2-level tree. Separability by multiple parallel lines is a special case of separability by a k-level tree; in particular, m= 2k−1 parallel lines can be a associated with a (heightbalanced) k-level tree. The minimum number of parallel lines needed to separate Rand Bcan be computed in O(n2log n) time.2If Rand Bare the vertices of a regular n-gon, ⌊n/2⌋is a tight upper bound for the number of parallel lines, and, given the minimum number of separating lines, their common orientation can be computed in O(nlog n) time.3 Other separability criteria have also been studied. Given any disjoint point sets, Rand B, there always exists a separating polygonal chain, which can be computed in O(nlog n) time. Computing a minimum-link separating polygonal chain that turns alternatively left and right by a constant angle α≥π/2 can be done in O(nlog n) time.11 Separability by mparallel lines is a special case of separability by a monotone m-link polygonal chain. The problem of determining a minimumlink separating polygonal chain of Rand Bis NP-complete.9Edelsbrunner and Preparata8solved, in time O(nlog n), the special case of computing a minimumedge convex polygon separating Rand B(if a convex separator exists); their time bound was shown to be optimal in Arkin et al.1 Our motivation is to consider natural generalizations of previously studied separation and classification problems and, in particular, to consider classifiers that are very fast at query time. The speed of classification of a point with respect to a k-level classification tree is proportional to k; thus, we are motivated to determine classification trees having the minimum number of levels. Outline of the paper. We initiate the study of separability by k-level trees by considering first the special case of k= 2, separability by a 2-level tree. Section 2is devoted to a special case of 2-level separability, that of separability by a zigzag, which corresponds to 2-level tree partitioning such that monochromatic cells of the same color are adjacent (Figure 2). In Section 3we study the general version of 2level tree separability, including the generalizations to three or four distinct colors of point sets (instead of just two, red and blue). In Section 4we consider k-level tree separability and possible configurations of points with O(log n)-level trees. Section 5 is devoted to separability by k-level trees whose partitioning cuts are axis-parallel. (Such trees and partitions are closely related to kd-tree data structures, which are useful for various types of range queries; see de Berg et al.,4chapter 5.) Int. J. Comput. Geom. Appl. 2012.22:143-165. Downloaded from www.worldscientific.com by UNIVERSITY OF SEVILLE on 01/25/16. For personal use only. September 11, 2012 9:30 WSPC/Guidelines S0218195912500021 146 E. M. Arkin et al. 2. Zigzag Separability In this section we consider the zigzag separability problem: Determine whether the sets Rand Bare separable by a zigzag Z= (ℓ1, s, ℓ2), that is a simple, nonconvex 3-link polygonal chain formed by two rays ℓ1,ℓ2and a segment sjoining the origins of the rays (Figure 2). Let ℓsbe the line containing the segment s, and let ℓ′ 1(ℓ′ 2) be the line containing the ray ℓ1(ℓ2). Let CH(X) denote the convex hull of a point set X. We can assume that the simpler known special cases of separability have already been tested; specifically, we assume that Rand Bare not separable by a line, strip, wedge, or convex polygonal chain, each of which can be decided in O(nlog n) time. Thus, under this condition, the following lemma is straightforward. B1 B2 B2 B1R2 R1 R2 R1 q s/s ℓ1 ℓ1ℓ2 ℓ2 s ℓs ℓs ...................................................... Fig. 2. A separating zigzag. Lemma 1. Let Rand Bbe zigzag separable but not separable by a convex polygon. Then, CH(R)contains at least one blue point, and CH(B)contains at least one red point. There are three types of zigzags depending on the values of the angles αand β formed by ℓsand ℓ1, and by ℓsand ℓ2, respectively (Figure 3). A separating zigzag Z= (ℓ1, s, ℓ2) defines four wedges that partition Rinto R1and R2, and Binto B1 and B2, all four subsets are non-empty, since Rand Bare not wedge separable. Since separating zigzags are not necessarily unique, we make the choice specific by considering two optimal separating zigzags: Either a zigzag maximizing min{α, β}, called the most convex separating zigzag (approximating linear separability), or a zigzag that minimizes max{α, β}(approximating separability by three parallel lines). Lemma 2. Let Z= (ℓ1, s, ℓ2)be the most convex separating zigzag for Rand B. Then each of the two rays, and the segment of Zpass through two points of different colors. Moreover, either ℓ′ 1is an inner common tangent line of CH(R2) and CH(B), or ℓ′ 2is an inner common tangent line of CH(B2)and CH(R). Proof. The key idea is to stretch the separating zigzag until each part of the structure touches two points of different colors. Moreover, for each of the types of zigzag in Figure 3, either ℓ′ 2intersects ℓ1or ℓ′ 1intersects ℓ2. In the first case ℓ′ 1is an Int. J. Comput. Geom. Appl. 2012.22:143-165. Downloaded from www.worldscientific.com by UNIVERSITY OF SEVILLE on 01/25/16. For personal use only. September 11, 2012 9:30 WSPC/Guidelines S0218195912500021 Separability of Point Sets by k-Level Linear Classification Trees 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≤α, β < π. inner common tangent line of CH(R2) and CH(B), and in the second case ℓ′ 2is an inner common tangent line of CH(B2) and CH(R). Notice that both statements hold if ℓ′ 1and ℓ′ 2are parallel. Let IX,Y be the number of intersections between pairs of edges of the convex hulls of two point sets Xand Y. Lemma 3. Let Rand Bbe zigzag separable. Then IR,B ∈ {0,2,4,6}. Proof. Because the convex hulls are closed Jordan curves, IR,B is even. If CH(R) and CH(B) are nested polygons, IR,B = 0 (Figure 4(a)). Assume that IR,B ≥2. By Lemma 2, either CH(B) intersects CH(R1) but not CH(R2), or CH(R) intersects CH(B1) but not CH(B2). Moreover, CH(R1) and CH(B) are wedge separable; thus, IR1,B ≤4. Analogously, IB1,R ≤4 (Figures 4and 5). Since CH(R) = CH(R1∪R2), there are two bridge-edges between CH(R1) and CH(R2). An analogous statement holds for CH(B1) and CH(B2). Hence, IR,B ≤4 + 2 = 6, corresponding to the at most six alternations of colors in CH(B∪R) (Figure 5). Let RI(BI) be the subset of red (blue) interior points of CH(B) (CH(R)). By Lemma 1,|RI| ≥ 1 and |BI| ≥ 1. If IR,B = 6, let R′ 1,R′ 2, and R′ 3(B′ 1,B′ 2, and B′ 3) be the three disjoint subsets of red points (blue points) that are not contained in CH(B) (CH(R)) defined according to the 6 intersections of the edges of CH(B) and CH(R). These eight subsets and their respective convex hulls can be computed in O(nlog n) time (Figure 5). Lemma 4. Let Z= (ℓ1, s, ℓ2)be the most convex separating zigzag of Rand B. Then ℓsis a supporting line of some of the following eight convex polygons: CH(RI), CH(BI),CH(R′ 1),CH(R′ 2),CH(R′ 3),CH(B′ 1),CH(B′ 2), and CH(B′ 3). Proof. We first prove that either RIis separable from Bby the wedge (ℓs, ℓ2), or BIis separable from Rby the wedge (ℓ1, ℓs), and both cases do not always occur (Figures 4(a) and 4(c)). By Lemma 2, if R2and Bare line separable, then R1is Int. J. Comput. Geom. Appl. 2012.22:143-165. Downloaded from www.worldscientific.com by UNIVERSITY OF SEVILLE on 01/25/16. For personal use only. September 11, 2012 9:30 WSPC/Guidelines S0218195912500021 148 E. M. Arkin et 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. Subsets of red and blue points for IR,B = 6. separable from Bby the wedge (ℓs, ℓ2), and so RI⊆R1is separable from Bby the same wedge. By analogous reasoning, if B2and Rare line separable, then BIand Rare wedge separable. If IR,B ∈ {0,2,4}, then ℓsis a supporting line of CH(RI), because, otherwise, there are not red points inside CH(B) and then Bis wedge separable from R, since Zis the most convex separating zigzag. Analogously, if B2and Rare line separable and IR,B ∈ {0,2,4}, then ℓsis a supporting line of CH(BI). Assume that IR,B = 6 and recall the second statement of Lemma 2. Let firstly assume that R2is line separable from B, and ℓsis not a supporting line of CH(RI). One of the subsets R′ 1,R′ 2,R′ 3has to be R2(say, R′ 3=R2) because, by convexity of CH(B), ℓ′ 1does not separate two of these subsets from CH(B). Thus, R′ 1and R′ 2are contained in R1and, since ℓsis not a supporting line of CH(RI), then ℓsis a supporting line of either CH(R′ 1) or CH(R′ 2) (Figure 5). We can proceed analogously, if we assume that B2and Rare line separable, IR,B = 6, and ℓsis not a supporting line of CH(BI). Lemma 4provides the key tool to design the following O(nlog n) time algorithm for computing a separating zigzag Z= (ℓ1, s, ℓ2) for Rand B(if it exists). The algorithm looks for ℓsand checks the linear separability of CH(R2) and CH(B1) by ℓ′ 1and the linear separability of CH(R1) and CH(B2) by ℓ′ 2. There are a linear number of candidates ℓsthat are supporting lines of the eight convex polygons above. Int. J. Comput. Geom. Appl. 2012.22:143-165. Downloaded from www.worldscientific.com by UNIVERSITY OF SEVILLE on 01/25/16. For personal use only. September 11, 2012 9:30 WSPC/Guidelines S0218195912500021 Separability of Point Sets by k-Level Linear Classification Trees 149 Zigzag-algorithm Input: Point sets R(red) and B(blue) Output: A separating zigzag Z= (ℓ1, s, ℓ2), or report that none exists (1) Compute CH(R), CH(B), RI,BI,CH(RI), CH(BI), and IB,R. Check whether IR,B ∈ {0,2,4,6}, and compute the intersecting edges of CH(R) and CH(B). Check that CH(RI) or CH(BI) is monochromatic. For RI={r1}and BI={b1}, do as follows: If r1∈CH(R) and b1∈CH(B), then Rand B are zigzag separable as shows Figure 6(a) and it is easy to see how to compute the separating zigzag. Analogously if r1∈CH(R) and b1is interior to CH(B) or vice versa (Figure 6(b)). From now on, assume that |RI| ≥ 2 or |BI| ≥ 2. r1 b1 b1 r1 (a) (b) Fig. 6. Zigzag separability with |RI|= 1 and |BI|= 1. (2) Let Pbe any of the polygons: CH(RI), CH(BI), CH(R′ 1), CH(R′ 2), CH(R′ 3), CH(B′ 1), CH(B′ 2), or CH(B′ 3), with their interior points. Do the following: (a) Sort the points in (R∪B)−Pby a counterclockwise rotational sweep over Pwith an oriented supporting line ℓsaccording to Lemma 4. (b) Do a second rotational sweep over P. Each time ℓsencounters a red or blue point of (R∪B)−P, maintain and update the convex hulls CH(R2), CH(B1) (CH(R1), CH(B2)) of the red and blue points on the left (right) side of ℓsin O(log n) time.14 In O(log n) time, check the linear separability between CH(R2) and CH(B1), and between CH(R1) and CH(B2), and compute their respective inner common tangent lines (Figure 7). In the affirmative case, a separating zigzag is found. Analysis of the algorithm. Each step can be done in O(nlog n) time. In step 2, a rotational sweep is done over eight different convex polygons, spending O(nlog n) time on each. To prove the Ω(nlog n) time lower bound for deciding the zigzag separability, we reduce the strip separability problem1to the zigzag separability problem. The reader is referred to Arkin et al.1for the construction of the reduction. We place red and blue points on two concentric circles with appropriate radii. A modification from the construction in Arkin et al.1is needed: We place blue points around the smaller, unit-radius circle and red points around a larger circle of radius d > 1, and two additional red points, r1and r2, as in Figure 8. (Specifically, radius dis Int. J. Comput. Geom. Appl. 2012.22:143-165. Downloaded from www.worldscientific.com by UNIVERSITY OF SEVILLE on 01/25/16. For personal use only. September 11, 2012 9:30 WSPC/Guidelines S0218195912500021 150 E. M. Arkin et al. ℓ1 B1 R2 ℓs ℓ2 B2 R1 ........................................................................................................... ................... . . . ...... ................................... . .. .. . .. .......................... . . . . . . . . ....... . . . . . . . . . . . . .......... ............................................ . . . . .. . . . . . . . . . . .................................. ...... . . . . . .. . . . . . . . . . ... . .. .. . . . ...................... ......................... Fig. 7. Supporting lines between monochromatic convex hulls. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ................. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . b1 b2 ǫ a 2ad ǫ r1 r2 Fig. 8. Construction for the lower bound for zigzag separability. selected so that a gap of size ǫbetween two consecutive blue points on the unit circle determines a line, ℓ, through these two points, and a line, ℓ′, through the symmetric pair of blue points, such that ℓand ℓ′pass through the corresponding red points on the circle of radius d(Figure 8). Letting adenote the distance from the origin to ℓ or ℓ′, an appropriate choice of dis d= 2a/ǫ =√4−ǫ2 ǫ.) Additionally, we place two blue points, b1and b2, far enough away from the larger circle, at positions indicated in Figure 8. Now it is clear that there exists a separating zigzag of the sets of red and blue points if and only if the same sets of red and blue points without b1and b2are strip separable. The last statement is reduced to determining whether there exist two consecutive blue points in the first quadrant of the smallest circle, such that their Euclidean distance is greater than a given ǫ > 0, specified in the input of the problem. Theorem 1. Computing a separating zigzag for Rand Brequires Θ(nlog n)time. Remark. An O(n3log n) time algorithm for determining the separability of Rand Bby a monotone (with respect to some direction) (k≤7)-polygonal chain is as follows: A mid-segment of the polygonal chain is defined by a line ℓgoing through two points. Then, we apply an O(nlog n) time algorithm for the line, wedge or zigzag separability of the point subsets on both sides of ℓ. Int. J. Comput. Geom. Appl. 2012.22:143-165. Downloaded from www.worldscientific.com by UNIVERSITY OF SEVILLE on 01/25/16. For personal use only. September 11, 2012 9:30 WSPC/Guidelines S0218195912500021 Separability of Point Sets by k-Level Linear Classification Trees 151 3. Separability by a 2-Level Tree We turn now to the problem of computing a separating 2-level tree T= (ℓ1, ℓ0, ℓ2) for Rand B, where ℓ0,ℓ1, and ℓ2are the oriented line, the ray on the left side of ℓ0, and the ray on the right side of ℓ0, respectively (recall Figure 1). Let ℓ′ 1(ℓ′ 2) be the line containing ℓ1(ℓ2). Denote by m(ℓ) the slope of ℓ. Let p(q) be the intersection point of ℓ0and ℓ1(ℓ2). Tsplits the plane into four convex regions. Recall that R and Bare separated by a 2-level tree if there exists a partition of R∪Binto four monochromatic subsets and a 2-level tree, T, whose partition of the plane respects the partition of R∪B. Criteria. The following criteria provide a systematic classification of possible separating 2-level trees: (1) m(ℓ0)>0, m(ℓ0)<0, or ℓ0is horizontal or vertical. (2) Relative position of pand qalong ℓ0:pqor qp. (3) Slopes of ℓ1and ℓ2with respect to ℓ0. (4) Different color assignments to the convex regions. Classification. We do case analysis according to the following classification criteria: (1) The slope of ℓ0: We only consider the m(ℓ0)≥0 case; the case in which m(ℓ0)<0 can be analyzed by rotating the configuration by 90 degrees and applying the corresponding m(ℓ0)>0 case. The first row of Figure 9illustrates all possible cases for m(ℓ0)≥0 according to the different relative positions of the rays ℓ1and ℓ2. (2) The relative position of pand q: We only study the case qp. By applying symmetry with respect to a vertical line, followed by a 90-degree rotation, we obtain the case pq; this is seen by comparing the second row with the first row in Figure 9. (3) If two regions that are consecutive (in the order in which the circle at infinity meets the regions) have the same color, the configuration corresponds to one of the following special cases: Linear, zigzag (p6=q), or wedge separability (p=q), each of which can be solved in Θ(nlog n) time.1,11,12 Thus, we assume that the colors alternate, ℓ0has nonnegative slope, and qp. For an easier analysis of the point configurations for the design of algorithms, we expand the four cases for qpin the first row of Figure 9(from left to right) into the seven cases in Figure 10 as follows: The first case is just the case (a) of Figure 10; the second case is expanded into the cases (b) and (c) in Figure 10 according to the slope of ℓ1; the third case is expanded into the 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. Int. J. Comput. Geom. Appl. 2012.22:143-165. Downloaded from www.worldscientific.com by UNIVERSITY OF SEVILLE on 01/25/16. For personal use only. September 11, 2012 9:30 WSPC/Guidelines S0218195912500021 158 E. M. Arkin et al. (b) Starting at b′ nand following the order above, in O(n) time compute the location of the blue points in ℓ+ nor ℓ− n. Let b′ ibe the last blue point in ℓ+ n∩ℓ− R. If there exists an appropriate bipartition {B1, B2}, then {b′ i, b′ i−1, . . . , b′ 1} ⊆ B2. (c) Let B1={b′ n,...,b′ i+1}and B2={b′ i, b′ i−1,...,b′ 1}. By construction, R1 and B1are line separable by ℓn. In O(n) time, check if R2and B2are line separable, and if R1∪B1is line separable from R2∪B2. Otherwise, there does not exist a separating 2-level tree for the bipartition {R1, R2}. In the affirmative case, construct a separating 2-level tree Tfor Rand B. B1B2 CH(R1) ℓn ℓ+ n ℓ− n b′ n CH(R2) b′ 1 ....................... ℓR ℓ+ R ℓ− R . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... .... ... .... .... ... .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Fig. 15. Illustrating step 3 of the algorithm for a 2-level tree of type (2). Theorem 2. Computing all of the separating 2-level trees for Rand Bcan be done in O(n2)time and space. Proof. The algorithm above spends O(n2) time and space constructing the dual arrangement A. For each partition {R1, R2}of R, the algorithm decides whether there exists a separating 2-level tree and computes it in O(n) time. Lemma 8ensures the existence of an appropriate bipartition of Rat some step, if there exists a separating 2-level tree for Rand B. By Lemma 6we can assume that ℓis a supporting line of CH(R1) and proceed analogously for ℓbeing a supporting line of CH(R2). By the same lemma we can assume that ℓnis a supporting line of CH(R1) and CH(B1). Remark. It is easy to see that all of the combinatorially different 2-level trees for a set of nred and blue points in Rdcan be computed in O(nd+1) time. For d= 2, the above theorem shows that an improved time bound of O(n2) is possible. It remains an open problem to determine if a separating 2-level tree for Rand Bcan be computed in o(n2) time. Int. J. Comput. Geom. Appl. 2012.22:143-165. Downloaded from www.worldscientific.com by UNIVERSITY OF SEVILLE on 01/25/16. For personal use only. September 11, 2012 9:30 WSPC/Guidelines S0218195912500021 Separability of Point Sets by k-Level Linear Classification Trees 159 3.2. Three or four colored point sets The 2-level tree problem for point sets having three or four distinct colors can be solved as follows. The four colors case can be solved in O(n) time by checking the linear separability between pairs of point sets. The three colors case, with point sets R,Band G, can be viewed either as a zigzag of Rand G∪B, or as a separation with a 2-level tree of Rand G∪Brestricted to have linear separability between G and B(Figure 16). But, in both cases, we have as additional information the linear separability of Gand B, which can be checked in advance in O(n) time. We use this information to compute the corresponding 2-level tree. Thus, this problem can be solved in O(nlog n) time. This time bound is optimal, as can be seen from the zigzag separability for R,Band G, with an easy adaptation of the lower bound construction in Theorem 1. R1 R2 B G Y R B G R1 R2 B G Fig. 16. 2-level trees for three and four colored point sets. Theorem 3. A separating 2-level tree for three-colored sets of npoints can be computed in O(nlog n)time, which is worst-case optimal. For four-colored sets of npoints a 2-level tree can be computed in O(n)time. 4. k-Level Trees We now consider separating (k≥3)-level trees for Rand B. A separating O(log n)- level tree for Rand Bcan be computed as follows: Appealing to the Ham-Sandwich theorem, we can compute a line that gives an equitable bipartition B1∪R1,B2∪R2 of B∪R, then proceed recursively on each part until we obtain monochromatic subsets. In the end, we obtain a k-level tree for n≤2kpoints. Note that a k-level tree produces a subdivision of the plane into monochromatic convex cells, each one bounded by at most klines. We can use a dynamic programming algorithm to compute a minimum-level tree for Rand Bin (quasi-polynomial) nO(log n)time. In particular, a subproblem is specified by a convex polygon Phaving at most k=O(log n) sides, each defined by one of the n 2lines determined by point pairs of R∪B. The optimization for a subproblem selects among the ≤n 2 possible cuts, ℓ, and recursively solves the minimum-level tree problem on each side of ℓ. Theorem 4. A separating k-level tree for Rand Bexists with k≤ ⌈log n⌉. Furthermore, a minimum-level tree can be computed in nO(log n)time. Int. J. Comput. Geom. Appl. 2012.22:143-165. Downloaded from www.worldscientific.com by UNIVERSITY OF SEVILLE on 01/25/16. For personal use only. September 11, 2012 9:30 WSPC/Guidelines S0218195912500021 160 E. M. Arkin et al. On the other hand, there exist configurations of points for which the depth k∗of a minimum-level tree is Ω(log n). In particular, let Sbe a set of npoints in general position. Replace each point pi∈Sby a structure of four (very close) points, two red and two blue, as in Figure 17, obtaining the sets Rand Bof 2nred and 2nblue points, respectively. Any k-level tree for Rand Bhas to separate each pair of red and blue points of the pistructure and must, therefore, have k= Ω(log n) levels. j pi pi p1p2pn pi 6 O(log n) Fig. 17. An example (left) of a configuration of R∪Brequiring an Ω(log n)-level separating tree. It is unlikely that a substantially more efficient algorithm exists for computing separating k-level trees in general. In fact, in related work, Grigni et al.10 considered the problem of designing a near-optimal linear decision tree Tto classify two given point sets Rand Bin Rn, so that Tdefines a linear decision at each internal node, such that for each leaf vof T, either only red or only blue points lead the algorithm to v. The authors considered two measures of such a classifier, the number of internal nodes and the depth of the tree, and prove a very strong negative result on highdimensional classification trees: Unless NP=ZPP, no polynomial-time algorithm for optimizing the depth of a classifier can have approximation ratio better than any fixed constant. Further, Das and Goodrich7showed that the following problem is NP-complete: Given a set Sof npoints in R3, partitioned into two concept classes, red and blue, decide if there exists a decision tree Twith at most knodes that separates the red points from the blue points. 5. Separability with Axis-Parallel Partitions In this section, we consider k-level trees defined by axis-parallel lines. First we show how to compute a 2-level tree as in Figure 18(a). We consider the case in which ℓ0is vertical and ℓ1,ℓ2are horizontal; other cases, which also depend on the color assigned to the rectangles produced by the 2-level tree structure, can be handle analogously. A key observation is that, if there exists a separating 2-level tree, then during a sweep with a vertical line ℓfrom left to right the sets of red and blue points on the left of ℓmust be separable by a horizontal line at least until the moment when ℓreaches ℓ0. This observation is utilized in the following O(n) time algorithm. Axis-parallel 2-level tree algorithm. Let T(n) denote the running time for an input of size n. First, compute (in O(n) time6) the median Mof the x-coordinates of the points. Let ℓbe the vertical line through M. Let R1and B1(resp., R2and B2) be the Int. J. Comput. Geom. Appl. 2012.22:143-165. Downloaded from www.worldscientific.com by UNIVERSITY OF SEVILLE on 01/25/16. For personal use only. September 11, 2012 9:30 WSPC/Guidelines S0218195912500021 Separability of Point Sets by k-Level Linear Classification Trees 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-parallel 2-level tree, (b) and (c) axis-parallel 3-level trees. subsets of red and blue points on the left (resp., right) side of ℓ. Check, in time O(n), whether R1and B1(resp., R2and B2) are line separable with a horizontal line. If the two answers are negative, the algorithm concludes that there is no separating 2level tree. If the two answers are positive, the algorithm concludes with a separating 2-level tree, with ℓ0=ℓ. Otherwise, assume that the positive answer is on the left of ℓ; compute and store the y-interval of horizontal separators for points (R1,B1) left of ℓ. Now, proceed recursively, in time T(n/2), for the n/2 points on the right of ℓ. Specifically, we compute the median M′of the x-coordinates of the points in R2∪B2, and determine the y-interval of horizontal separators (if any exist) for the red and blue points of R2∪B2on each side of a vertical line, ℓ′, through M′, intersecting the y-interval for points in R2∪B2left of ℓ′with the y-interval for points (R1∪B1) left of ℓ. The recursive search continues, either on the left or on the right of each successive median vertical line, according to the existence of horizontal separators (recursing on the side that has no separator). The search concludes when we discover a vertical separator such that there either exist horizontal separators on both sides (yielding the desired 2-level separating tree), or we discover that there is no possible horizontal separator on both sides (showing that no 2-level separating tree exists). The running time, T(n), satisfies T(n) = T(n/2)+O(n), implying that T(n) = O(n). Theorem 5. A separating axis-parallel 2-level tree for Rand Bcan be computed in O(n)time. Acrossing 2-level tree is a 2-level tree for Rand Bdefined by two axis-parallel perpendicular lines (p=q). A separating crossing 2-level tree is also a separating horizontal/vertical double-wedge for Rand B. In Arkin et al.,1the authors showed an Ω(nlog n) time lower bound for the horizontal/vertical double-wedge separability problem; this lower bound applies also to the crossing 2-level tree problem. An O(nlog n) time algorithm for the separability by a crossing 2-level tree can be obtained by first sorting the points of R∪Bby both xand y-coordinate and then applying an easy modification of the linear-time algorithm above. Int. J. Comput. Geom. Appl. 2012.22:143-165. Downloaded from www.worldscientific.com by UNIVERSITY OF SEVILLE on 01/25/16. For personal use only. September 11, 2012 9:30 WSPC/Guidelines S0218195912500021 162 E. M. Arkin et al. Axis-parallel 3-level tree algorithm. A key observation is that if there exists a 3-level tree for Rand Bwith a configuration as in Figure 18(b), then for any vertical line ℓ0crossing the axis-parallel bounding box of R∪B, either (i) the subset of points of R∪Bon the left of ℓ0is separable by a 2-level tree or (ii) the subset of points of R∪Bon the right of ℓ0is separable by a 2-level tree. Thus, analogous to the search described above for the 2-level tree problem, we can do a binary search for a possible vertical line ℓ0such that both subsets of points of R∪Bon the left and on the right of ℓ0are separable by a 2-level tree, or the conclusion that no such ℓ0exists. The result is an O(nlog n) time algorithm. (Other configurations, as in Figure 18(c), can be handled analogously.) We now show, however, that there is a linear-time algorithm for the axis-parallel 3-level tree problem. Consider the case in Figure 18(b); other cases are similar. In O(n) we compute the vertical line ℓ′ 3containing the ray ℓ3using the median technique above such that the points on the left of ℓ′ 3are separable by a horizontal line (say, ℓ′ 1); we also compute a vertical interval I1where this horizontal line ℓ′ 1can be located. Then we proceed analogously (using the median technique) with the points on the right of the computed ℓ′ 3until we find a vertical line ℓ′ 4containing a ray ℓ4 such that the points between ℓ′ 3and ℓ′ 4are monochromatic, spending O(n) time in this second process. Then we proceed analogously with the points on the right of ℓ′ 4until we find a vertical line ℓ0such that the points between ℓ′ 4and ℓ0are separable by a horizontal line located in the computed vertical interval I1; again we spend O(n) time in this third process. Thus, the computation of the line ℓ0 and the 2-level tree on the left of ℓ0takes O(n) time. Similarly, in additional O(n) time we check that the points on the right of the computed ℓ0are separable by a 2-level tree. Notice that depending on the vertical/horizontal choices for ℓ0,ℓ1,ℓ2,ℓ3,ℓ4, ℓ5,ℓ6, and the colors assigned to each region, the number of different types of axis-parallel 3-level trees is 223−1. So the overall algorithm takes O(n) time. Theorem 6. A separating axis-parallel 3-level tree for Rand Bcan be computed in O(n)time. Remark. The linear-time method for determining the existence of an axis-parallel 3-level tree implies that, using the binary search previously discussed, we can solve the 4-level tree problem in time O(nlog n), and, more generally, the k-level tree problem in time O(nlogk−3n), for fixed k, with a huge dependence on khidden in the big-Oh notation. In fact, the linear-time method we gave for 3-level trees can be extended to 4 or more levels, yielding a linear-time method for any fixed k; however, the dependence on kreflects the fact that there are 22k−1k-level trees, leading to a very high (O(22kn)) time bound in terms of nand k. Below, we obtain polynomial time in both nand kfor computing a minimum-level axis-parallel tree, using dynamic programming. Int. J. Comput. Geom. Appl. 2012.22:143-165. Downloaded from www.worldscientific.com by UNIVERSITY OF SEVILLE on 01/25/16. For personal use only. September 11, 2012 9:30 WSPC/Guidelines S0218195912500021 Separability of Point Sets by k-Level Linear Classification Trees 163 Minimum-level axis-parallel tree algorithm. The general problem consists of computing a minimum-level axis-parallel tree for points Rand B, in general position. We can assume that each of the horizontal/vertical lines defining the tree pass through the input points, R∪B; we consider a point pthat lies on a horizontal (resp., vertical) line ℓto lie in the (closed) region to the left (resp., below) ℓ. Our algorithm employs dynamic programming. Let x1< x2<···< xndenote the x-coordinates of the ninput points R∪B, indexed in sorted order; similarly, let y1< y2<··· < yndenote the y-coordinates. A subproblem is specified by a rectangle, R= (xi, xj]×(yk, yl]. Thus, there are O(n4) subproblems. The value of a subproblem R,f(R), is the minimum number of levels in an axis-parallel classification tree of the points of R∪Bwithin R. If Ris monochromatic (i.e., has points only of Ror only of Bwithin it), f(R) = 0; this forms the base case for the dynamic programming recursion. In general, for subproblem Rwe have f(R) = (0 if Ris monochromatic 1 + minℓmax{f(R≤ℓ), f(R>ℓ)}otherwise, where the minimization is over all horizontal/vertical cuts ℓthat pass through points of R∪Band intersect R, and R≤ℓ(resp., R>ℓ) denotes the subrectangle of Rthat is on or below/left (resp., strictly above/right) horizontal/vertical line ℓ. The algorithm tabulates the values f(R) in order of increasing values of j−iand l−k, in the standard way. Since there are O(n) candidate cuts ℓto consider for each R, the overall running time is O(n5), using a table of size O(n4). We thus conclude with the following theorem. Theorem 7. A minimum-level separating axis-parallel tree for Rand Bcan be computed in O(n5)time, using O(n4)space. Remark. A minimum-level separating tree using only vertical (or only horizontal) lines can easily be computed in O(nlog n) time by considering color transitions in the x-sorted (y-sorted) list of points R∪B. 6. Conclusion We have initiated a study of k-level linear classification trees. Table 1summarizes the time and space complexities of the algorithms presented. (As we remarked after Theorem 6, we note that the method we presented for axis-parallel 2and 3-level trees can be extended to yield a linear (in n) time algorithm for any constant number, k, of levels, but the dependence on kis prohibitive (O(22kn)).) In future work, we hope to consider other k-level trees defined by cuts other than lines or hyperplanes, e.g., circles or axis-aligned boxes; see Figure 19. Multilevel trees based on separation by circles or axis-aligned boxes have potential applications in bounding volume hierarchies, which are useful for intersection detection and shape approximation. Int. J. Comput. Geom. Appl. 2012.22:143-165. Downloaded from www.worldscientific.com by UNIVERSITY OF SEVILLE on 01/25/16. For personal use only. September 11, 2012 9:30 WSPC/Guidelines S0218195912500021 164 E. M. Arkin et al. Table 1. Summary of the time and space complexities. Classification trees Time Space Zigzag Θ(nlog n)O(n) 2-level tree O(n2)O(n2) Minimum-level tree (3 ≤k≤log n)nO(log n)nO(log n) Axis-parallel 2-level tree O(n)O(n) Axis-parallel 3-level tree O(n)O(n) Minimum-level axis-parallel tree O(n5)O(n4) c0c1 c2 (b) (a) B1 B2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .......................................... ........................................ R1 R2 s0 s1 s2 R1 B1 R2 B2 Fig. 19. Example of 2-level trees based on (a) axis-aligned boxes and (b) circles. Acknowledgments We thank to two anonymous referees for their many useful suggestions and comments, which helped improve the paper substantially. References 1. E. M. Arkin, F. Hurtado, J. S. B. Mitchell, C. Seara and S. S. Skiena, Some lower bounds on geometric separability problems, Int. J. Comput. Geom. Appl. 16(1) (2006) 1–26. 2. E. M. Arkin, F. Hurtado, J. S. B. Mitchell, C. Seara and S. S. Skiena, Some separability problems in the plane, Abstracts of the 16th European Workshop on Computational Geometry, Eilat, Israel (2000), pp. 51–54. 3. T. Asano, J. Hershberger, J. Pach, E. Sontag, D. Souvaine and S. Suri, Separating bichromatic points by parallel lines, Proc. 2nd Canadian Conf. Computational Geometry (1990), pp. 46–49. 4. M. de Berg, O. Cheong, M. van Kreveld and M. Overmars, Computational Geometry: Algorithms and Applications, 3rd edn. (Springer-Verlag, 2008). 5. G. Brodal and R. Jacob, Dynamic planar convex hull, Proc. 43rd Symp. Foundations of Computer Science, IEEE Computer Society (2002), pp. 617–626. 6. T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms (MIT Press, 2001). 7. G. Das and M. T. Goodrich, On the complexity of optimization problems for convex polyhedra and decision trees, Comput. Geom.: Theor. Appl. 8(1997) 123–137. 8. H. Edelsbrunner and F. P. Preparata, Minimum polygonal separation, Infor. Comput. 77 (1988) 218–232. 9. S. Fekete, On the complexity of min-link red-blue separation problem (1992). Int. J. Comput. Geom. Appl. 2012.22:143-165. Downloaded from www.worldscientific.com by UNIVERSITY OF SEVILLE on 01/25/16. For personal use only. September 11, 2012 9:30 WSPC/Guidelines S0218195912500021 Separability of Point Sets by k-Level Linear Classification Trees 165 10. M. Grigni, V. Mirelli and C. H. Papadimitriou, On the difficulty of designing good classifiers, SIAM J. Comput. 30(1) (2000) 318–323. 11. F. Hurtado, M. Mora, P. A. Ramos and C. Seara, Separability by two lines and by nearly-straight polygonal chains, Discr. Appl. Math. 144 (2004) 110–122. 12. F. Hurtado, M. Noy, P. A. Ramos and C. Seara, Separating objects in the plane by wedges and strips, Discr. Appl. Math. 109 (2000) 109–138. 13. N. Megiddo, Linear-time algorithms for linear programming in R3and related problems, SIAM J. Comput. 12(4) (1983) 759–776. 14. F. P. Preparata and M. I. Shamos, Computational Geometry, An Introduction (Springer-Verlag, 1988). Int. J. Comput. Geom. Appl. 2012.22:143-165. Downloaded from www.worldscientific.com by UNIVERSITY OF SEVILLE on 01/25/16. For personal use only.