Fitting a two-joint orthogonal chain to a point set

Computational Geometry 44 (2011) 135–147 Contents lists available at ScienceDirect Computational Geometry: Theory and Applications www.elsevier.com/locate/comgeo Fitting a two-joint orthogonal chain to a point set J.M. Díaz-Báñez a,∗,1,M.A.López b,M.Mora c,2, C. Seara c,2, I. Ventura a,1 aDepartamento de Matemática Aplicada II, Universidad de Sevilla, Spain bDepartment of Mathematics, University of Denver, 2360 South Gaylord Street, Denver, CO 80208, USA cDepartament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Spain article info abstract Article history: Received 31 July 2009 Accepted 28 July 2010 Available online 3 August 2010 Communicated by J. Mitchell Keywords: Polygonal approximation Combinatorial optimization Curve fitting Algorithms We study the problem of fitting a two-joint orthogonal polygonal chain to a set Sof n points in the plane, where the objective function is to minimize the maximum orthogonal distance from Sto the chain. We show that this problem can be solved in Θ(n)time if the orientation of the chain is fixed, and in Θ(nlogn)time when the orientation is not a priori known. Moreover, our algorithm can be used to maintain the rectilinear convex hull of S while rotating the coordinate system in O(nlogn)time and O(n)space, improving on a recent result (Bae et al., 2009 [4]). We also consider some variations of the problem in three-dimensions where a polygonal chain is interpreted as a configuration of orthogonal planes. In this case we obtain O(n),O(nlogn),andO(n2)time algorithms depending on which plane orientations are fixed. ©2010 Elsevier B.V. All rights reserved. 1. Introduction and definitions Fitting a curve of a certain type to a given point set in the plane is a fundamental problem with applications in fields as diverse as statistics, computer graphics, and artificial intelligence. A special case of this problem is the so-called polygonal approximation problem or polygonal fitting problem, where a polygonal chain with kcorners or joints is fitted to a data set so as to minimize the approximation error according to some agreed upon metric. This problem is closely related to that of approximating a piecewise-linear curve with nedges by one with fewer edges, except that the input is now also a chain. Applications of this problem arise in cartography, pattern recognition, and graphic design [5,9,25], and has received much attention in computational geometry [1,6,16,20,27]. In the Min–Max problem a polygonal chain with kjoints is fitted to a data set with the goal of minimizing the maximum vertical distance from the input points to the chain. This problem was first posed by Hakimi and Schmeichel [17] and solved in O(n2logn)time. The complexity has since been improved, first by Wang et al. [29] to O(n2)time and then by Goodrich [14] to O(nlogn)time. We consider the case in which the approximating curve is an orthogonal polygonal chain, i.e., a chain of consecutive orthogonal line segments where the extreme segments are half-lines with the same slope, the slope of the orthogonal polygonal chain. The case in which this slope is given was first solved by Díaz-Báñez and Mesa [11] in O(n2logn)time, and subsequently improved by Wang [28] to O(n2)time, and by López and Mayster [24] to min{n2,nk logn}time. Very recently, Fournier and Vigneron [13] give an O(n)time algorithm if the points are sorted by their x-coordinates, and an O(nlogn) *Corresponding author. E-mail addresses: [email protected] (J.M. Díaz-Báñez), [email protected] (M.A. López), [email protected] (M. Mora), car[email protected] (C. Seara), iv[email protected] (I. Ventura). 1Partially supported by grant MTM2009-08625. 2Supported by projects MTM2009-07242 and Gen. Cat. DGR2009GR1040. 0925-7721/$ – see front matter ©2010 Elsevier B.V. All rights reserved. doi:10.1016/j.comgeo.2010.07.005 136 J.M. Díaz-Báñez et al. / Computational Geometry 44 (2011) 135–147 Fig. 1. A 6-orthogonal polygonal chain dividing the plane into 6 strips. time algorithm for the unsorted case. These authors give an Ω(nlogk)lower bound for the decision problem and thus prove the optimality of their algorithm for the unsorted case when k=Θ(n). Let S={p1,...,pn}be a set of npoints in the plane in general position, i.e., no three points on a line. When k⩾1 and 0◦⩽θ<180◦,ak-orthogonal polygonal chain with orientation θ,Ok,θ , is a chain of 2k−1 consecutive orthogonal segments such that the extreme segments are in fact half-lines with slope tan(θ).Thus,Ok,θ consists of ksegments with slope tan(θ) and k−1segmentswithslopetan(θ +90◦)(Fig. 1). Clearly, Ok,θ is always monotone with respect to its orientation. We deal with the problem of fitting a k-orthogonal polygonal chain Ok,θ to the set S. Fitting Ok,θ to Smeans to locate θ-oriented segments si(θ),i=1,...,k, according to a given optimization criterion. We consider the Min–Max criterion, illustrated in Fig. 1 and defined as follows. Let li(θ) bethelinepassingthroughpi∈Swith orientation θ+90◦. The fitting distance between piand Ok,θ ,denotedbydf(pi,Ok,θ ),isgivenby df(pi,Ok,θ )=min p∈li(θ)∩Ok,θ d(pi,p). Notice that dfis not the Euclidean distance between the point piand the polygonal chain. However, we can assume that this distance is the Euclidean distance between piand a point on a segment with orientation θin Ok,θ .Theerror tolerance of Ok,θ with respect to S,denotedbyμ(Ok,θ ,S), is the maximum fitting distance between the points of Sand Ok,θ , i.e., μ(Ok,θ ,S)=max pi∈Sdf(pi,Ok,θ ). Definition 1. The k-fitting problem for Swith the Min–Max criterion consists of finding an orthogonal polygonal chain Ok,θ such that its error tolerance μ(Ok,θ ,S)is minimized. Notice that if the orientation of Ok,θ is fixed, for example θ=0◦, then the k-fitting problem consists of finding an xmonotone rectilinear path formed by 2k−1 segments with minimum error tolerance where the fitting distance is just the vertical distance [11]. We focus here on the case where kis small, in fact k=2, and the points in Sare not sorted. We study the 2-fitting problem for Swith fixed orientation (the oriented 2-fitting problem) and the problem of finding the best orientation for fitting a two-joint orthogonal polygonal chain to S(the un-oriented 2-fitting problem). We also consider the extension of the problem to three-dimensions where an orthogonal polygonal chain is a configuration of orthogonal planes. See Chen and Wang [7,8] for recent results on some variants of this problem including NP-hardness results in three dimensions. Outline of the paper. In Section 2 we study the oriented fitting problem in the plane. In Section 3 we study the un-oriented 2-fitting problem in the plane. Finally, in Section 4, we study the oriented 2-fitting problem in three-dimensions. 2. The oriented fitting problem In this section we consider the oriented k-fitting problem for S, i.e., the case where the orientation θof the k-orthogonal chain that fits Sis fixed. Without loss of generality we assume that θ=0◦. Thus, we are looking for an x-monotone rectilinear path, Ok,0or Ok, consisting of an alternating sequence of khorizontal and k−1 vertical segments with minimum error tolerance. Often, the algorithms proposed in the literature for these kinds of fitting problem assume that the input points are given in sorted order. Recently, Fournier and Vigneron [13] give an O(nlogn)time algorithm for the oriented k-fitting problem when the points are unsorted and prove its optimality when k=Θ(n). The running time of the algorithm from Lopez and Mayster [24] is min{n2,nk logn}which is O(nlogn)when kis a constant. For the sorted case, Fournier and Vigneron [13] J.M. Díaz-Báñez et al. / Computational Geometry 44 (2011) 135–147 137 present an optimal O(n)time algorithm, and an Ω(nlogk)time lower bound for the decision problem for the unsorted case. Here we consider the oriented k-fitting problem for the case k=2 for the unsorted case. Let S={p1,...,pn}, where pi=(xi,yi). We can compute ymax =max{y1,...,yn}and ymin =min{y1,...,yn}in linear time. The oriented 1-fitting problem then is solved in O(n)time by finding the horizontal line y=(ymax +ymin)/2. Let O2denote an optimal solution to the oriented 2-fitting problem for a set S.ThenO2consists of two horizontal half-lines joined by a vertical segment contained in a vertical line ∗which partitions Sinto subsets S1and S2, namely the points of Sto the left and to the right of ∗respectively. Since ∗must minimize the maximum error tolerance of S1and S2, the following is apparent. Lemma 1. Line ∗separates the two points in S with y-coordinates ymin and ymax. We remark here that there could be several points that achieve ymax and ymin. All these points can be computed in linear time. It is clear that ∗has to separate all the ymax points from all ymin points, since otherwise the solution is trivial. This can be checked in linear time. Thus, without loss of generality we can assume that the ymax and ymin points are unique. Linear time algorithm for oriented 2-fitting. Any vertical line between two points of Sinduces a candidate solution to the oriented 2-fitting problem whose cost is given by max{1,2}, where 1(resp. 2) denotes the tolerance of the subset of S to the left (resp. right) of . Our algorithm performs a binary search based on the following observation: Lemma 2. If is not optimal and 1<2(resp. 1>2)then ∗lies to the right (resp. left)of . We now outline the algorithm. Let denote the vertical line through the median x-coordinate of S. Partition Sinto subsets S1and S2to the left and right of , respectively. Compute also the tolerances 1of S1and 2of S2, and store the two witness pairs of points responsible for the tolerances. All this can be computed in O(n)time [10]. If 1=2,stopthe algorithm, as ∗=.If1<2,inO(n/2)time compute the median of S2,resetas the vertical line at this median value, compute the subsets S 2and S 2of the bipartition of S2produced by the new median, and compute the tolerances  2and  2of S 2and S 2. The next move of (left or right) is determined based on the maximum of  2and where is the error tolerance of all points to the left of , which can be obtained in constant time by the two witness points for 1and the two witness points for  2. Store the tolerance values and the corresponding witness pairs as temporary values. Next compute and update the tolerances once we know the next move of .(If1>2we proceed in a symmetric way.) Compare the new tolerance values and continue recursively translating the line left or right by computing the new median of a subset with half of the points and updating the new tolerance values (left and right) from the old ones. At all times we have two unions at the extremes and an unknown zone in between containing at most two strips. The points in the zone are known but, in general, are not sorted. Clearly, the time complexity of the algorithm is T(n)=T(n/2)+O(n)=O(n), using a linear time median finding algorithm [10]. By Lemma 1 the optimal line ∗will be located between the two points in Swith y-coordinates ymin and ymax. The algorithm stops when either the tolerance values 1and 2are equal, or when translating left and right the bigger of the two tolerances switches sides and the unknown zone contains no points. In this last case the solution will be the best of the two. Since the algorithm performs a binary search on a unimodal function, the method is correct. Notice that the solution (position of line or bipartition of S) is not unique because in an optimal solution some points can belong to S1 or S2without changing the solution. Notice also that our algorithm does not sort the input points. We have the following result. Theorem 1. The oriented 2-fitting problem can be solved in Θ(n)time and space. By the Ω(nlogk)lower bound for the decisional oriented k-fitting problem [13] in the unsorted case, it is clear that if k=ω(1)there is no linear time algorithm. Thus, we raise the following open question more from a theoretical than from a practical point of view. Open problem 1. For which values of k⩾3 does there exist a linear time algorithm for the oriented k-fitting problem? 2.1. An O(nlogn)-time algorithm We now describe an O(nlogn)-time algorithm for the oriented 2-fitting problem whose interest derives not from its time complexity but from the fact that it will be used as a preprocessing step in the O(nlogn)-time algorithm for the un-oriented 2-fitting problem discussed in Section 3. We start by introducing a basic tool. In [21,26] the maxima problem for a point set Sin the plane is considered. Concretely, given two points pi,pj∈S,the following dominance relation is established: pidominates p j(pj≺pi),ifxj⩽xiand y j⩽yi.Therelation≺is a partial order in S.Apointpi∈Sis called maximal if there does not exist pj∈Ssuch that i= jand pi≺pj. The maxima problem 138 J.M. Díaz-Báñez et al. / Computational Geometry 44 (2011) 135–147 Fig. 2. A rectilinear convex hull of Sformed by the maximal points of S. consists of finding all the maximal points of Sunder dominance. One can formulate maxima problems for each quadrant in theplane.WeareinterestedinthesetofmaximalpointsforSwith respect to the four quadrants which form the rectilinear convex hull of S, also known as orthogonal convex hull (Fig. 2). Each set of maximal points has a total ordering that can be stored in a height balanced search tree [26]. Theorem 2. (See [21].) The maxima problem for S with respect to any of the four quadrants can be solved optimally in Θ(nlogn)time and O(n)space. O(nlogn)-time algorithm for oriented 2-fitting 1. Let xmax,xmin,ymax, and ymin denote the respective maximum and minimum of the x- and y-coordinates of the points in S. Without loss of generality assume xmin =ymin =0, xmax =c, and p1=(0,y1),pn=(c,yn),pi=(xi,ymax), and pj=(xj,0)(Fig. 2), i.e., the rectangle with corners at (0,0)and (c,ymax)is the axis-parallel bounding box for S. Assume further that piis strictly to the left of pjand thus, by Lemma 1, the vertical line ∗lies between piand pj.(If both have the same x-coordinate the solution is trivial.) By Theorem 2, in O(nlogn)time we can compute the rectilinear convex hull of Sformed by the staircases structure as in Fig. 2. Notice that staircases of opposite quadrants can intersect. Since piis to the left of pj, then the third quadrant staircase gives the lower point on the left of ∗and the first quadrant staircase gives the upper point on the right of ∗. 2. By Lemma 1 the vertical line ∗:= (x=a)is between xiand xj. In order to find its correct location we do a binary search over the points in the staircase structure (first and third quadrants) in O(logn)time getting the best balance between the error tolerance on the left and on the right sides of ∗, i.e., min xi⩽a<xj asubject to max xk⩽a{ymax −yk}⩾max xm>aym(1) or max xi<a⩽xj asubject to max xk⩽a{ymax −yk}⩽max xm>aym.(2) For at least one of Eqs. (1) or (2) there exists a solution. In case (1), the error tolerance of Sis given by the points to the left of ∗and, in case (2), by the points to the right of ∗. In constant time compute this error tolerance given by the difference between the bigger and smaller y-coordinates of the points to the left or right of line ∗. If piis to the right of pj, then the algorithm is similar with the obvious changes: the second quadrant staircase gives the upper point to the left of ∗and the fourth quadrant staircase gives the lower point to the right of ∗. Notice that once the rectilinear convex hull of Sis obtained, the oriented 2-fitting problem can be solved in O(logn) time; this is a key component for the algorithm of Section 3. The above staircase structure can be used to design O(nlogn)time algorithms for the oriented 3-fitting and 4-fitting problems as well. We consider 3-fitting first. Let 1and 2denote, respectively, the two vertical lines containing the two vertical segments of the solution. By Lemma 1, at least one of 1and 2must lie between ymax and ymin. Assume that 1 is to the left of 2. There are at most a linear number of locations for 1between two consecutive points of the staircase structure. For each of these locations a binary search over the staircase structure to the right of 1yields the optimal location for 2in O(logn)time. Details are omitted but the binary search depends on whether the location of 2is either between ymax and ymin or to the right of ymin. It is clear that for the oriented 4-fitting problem with three vertical lines 1,2, and 3, we can proceed in a similar way, first fixing the location of the median line, say 2, in each of the linear number of possible locations, and then finding the locations of 1(to the left of 2) and 3(to the right of 2) by binary search on the staircase structure. As a consequence of the discussion above, both the oriented 3- and 4-fitting problems can be solved in O(nlogn)time and O(n)space. The same result but using different techniques can be achieved by the proposals in [13,15,24]. J.M. Díaz-Báñez et al. / Computational Geometry 44 (2011) 135–147 139 Fig. 3. Un-oriented Θ-maximum with respect to S. 3. The un-oriented 2-fitting problem In this section we consider the problem of fitting Susing an un-oriented 2-orthogonal polygonal chain O2,θ with free orientation θ. Notice that the un-oriented 1-fitting problem for Sis equivalent to the problem of computing the width of S. If we know the convex hull of S, this problem can be solved in O(n)time using rotating calipers [19]. Otherwise, computing the width of Shas an Ω(nlogn)-time lower bound [23]. Therefore the un-oriented 1-fitting problem for Scan be solved optimally in Θ(nlogn)time. Before studying the un-oriented 2-fitting problem we introduce some notation and tools which will be useful later. We start by reviewing some definitions and results from Avis et al. [2] concerning the computation of un-oriented Θ-maximal points of a planar point set S. Definition 2. (See [2].) A ray from a point p∈Sis called a maximal ray if it passes through another point q∈S. A cone is defined by a point pand two rays Cand Demanating from p.Apointp∈Sis an un-oriented Θ-maximal with respect to Sif and only if there exist two maximal rays, Cand D, emanating from pwith an angle at least Θbetween them so that the points of Slie outside the (Θ-angle) cone defined by p,Cand D(Fig. 3(a)). Theorem 3. (See [2].) All un-oriented Θ-maximal points of S for Θ⩾90◦can be computed in O(nlogn)time and O(n)space, and the algorithm is optimal for fixed values of Θ. For Θ=90◦, the output of the algorithm of Theorem 3 is the list of all the un-oriented 90◦-maximal points that are apices of the wedges that have bounding rays (crossing an edge of CH(S)) with aperture angle at least 90◦.Foreverysuch maximal point pthe output also contains the two rays Lpand Rpbounding the widest empty wedge on the left and on the right, respectively (Fig. 3(b)). Since the aperture angle is at least 90◦, then each maximal point pcan have at most three disjoint wedges. In constant time we can compute the set of orientations of the bisectors of the (90◦-angle) cones with apex pcontained in the wedge defined by p,Lpand Rp: compute the ray R p(resp. L p)frompwhich is perpendicular to Lp(resp. Rp), the bisectors of the (90◦-angle) cones formed by Rp,p,L pand by R p,p,Lpare the extremes of the set of orientations of bisectors (Fig. 3(b)). This set of orientations can be translated into an orientation interval in S1(see footnote 3for definition). Thus, each maximal point p∈Scan have at most three disjoint orientation intervals in S1such that for each orientation inside these intervals the point pis 90◦-maximal. Notice that all the points in the boundary of the convex hull of Sare 90◦-maximal, and that the total number of orientation intervals is linear. Now we consider the un-oriented 2-fitting problem. An optimal solution for this problem is given by an orthogonal polygonal chain O2,θ with orientation θsuch that the error tolerance of Swith respect to O2,θ is minimum. Clearly, this is equivalent to the problem of determining a line θwith slope tan(90◦+θ) that splits Sinto subsets Slθand Srθ, where eu lθand eb lθ(eu rθand eb rθ) are the points responsible for the error tolerance of Slθ(Srθ) and such that O2,θ minimizes the error tolerance of Sover all values of θ. Accordingly, the error tolerance is given by the following formula, where dθ(p,q) denotes the distance between parallel lines through pand qwith orientation θ. μ(O2,θ ,S)=max pi∈Sd(pi,O2,θ )=maxdθeu lθ,eb lθ,dθeu rθ,eb rθ. Let ymin,θ and ymax,θ be the minimum and maximum y-coordinates of the points in Swhen the coordinate system is rotated by angle θ. The following lemma is a generalization of Lemma 1. 3By Sd−1,d⩾2, we denote the unit sphere centered at the origin of the coordinate system defined by the tips of the unit normal vectors of the orientations in Rd. 140 J.M. Díaz-Báñez et al. / Computational Geometry 44 (2011) 135–147 Fig. 4. Sweeping the orientation intervals of the 90◦-maximal points of S. Lemma 3. Givenanorientationθ, an optimal solution for the un-oriented 2-fitting problem with orientation θis defined by a line θ passing through a point of S which separates the points of S with y-coordinates ymin,θ and ymax,θ . Description of the un-oriented 2-fitting algorithm. The goal of our approach is to adapt the O(nlogn)-time algorithm for the oriented 2-fitting problem described earlier to account for continuous changes in the orientation θ, looking for the optimal O2,θ chain in the process. To do this we update the staircase structure as θvaries and use Lemma 3 to look for an optimal solution. •Initialization: The starting situation is the staircase structure formed by the four sets of maximal points with respect to the four quadrants of the coordinate system when θ=0◦. Analogously to [21,26], we use a height-balanced search tree to store and compute each of the four sets of maximal points with insertions or deletions in optimal O(nlogn)time. Thus, we compute the staircase structure and its corresponding optimal solution in O(nlogn)time as we did for the oriented case. •Update as θsweeps over [0◦,90◦]: As we rotate the coordinate system according to the orientation θin discrete steps from θ=0◦to θ=90◦to compute the un-oriented optimal solution, we identify the four quadrants by their oriented bisectors, i.e., by the oriented lines with slopes tan(θ +45◦),tan(θ +135◦),tan(θ +225◦), and tan(θ +315◦). The staircases are formed by the four sets of maximal points in Swith respect to the bisectors of the current four quadrants. Notice that for any θ, a point is in the staircases if and only if it is a 90◦-maximal point for some of the four orientations above, i.e., when at least one of these four orientations lies in the orientation intervals defined by the point. The main idea of the algorithm is to rotate the coordinate system by θ, and update the staircase structure by inserting or deleting points to each of the staircases as the orientation θchanges. To do this we maintain four ordered lists of the current un-oriented 90◦-maximal points of Swith respect to the bisectors with orientations θ+45◦,θ+135◦,θ+225◦, and θ+315◦. The lists correspond to the sequences of points in the four staircases. More precisely, the staircase structure will be maintained with insertions and deletions of points induced by the changes in θ. Notice that for any orientation θ the staircase structure has linear size, and updating a point on it can be done in O(logn)time as in the θ=0◦case [21,26]. As θchanges, the four staircases can be modified because either a new point of Sbecomes 90◦-maximal or some current 90◦-maximal point of Shas to be deleted. To determine the sequence of events, as θchanges, we use Theorem 3 to precompute in O(nlogn)time the set of all un-oriented 90◦-maximal points of Stogether with their respective orientation intervals in S1. These orientation intervals are the intervals where each point is an un-oriented 90◦-maximal point for S. Notice that a point can be 90◦-maximal for at most 3 (disjoint) orientation intervals and, consequently, the total number of changes in the staircase structure is linear. To know in advance the sequences of events, i.e., the values of θwhere insertions or deletions of points occur, we proceed as follows. Suppose that we have computed the orientation intervals for each point pi∈S. Fig. 4 represents the set of these orientation intervals. A point p∈Scan have at most 3 disjoint orientation intervals. We sweep the set of these intervals from 0◦to 360◦, keeping track, for each orientation θ,ofthesetof90 ◦-maximal points for that orientation which is the set of intervals intersected by the sweep line. Thus, the algorithm performs a sweep of these intervals from θ=0◦to θ=90◦by vertical lines corresponding to orientations θ,θ+90◦,θ+180◦, and θ+270◦, stopping at each event (interval endpoint) and updating the staircase structure. Since the points in Sare in general position, only a constant number of updates can occur at each event. We compute the optimal solution for the staircase structure between two consecutive events by computing a line θwith slope tan(θ +90◦), as explained below. In order to cover all the orientations of the plane, we also run the algorithm as θchanges from 90◦to 180◦, which can be handled analogously. Consider consecutive events θ1and θ2. Lemma 3 implies that for a fixed value θ∈[θ1,θ 2], the line θthat gives the optimal solution has to separate the points with the current y-coordinates ymin,θ and ymax,θ . Thus, the optimal solution is determined by two pairs of points, either (i) (ymax,θ ,eb lθ)and (eu rθ,ymin,θ )if ymax,θ is to the left of ymin,θ , or (ii) (eu lθ,ymin,θ ) and (ymax,θ ,eu rθ)if ymax,θ is to the right of ymin,θ , giving the error tolerance in Slθ,the left error tolerance, and the error J.M. Díaz-Báñez et al. / Computational Geometry 44 (2011) 135–147 141 Fig. 5. (a) and (b) Variation of the left error tolerance depending on whether pkis on the right or left side of θ,i, (c) and (d) variation of the right error tolerance depending on whether pmisontheleftorrightsideofθ,j. Fig. 6. Variations of the left and right error tolerances. tolerance in Srθ,the right error tolerance, respectively. To compute the optimal solution between two consecutive events we use the following lemma. Lemma 4. Let [θ1,θ 2]be an orientation interval corresponding to consecutive events. The optimal solution for the un-oriented 2-fitting problem in this interval occurs at an endpoint, i.e., at θ1or θ2,oratanorientationθ0∈[θ1,θ 2]where the left and right error tolerances are equal. Proof. Let θ0∈[θ1,θ 2]be the orientation of the optimal solution in [θ1,θ 2]. Assume that the left and right error tolerances of the optimal solution for θ0aregivenbythepointpairs(pi,pk)and (pj,pm), respectively. Let piand pjbe the points with maximum and minimum y-coordinate, respectively, for any orientation in [θ1,θ 2]. The identity of these points does not change in the interval, as otherwise we would get a new orientation interval. Assume that piis to the left of pj.Other cases can be handled analogously. The left error tolerance can be written as a function w1(θ) =d(pi,pk)cos(θik −θ), where θik is the orientation of the line passing through piand pk, and θis the current orientation in the rotation process. This function is a continuous and unimodal function of the angle θ. Thus, either w1(θ) always increases as in Fig. 5(a), or it always decreases as in Fig. 5(b), or the unique increasing/decreasing change occurs if, during the rotation, pkpasses from one side to the other side of line θ,iwith orientation θgoing through piwhich is a predictable event. An entirely analogous situation occurs with the right error tolerance with the function w2(θ) =d(pj,pm)cos(θ jm −θ) (Figs. 5(c) and 5(d)). If both functions w1(θ) and w2(θ) increase, the optimal solution is found at the endpoint θ1, as otherwise we can rotate clockwise, decreasing both error tolerances in the process (Fig. 6(a)). If both functions w1(θ) and w2(θ) decrease, the optimal solution is found at the endpoint θ2as a counterclockwise rotation decreases both error tolerances (Fig. 6(c)). Analogous is the case when w1(θ) increases and w2(θ) decreases, or vice versa, but both functions do not intersect. Otherwise, the intersection of both functions gives the optimal solution in an orientation θ0when the left and right error tolerances are equal (Fig. 6(b)). This can be detected because there is a change of the maximum error tolerance from the right error tolerance in θ1to the left error tolerance in θ2or vice versa. 2 As a consequence of Lemma 4, the optimal solution for a (non-starting) interval orientation [θ1,θ 2]can be computed in O(logn)time. Summarizing: (1) the number of events for the staircase structure as θchanges from 0◦to 90◦is linear, (2) any update can be done in O(logn)time, (3) for a fixed value of θan O(logn)time binary search produces the optimal location of the line θ, its corresponding error tolerance, and allows us to maintain the minimum one. We conclude that the un-oriented 2-fitting problem can be solved in O(nlogn)time and O(n)space. The un-oriented-2-fitting-algorithm. We assume that for the current orientation θthe point with y-coordinate ymax,θ is to the left of the point with y-coordinate ymin,θ ; otherwise, we only update the changes in the staircase structure without computing the optimal solution. We repeat the algorithm for the alternative case. 1. Use the algorithm from Avis et al. [2] to compute in O(nlogn)time the list of the un-oriented 90◦-maximal points of Sand their orientation intervals in S1where each point is un-oriented 90◦-maximal. Sort the arrangement of the orientation intervals according to their endpoints in such a way that when we sweep the arrangement we know which 90◦-maximal points are active in a current sweeping orientation, and which is the next incoming endpoint (Fig. 4). 142 J.M. Díaz-Báñez et al. / Computational Geometry 44 (2011) 135–147 Fig. 7. Construction in the proof of the lower bound for the un-oriented 2-fitting problem. 2. In O(nlogn)time compute the horizontal/vertical staircase structure for Sand the optimal solution as we did in the oriented 2-fitting problem. The staircase structure is formed by the 90◦-maximal points for Swith orientations 0◦+45◦, 90◦+45◦, 180◦+45◦, and 270◦+45◦. 3. Sweep the arrangement of the orientation intervals with the four vertical lines. Each time that we reach an endpoint, either (1) a new un-oriented 90◦-maximal point enters the staircase structure, or (2) an active un-oriented 90◦-maximal point is deleted from the staircases. We update the changes in the staircases in O(logn)time, including also the possible changes of the points with minimum and maximum y-coordinates for the current orientation. Since we consider the points in general position, at most two aligned points are updated at the same time producing a constant number of changes. We use binary search to compute the separating line of the new optimal solution in O(logn)time, and store and update the information of the optimal solution. Notice that a point enters one of the staircases at most once, so a point is updated a constant number times and the overall running time for updating changes is O(nlogn)time. The running time of the algorithm is O(nlogn)and the space is O(n)since the lists and the arrangement of orientation intervals have linear size.4 Next, we show a reduction for the un-oriented 2-fitting problem from a MAX-GAP problem for points on the first quadrant of the unit circle [23], establishing in the process an Ω(nlogn)-time lower bound. We reduce the MAX-GAP problem for points on the first quadrant of the unit circle centered at the origin of the coordinates system to our problem. This MAXGAP problem has an Ω(nlogn)time lower bound in the algebraic decision tree model [23]. Let P={(x1,y1),...,(xn,yn)} be the set of points of an instance of MAX-GAP. Consider a symmetric copy of points in the third quadrant and new copies of the overall circle in other positions as in Fig. 7. It is easy to see that the optimal un-oriented 2-fitting orthogonal chain defines the maximum gap for Pand vice versa. This construction can be generalized to work with the un-oriented k-fitting problem, k⩾3, using k−1 copies of the initial circle with the centers located with adequate distances between them. Theorem 4. The un-oriented 2-fitting problem can be solved in optimal Θ(nlogn)time and O(n)space. 4. The oriented 2-fitting problem in 3D In this section we consider the oriented 2-fitting problem in three-dimensions where a polygonal chain is interpreted as a configuration of two parallel half-planes, joined with an orthogonal strip. First, we give a short discussion of the 1-fitting problem. To solve the oriented 1-fitting problem for Sin R3we proceed according to how much information about the solution plane we have, distinguishing between two cases: Case i:The orientation of the solution plane is fixed. Assume that the solution plane has normal  u=(0,0,1)∈S2.Wesolve this problem in Θ(n)time by computing the points with maximum and minimum z-coordinates. Case ii:The orientation of the solution plane has one degree of freedom. Assume that the solution plane has normal  uwhich is orthogonal to  v=(0,1,0)∈S2. We solve this problem by projecting the points onto a plane with normal  vand computing the width of the convex hull of the projected points with a rotating caliper. The total running time is Θ(nlogn).The Ω(nlogn)time lower bound comes from the computation of the width of a set of points in two-dimensions. The oriented 2-fitting problem can be defined by three consecutive orthogonal planes. We refer to the plane Πproducing the bipartition of Sas the separating plane and to the two parallel planes that induce the error tolerances on either side of Π as the supporting planes. We distinguish among three cases depending on how the orientation for the solution is constrained: 4Notice that the algorithm can maintain the rectilinear convex hull of Sduring the rotation in O(nlogn)time and O(n)space, improving on a recent result by Bae et al. [4] who present an O(n2)time and O(n)space algorithm for this problem. In their paper, the authors derive a space/time trade-off: O(n3/2log7/3(n)) time and O(n3/2logn)space are also possible. J.M. Díaz-Báñez et al. / Computational Geometry 44 (2011) 135–147 143 Fig. 8. Sample configuration for case (2). (1) the orientations of both the separating plane and the parallel supporting planes are fixed; (2) the orientation of the separating plane is fixed; and (3) the orientation of the parallel supporting planes is fixed. Next, we consider the three cases. Case (1): The orientations of both the separating plane and the parallel supporting planes are fixed. Assume that the separating plane has normal  u1=(0,1,0)and that the parallel supporting planes have normal  u2=(0,0,1). We reduce the problem to two-dimensions as follows. Let  u3= u1× u2, where ×denotes the cross product. We project the points in Sonto a plane with normal  u3=(1,0,0)and solve it optimally in O(n)time using the algorithm of Section 2. Theorem 5. The oriented 2-fitting problem in 3D can be solved in Θ(n)time and space if the orientations of both the separating plane and the parallel supported planes are fixed. Case (2): The orientation of the separating plane is fixed. Assume that the separating plane has normal  u=(0,1,0).In O(nlogn)time, sort the points in Salong  u, i.e., by  u·piwhere ·denotes the dot product (e.g., by y-coordinate). Let p1,...,pnbe the sequence of the points of Swith this order. According to this order, let Sl,i={p1,...,pi}and Sr,i= {pi+1,...,pn},i=1,...,n−1, be the bipartition of Sgiven by the separating plane passing through pi. In order to compute the parallel supporting planes of Sl,iand Sr,ifor determining which bipartition of Sgives the optimal solution, we project the points of Sl,iand the points of Sr,ionto two planes parallel to the separating plane. We work with the convex hulls of the projected points. Let S l,iand S r,ibe the projected points of Sl,iand Sr,irespectively, and let CH(S l,i)and CH(S r,i)be their respective convex hulls (Fig. 8). To find the optimal 2-fitting solution for a bipartition Sl,iand Sr,i, we use two clockwise rotating calipers which rotate simultaneously over CH(S l,i)and CH(S r,i)in discrete steps. Each step is defined by the minimum rotating angle of the two calipers on antipodal pairs. Suppose that at some step, the rotating caliper over CH(S l,i)(resp. CH(S r,i)) has antipodal points q1and q2(resp. q3and q4). Let α1(resp. α2) be the angle of rotation with respect to the parallel supporting lines passing through q1and q2(resp. q3and q4). Let w1(resp. w2) be the width function of CH(S l,i)(resp. CH(S r,i))intherotation interval and d1=d(q1,q2)(resp. d2=d(q3,q4)). The continuous and monotone width function w1(resp. w2) depends on d1(resp. d2) and cos(α1)(resp. cos(α2)). The minimum of the maximum of the two width values is a minimum of the upper envelope of the two functions w1and w2. We compute the minimum of the upper envelope in the rotation interval and the corresponding width (at most a linear number of intervals) and maintain the best solution. Algorithm for case (2).We can update the convex hulls CH(S l,i)and CH(S r,i)in O(logn)time when a point pichanges from Sr,i−1to Sl,i[3]. We use linear time for the task of computing an optimal solution for each bipartition and update the optimal. Thus, the total running time is O(n2). Next, we show a reduction from the MAX-GAP problem for points on the first quadrant of the unit circle [23] to case (2) of the oriented 2-fitting problem. Since MAX-GAP has an Ω(nlogn)time lower bound in the algebraic decision tree model [23], this establishes the same bound for our problem. The reduction is as follows. Let P={p1,...,pn}be an instance of the MAX-GAP problem for points on the first quadrant of the unit circle Cin the XZ-plane centered at the origin of the coordinate system, where pi=(xi,0,zi),fori=1,...,n.InO(n)time compute the first, the second, the penultimate, and the last points of Pin the x-coordinate order; without loss of generality, assume that p1,p2,pn−1, and pnare these points of P, respectively. Furthermore, we can assume that p1=(0,0,1). Make three copies of Pon Cby rotating clockwise the points of Pby π/2, π, and 3π/2, respectively. Let P1={p1 1,...,p1 n},P2={p2 1,...,p2 n},andP3={p3 1,...,p3 n}be the points of the three copies. Notice that the rotation of each point can be done in constant time. We put a point aat the intersection point of the line passing through the points pn−1and pn, and the line passing through the points p1 1and p1 2.Weputapointb at the intersection point of the line passing through the points p1 n−1and p1 n, and the line passing through the points p2 1 and p2 2.Weputapointcat the intersection point of the line passing through the points p2 n−1and p2 n, and the line passing through the points p3 1and p3 2. Finally, we put a point dat the intersection point of the line passing through the points p3 n−1and p3 n, and the line passing through the points p1and p2.NowletS1be the set of these 4n+4pointsinC, i.e., S1=P∪P1∪P2∪P3∪{a,b,c,d}.Thefourpoints{a,b,c,d}force that the minimum width of S1(or equivalently the MAX-GAP of P) is defined by two consecutive points of Pand the corresponding rotated points in P2(similarly for P1