Measuring the error of linear separators on linearly inseparable data

Measuring the error of linear separators on linearly inseparable data Boris Aronov ∗Delia Garijo †Yurai N´u˜nez-Rodr´ıguez‡David Rappaport § Carlos Seara ¶Jorge Urrutiak Abstract Given a set of red points Rand blue points Bwe seek to determine a linear separator of the sets, although the sets may be linearly inseparable. Thus we obtain a partition into two parts, where each part may contain some misclassified points. We determine the error of the partition based on the amount of work needed to move the misclassified points. We consider several different measures of work and provide algorithms to find linear separators that minimize the error under these different measures. 1 Introduction Let R={r1, . . . , rp}be a set of pred points and B={b1, . . . , bq}a set of qblue points in Rd. Let n=p+qand assume that the points are disjoint and in general position, that is, no d+1 of the points lie in the same hyperplane in Rd. We say that Rand Bare linearly separable if there is a hyperplane, a linear separator, that partitions Rdsuch that each part contains only red or only blue points. If there is no linear separator for Rand B, then we say that the sets are linearly inseparable. Given sets R and Bwe attempt to find a linear separator, and if no such separator exists we would like to produce an approximate separator with the “best” approximation. The notion of “best” is left intentionally informal as the precise properties that should be optimized are application dependent. In this paper we will examine several different criteria for choosing an approximate separator. Let P={p1, . . . , pn}=R∪B. Let Hdenote a hyperplane which misclassifies Pand partitions P into two non-empty subsets. It will be useful to call one of the subsets the left subset and say that red points in it are well classified and blue points in it are misclassified. This language is hardly a loss of generality as we can always just label the majority color in some side red, and name that side the left side. The other subset is refereed to as right and plays a complementary role. Given Pand H we may be left with a set, Ξ, the subset of Pthat is misclassified by H, that is, His an approximate separator. We use s(H) to represent the quality of Has an approximate separator, a cost of H. Our goal is to find a hyperplane that minimizes the cost under one of the following assumptions. 1. s(H) is the maximum Euclidean distance from Hto a point in Ξ: MinMax criterion. 2. s(H) is the sum of the Euclidean distances from Hto every point in Ξ: MinSum criterion. 3. s(H) is the sum of squares of the Euclidean distances from Hto every point in Ξ: MinSum2 criterion. 4. s(H) is simply the cardinality of Ξ: MinMis criterion. ∗Dept. of Computer and Information Science, Polytechnic University, USA, [email protected]. †Depto. de Matem´atica Aplicada I, Universidad de Sevilla, [email protected]. ‡School of Computing, Queen’s University, Kingston, Canada, [email protected]. §School of Computing, Queen’s University, Kingston, Canada, [email protected]. ¶Dept. de Matem`atica Aplicada II, Universitat Polit`ecnica de Catalunya, Spain, [email protected]. kInstituto de Matem´aticas, Universidad Nacional Aut´onoma de M´exico, [email protected]. Measuring the error of linear separators on linearly inseparable data 251 2MinMax In this section we concentrate in what may be considered as the simplest version of the problem as our solutions are straightforward and succinct. We will also be setting a pattern that we follow in all subsequent versions. We first consider the problem in R. In each case the one-dimensional algorithm for finding an optimal approximate separator offers intuitive insight to solutions in higher dimensions. This phenomenon is easily explained by the following observation. Observation 2.1. Suppose we have obtained an optimal approximate separator Hfor Pin Rd. Let P−(H−) denote a projection orthogonal to Hof P(H) to Rd−1. Maintaining the same notation, repeatedly project into a lower dimension until we get to R. Then H−is an optimal approximate separator of P−and furthermore s(H) = s(H−). Thus every optimal solution in higher dimensions has an equivalent one-dimensional solution, but the number of possible candidate solutions that we can evaluate to determine an optimal one usually increases with the dimension, i.e., bigger dimension implies more possible candidates. 2.1 d= 1 Observation 2.2. An optimal MinMax approximate separator is the mean of the leftmost blue point and the rightmost red point and is found in Θ(n) time. The observation is justified by the fact that the cost s(H) is realized by the misclassified point that is furthest away from H. Placing Hat the mean of the extremes is obviously the cost minimizing approximate separator. 2.2 d= 2 As in the one-dimensional version of this problem the optimal approximate separator is the mean of extreme points. In R2we must consider combinations of an extreme point of Rpaired with an extreme and antipodal extreme point of B. We then pick the pair that are closest together. When closest antipodal extreme points come from the same set they determine the width of the set. In our case the pairs come from two different sets, but it is a routine matter to show that in R2there are only O(n) antipodal pairs that need to be examined. These points can be found using the well known algorithmic technique that is described as the method of rotating calipers. See for example Tousaint [12]. Thus the crux of our method examines antipodal pairs from Rand B. We begin by computing the convex hulls CH(B) and CH(R) represented as the lists of the extreme points of Band Rrespectively stored in order around the boundary of the corresponding convex hulls. There are many well known convex hull algorithms for a set of npoints and the most efficient use O(nlog h) time where hrepresents the number of extreme points of the set. See for example Chan’s algorithm [2]. Once we have the hulls we pick fixed antipodal directions for CH(B) and CH(R), and then systematically march around each of the boundaries. As we never backtrack along either of the hulls, we make the full revolution in O(n) steps. At each step we maintain the distance between the antipodal points, and when we complete a full revolution we have the overall minimum antipodal distance. Thus we have the following observation. Observation 2.3. We can obtain a MinMax optimal approximate separator in O(nlog n) time, using O(n) space. If we use hto denote the sum of the number of the blue and red extreme points then we can say that the complexity is in O(nlog h) time. When the number of extreme points of Rand Bare in Ω(n) then we can demonstrate that Ω(nlog n) is a lower bound for find a best MinMax optimal approximate separator. We use a reduction from the Max–Gap problem for points on the first quadrant of the unit circle [11] which is known to have an Ω(nlog n) lower bound in the algebraic computation tree model. 252 XIII Encuentros de Geometr´ıa Computacional 2.3 d≥3 The minimum width problem for a set of npoints Pin R3can be solved in O(m+nlog n) time and O(n) space, where mis the number of antipodal edge-edge pairs of CH(P) (see Houle and Toussaint [9]). Houle and Toussaint perform an exhaustive analysis and show that there are polyhedra that have Θ(n2) antipodal edge-edge pairs. Thus it follows that with separate polyhedra with a sum total of nedges, we may have Θ(n2) edge pairs as well. Thus the search space for determining an antipodal pair with minimal distance is in Θ(n2), and by using the techniques developed by Houle and Toussaint we can obtain an optimal approximate MinMax separator in O(m+nlog n) time. With respect to the problem of computing the width of a set of points, a series of papers derived improved sub-quadratic algorithms, the best of which requires O(n3/2+δ) expected time (see [3]). For d≥4, the O(ndd/2e) time algorithm can be achieved by realizing the solution space as a convex polytope in d+ 1 variables/dimensions, and applying an optimal half-space intersection algorithm. 3 MinSum In this section we study the problem of minimizing the sum of distances of those points that have to be moved for Rand Bto become linearly separable, that is, using the MinSum criterium. Most of the proofs in dimension d= 1 can be extended for d≥2 as a consequence of Observation 2.1. 3.1 d= 1 Let Rand Bbe inseparable sets of red and blue points on a line. We want to find the optimal separator aaccording to the MinSum criterium. Assume that the red (blue) region is on the left (right) of a, and that ais strictly between two consecutive points. The following lemma characterizes the solution of the MinSum problem. Lemma 3.1. An optimal separator point alies between two consecutive points of R∪Bsuch that the number of misclassified blue points is equal to the number of misclassified red points. Observation 3.2. If there exists an optimal separator abetween consecutive points, say sand t, then any point p∈(s, t) is an optimal separator. In fact, we can take the closed interval [s, t] treating sas belonging to the left region and tbelonging to the right region. Lemma 3.3. Let |R|=p,|B|=q. The MinSum problem in Rhas infinitely many optimal solutions. An optimal separator is any point aof the closed interval defined by the two consecutive points of R∪B in the positions pand p+ 1 counting from left to right. Theorem 3.4. The 1-dimensional MinSum problem can be solved in Θ(n)time. 3.2 d= 2 Let `be an the optimal separator line for Rand Baccording to the MinSum criterion. Let `+(`−) be the open half-plane above (below) `. The following two lemmas are straightforward consequence from Observation 2.1 and Lemmas 3.1 and 3.3. Lemma 3.5. The optimal direction to move the misclassified points is the orthogonal direction to `. Lemma 3.6. The number of misclassified blue points on `+is equal to the number of misclassified red points on `−. The 2-dimensional MinSum problem has an infinite number of optimal separators. Let `:= ax +y+b= 0 and pi= (xi, yi)∈`+(pj= (xj, yj)∈`−) a point of P=R∪Bwhich satisfies axi+yi+b > 0 (axj+yj+b < 0). Assign a value δito each point pi, red or blue, such that δi= 0 for each red point in `−(well classified) and δi= 1 for each blue point in `−(misclassified). Analogously, assign δj= 0 to each blue point in `+(well classified) and δj= 1 to each red point in `+ Measuring the error of linear separators on linearly inseparable data 253 (misclassified). A red or blue point pi= (xi, yi) on `satisfies axi+yi+b= 0 and it is always consider well classified, i.e., δi= 0. If the number of misclassified points on `−and `+are equal, then the sum of distances of the points of P=R∪Bto `is the function: s(`) = 1 √a2+1³a(X(δixi−δjxj)) + X(δiyi−δjyj)´. Let us write A=P(δixi−δjxj) and B=P(δiyi−δjyj), which are constants for a fixed bipartition. Then, the function s(`) only depends on the parameter a, the slope of `, so we write s(`) = s(a). s(`) = s(a) = Aa +B √a2+1, s0(a) = −Ba +A (a2+1)3/2. The value a=A/B is a minimum of the function s(a), so line `0:= A/Bx +y+b= 0 is the optimal separator for the bipartition defined by `. This fixes the slope of `0but we still need to determine a value (or range of values) of b. The family of parallel lines A/Bx +y+b= 0, b∈[b1, b2], is defined by the supporting lines with slope A/B of the left and right part of the bipartition of Pproduced by `. Algorithm 1: 2d-MinSum-optimal-separator 1. Compute the pand (p+ 1)-levels in A(P) and the sequence (a1, . . . , anp−1). Let eiand e0 ibe the lines which intersection point is ai. 2. Let `1:= D(a1). In O(n) time do the following: (1) compute in the primal the bipartition {P1,1, P1,2}of Pproduced by `1:P1,1is the subset of points of Pabove `1including the point D(e1), and P1,2is the subset of points of Pbelow `1including the point D(e0 1); (2) compute the function s(a), the value A/B which minimizes s(a), check that A/B ≤a1; and (3) do m:= A/B, s(m) := s(A/B), and ind := 1 the index of the cell C1. 3. For i:= 2 to np(sweeping the p-level from left to right and stopping at ai)do: (a) Update the changes of the function s(a): only the two points D(ei−1) and D(e0 i−1) interchange their half-planes in the bipartition {Pi,1, Pi,2}given by `i:= D(ai) with respect to the bipartition {Pi−1,1, Pi−1,2}working with the neighbor cells Ci−1and Ci. Thus, only two values of δjin the function s(a) has to be updated. (b) Compute the new value A/B which minimizes the function s(a), and check that ai−1≤ A/B ≤ai(if i=npcheck that anp≤A/B). Compute the value s(A/B). If s(A/B)< s(m), then do m:= A/B,s(m) := s(A/B), and ind := i. 4. Let m,s(m), and ind be the current values. Compute the intersection points of the vertical line x=mwith the boundary of the cell Cind. Let (m, b1) and (m, b2) be these intersection points. Any line of the family of parallel lines `=mx +y+b= 0, b∈[b1, b2] is an optimal separator for Pand MinSum = s(m). Theorem 3.7. The 2-dimensional MinSum problem can be solved deterministically in time O(nlog n+ n4/3log1+²n)for an arbitrarily small constant ² > 0or in O(nlog n+n4/3)expected time. 3.3 d= 3 Let πa plane which is an optimal separator for P=R∪Baccording to the MinSum criterion. By the same reasoning, an optimal separator plane πwith normal vector ~v can be translated along the direction given by ~v until it bumps into a point in P, and all these planes are optimal. Let π:= ax +by +z+c= 0 a plane with normal vector (a, b, 1) and pi= (xi, yi, zi)∈π+(pj= (xj, yj, zj)∈π−) a point of P=R∪Bwhich satisfies axi+byi+zi+c > 0 (axi+byi+zi+c < 0). Let δiand δjbe defined as in the subsection above depending on whether the point is well or misclassified. We recall that a point pi= (xi, yi, zi) on πsatisfies axi+byi+zi+c= 0 and it is always consider well 254 XIII Encuentros de Geometr´ıa Computacional classified, so δi= 0. If the number of misclassified points in both half-spaces of πare equal, the sum of distances between misclassified points of Pand the plane πis the function: s(π) = 1 √a2+b2+1³a(X(δixi−δjxj)) + b(X(δiyi−δjyj)) + X(δizi−δjzj)´. Let us write A=P(δixi−δjxj), B=P(δiyi−δjyj), and C=P(δizi−δjzj). These values are constants for a fixed bipartition. Then, the function s(π) only depends on the parameters aand b, e.i., it only depends on the normal vector (a, b, 1) of π, so we write s(π) = s(a, b). s(π) = s(a, b) = Aa +Bb +C √a2+b2+1. Algorithm 2: 3d-MinSum-optimal-separator 1. Compute the pand (p+ 1)-levels in A(P) and the sequence (a1, . . . , anp). Let ei,e0 i, and e00 ibe the three planes which intersection point is ai. 2. Let π1:= D(a1). In O(n) time compute in the primal the bipartition {P1,1, P1,2}of Pproduced by π1:P1,1is the subset of points of Pin π+ 1including the point D(e1), and P1,2is the subset of points of Pin π− 1including the points D(e0 2) and D(e00 3) (analogously for D(e2) in π+ 1and D(e0 1) and D(e00 3) in π− 1, and for D(e3) in π+ 1, and D(e0 1) and D(e00 2) in π− 1, corresponding to the two neighbor cells sharing a1). For each case compute the function s(a, b) and the pair which minimizes s(a, b). Let (a1, b1) be this pair. Do (m1, m2) := (a1, b1), s(m1, m2) := s(a1, b1), and ind the index of the current cell. 3. For i:= 2 to npdo: (a) Update the changes of the function s(a, b): only the two points interchange their halfspaces in the bipartition {Pi,1, Pi,2}given by πi:= D(ai) with respect to the bipartition {Pi−1,1, Pi−1,2}working with the neighbor cells. Thus, only two values of δjin the function s(a, b) has to be updated. (b) Compute the pair (ai, bi) which minimizes the function s(a, b), compute the value s(ai, bi). If s(ai, bi)< s(m1, m2), then do (m1, m2) := (ai, bi), s(m1, m2) := s(ai, bi), and ind the index of the current cell. 4. Let (m1, m2), s(m1, m2), and ind be the current values. To check that (m1, m2,1) is a normal vector between the ones defined by the cell Cind cost the complexity of the cell. To determine the plane πand the infinite solutions we compute the extreme points, (m1, m2, c1) (m1, m2, c2), in the the boundary of the cell Cind with the vertical line passing through the point (m1, m2,0). Any plane of the family of parallel planes π=m1x+m2y+z+c= 0, c∈[c1, c2] is an optimal separator for Pand MinSum = s(m1, m2). Theorem 3.8. The 3-dimensional MinSum problem can be solved in O(n5/2log6n)expected time. 3.4 d≥4 For dimension d≥4, the upper bound for the size of the p-level is only slightly better than the O¡nbd/2cpdd/2e¢[5]. More concretely, an upper bound is O(nd−αd) for a very small αd= 1/(4d−3)d. As Agarval et al. [1] observed, the bound can be made sensitive to p, namely O(nbd/2cpdd/2e−αd). Matouˇsek et al. [10] give an O(n4−2/45) upper bound for d= 4. Theorem 3.9. The d-dimensional MinSum problem can be solved deterministically in time OÃnbd/2cpdd/2eµlog n log p¶O(1)!=O(nd). Measuring the error of linear separators on linearly inseparable data 255 4MinSum2 We now consider the criterion of minimizing the sum of the squared distances of those points that have to be moved until Rand Bbecome linear separable, i.e., using the MinSum2criterion. 4.1 d= 1 Let Rand Bbe two inseparable sets of red and blue points on the x-axis. Assume that an optimal separator point adetermines the red region on its left and the blue region on its right. It means that the misclassified red and blue points have to be moved to the left and to the right of a, respectively. Given an optimal separator point a, let b1, . . . , bkbe the x-coordinates of the misclassified blue points and r1, . . . , rmthe x-coordinates of the misclassified red points. The sum of the squared distances of the misclassified points to ais given by s(a) = (a−b1)2+···+ (a−bk)2+ (r1−a)2+···+ (rm−a)2 s(a) = (k+m)a2−2aÃk X i=1 bi+ m X i=1 ri!+Ãk X i=1 b2 i+ m X i=1 r2 i!. If we put A= k X i=1 bi+ m X i=1 ri, B = k X i=1 b2 i+ m X i=1 r2 i, s(a) = (k+m)a2−2aA +B, and s0(a) = (k+m)a−2A= 0 which implies that a=A k+m.This value is a minimum since there is at least one misclassified point and so s00(a) = k+m > 0. Observe that a=A k+m=Pk i=1 bi+Pm i=1 ri k+m is the arithmetic median of the misclassified points. Thus, the value agives us a measure of how much the points are misclassified with respect to their arithmetic median. A two-dimension interpretation is the regression line of the misclassified points. Let S= (s1, . . . , sn) denote P=R∪Bwith n=p+q, where the points are ordered from left to right. We use interval i to denote the interval between siand si+1. As a shorthand it will be convenient to use Ξito denote the set of misclassified points and Nithe number of misclassified points when the separator is in interval i. The average value of the misclassified points at interval iis ai=1 NiX s∈Ξi s. We say that an average ai, is correct if si< ai≤si+1. We prove the following theorem. Theorem 4.1. There is a unique correct average that defines an optimal solution for the one dimensional MinSum2problem, and it can be found in linear time. 4.2 d= 2 Let `:= ax +y+b= 0 be the optimal separator line according to the MinSum2criterion. Let pi= (xi, yi) (pj= (xj, yj)) be a point of R∪Bin `+(`−) which satisfies axi+yi+b > 0 (axj+yj+b < 0). Assign a value δito each point pi, red or blue, such that δi= 0 for each red point in `+(well classified) and δi= 1 for each blue point in `+(misclassified). Analogously, assign δj= 0 to each blue point in `− (well classified) and δj= 1 to each red point in `−(misclassified). A point pi= (xi, yi) on `satisfies axi+yi+b= 0 and it is consider well classified, i.e., δi= 0. The sum of squared distances between the points of R∪Band the line `is the function: s(`) = X pi∈`+ δi (axi+yi+b)2 a2+1+X pj∈`− δj (axj+yj+b)2 a2+1= 256 XIII Encuentros de Geometr´ıa Computacional =1 a2+1 X pi∈R∪B δi(a2x2 i+y2 i+b2+ 2axiyi+ 2abxi+ 2byi) . Let us write A=Pδix2 i,B=Pδiy2 i,C=Pδi,D=Pδixiyi,E=Pδixi, and F=Pδiyiwhich are constants for a given partition. Thus, s(`) only depends on aand b, so we write s(`) = s(a, b), s(a, b) = Aa2+B+Cb2+ 2Da + 2Eab + 2F b a2+1. Procedure: MinSum2-optimal-separator 1. Dualize the point set P=R∪Bas red and blue lines obtaining the arrangement A(P). 2. Visit all the cells in A(P) and for on each cell do the following calculations: (a) Update the changes of the function s(a, b): only a point change in the bipartition {P1, P2}, thus update two values of δi. (b) Compute the the pair (a1, b1) which minimizes s(a, b). Check that the point obtained by dualizing the line `1:= a1x+y+b1= 0 is inside the current cell. (c) Compute and update the minimum value of s(a, b) and its corresponding optimal separator `:= ax +y+b= 0. Theorem 4.2. The two-dimensional MinSum2problem can be solved in O(n2)time. For d≥3, similar computations can be extended obtaining an O(nd) time algorithm. 5 MinMis Another way of thinking into reach linear separability is to delete the misclassified points, i.e., compute the minimum number of points that have to be deleted in order to get the linear separability of the remaining red and blue points. This problem is equivalent to the problem of computing an optimal separator for Band Rwhich minimize the sum of misclassified points [7]. 5.1 d= 1 Let Rand Bbe set of red and blue points on a line, respectively. In order to compute the separator agiven the minimum number of misclassified points, i.e., the separator athat minimize the sum sof misclassified points in both sides, we sort the points in O(nlog n) time, obtained a linear number of intervals defined by two consecutive points. Any point in an interval gives the same value of s. Thus do a sweep from left to right updating the value sin constant time each time we a point (red or blue) changes from right to left of the current a. Notice that for a given separator awe have rred points and bblue points on its left and n−rred points and n−bblue points on its right. It is clear that we get an overall O(nlog n) time algorithm for computing the optimal separator (either point or interval). We prove that this algorithm is optimal using a reduction to the ²-distance problem for points on a line which has an Ω(nlog n) time lower bound in the algebraic decision tree model [11]. Theorem 5.1. The one-dimensional MinMis problem can be solved in optimal Θ(nlog n)time. 5.2 d= 2 For the two-dimensional problem we can proceed as for the 2-dimensions MinSum2problem counting the number of misclassified points in both sides of the line, updating the minimum of the sum of them. Houle [8] gave an O(n2) time algorithm for this problem. For a given k, Cole, Sharir and Measuring the error of linear separators on linearly inseparable data 257 Yap [6] presented an O(nk log n) time algorithm to compute the separators misclassifying at most k points. Everett et al. [7] improve upon these results if the number of misclassified points is not too large, getting a O(nm log m+nlog n) time algorithm, where mis the number of misclassified points. Chan [4] present an algorithm that find a line `that minimizes k, the total number of red points above `and the blue points below `, in O((n+k2) log n) expected time and O(n+k2) space. Theorem 5.2. The two-dimensional MinMis problem can be solved in O(n2)time. For d≥3 we can proceed as for the 2-dimensions MinSum2problem counting the number of misclassified points in both sides of the hyperplane. Thus, the d-dimensional MinMis problem can be solved in O(nd) time. Table 1: Summary of results. Dimension MinMax MinSum MinSum2MinMis d= 1 Θ(n) Θ(n) Θ(n) Θ(nlog n) d= 2 Θ(nlog n)O(nlog n+n4/3log1+n) O(nlog n+n4/3) (∗)O(n2)O(n2) d= 3 O(n2)O(n5/2log6n) (∗)O(n3)O(n3) d≥4O(ndd/2e)O(nd)O(nd)O(nd) (∗) expected time References [1] P. K. Agarwal, B. Aronov, T. M. Chan, and M. Sharir. On levels in arrangements of lines, segments, planes, and triangles. 2001 [2] T. M. Chan. Optimal output-sensitive convex hull algorithms in two and three dimensions. Discrete and Computational Geometry, Vol. 16,1996, pp.361–368. [3] T. M. Chan. Approximating the diameter, width, smallest enclosing cylinder, and minimum-width annulus. Sixteenth Annual Symposium on Computational Geometry, 2000, pp. 300–309. [4] T. M. Chan. Low-Dimensional Linear Programming with Violations. 2004. A preliminary version of this paper appeared in Proc. 43rd IEEE Sympos. Found. Comput. Sci., 2002. [5] K. L. Clarkson and P. W. Shor. Applications of random sampling in computational geometry, II. Discrete Comput. Geom., 4, 1989, pp. 387–421. [6] R. Cole, M. Sharir, and C. K. Yap. On k-hulls and related problems. SIAM J. Comput., 16, 1987, pp. 61–77. [7] H. Everett, J.-M. Robert, and M. van Kreveld. An optimal algorithm for the (≤k)-levels, with applications to separation and transversal problems. International Journal of Computational Geometry and Applications, 6, 1996, pp. 247–261. [8] M. E. Houle. Algorithms for weak and wide separation of sets. Discrete Applied Mathematics, Vol. 45, N. 2, 1993, pp. 139-159. [9] M. E. Houle and G. T. Toussaint. Computing the width of a set. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 10, no. 5, pp. 761–765, 1988. [10] J. Matouˇsek, M. Sharir, S. Smorodinsky, and U. Wagner. On k-sets in four dimension. Manuscript, 2004. [11] V. Sacrist´an. Lower bounds for some geometric problems. Technical Report MA-IR-98-0034, Universitat Polit`ecnica de Catalunya, Departament de Matem`atica Aplicada II, 1998. [12] G. T. Toussaint. Solving geometric problems with the rotating calipers. Proceedings of IEEE MELECON’83, Athens, Greece, May 1983, pp. A10.02/1–4. 258 XIII Encuentros de Geometr´ıa Computacional