Stabbers of line segments in the plane

Computational Geometry: Theory and Applications Stabbers of line segments in the plane Mercè Claverol a,1, Delia Garijo b,2, Clara I. Grima b,2, Alberto Márquez b,2, Carlos Seara c,∗,1 aDpt. de Matemàtica Aplicada IV, Universitat Politècnica de Catalunya, Spain bDpto. de Matemática Aplicada I, Universidad de Sevilla, Sevilla, Spain cDpt. de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Spain abstract Keywords: Stabbers Transversal Line segments Red-blue separability The problem of computing a representation of the stabbing lines of a set Sof segments in the plane was solved by Edelsbrunner et al. We provide efficient algorithms for the following problems: computing the stabbing wedges for S, finding a stabbing wedge for a set of parallel segments with equal length, and computing other stabbers for Ssuch as a double-wedge and a zigzag. The time and space complexities of the algorithms depend on the number of combinatorially different extreme lines, critical lines, and the number of different slopes that appear in S. 1. Introduction Let S={s1,...,sn}be a set of nnot necessarily disjoint line segments (or segments) in the plane. If pand qare the endpoints of a segment, for convenience, we require that p= qand neither of them are at the infinity; consequently, lines, rays, and points are not considered to be segments, not even degenerate ones. In order to avoid tedious case analysis, we assume that the set of endpoints of the segments is a point set in the plane in general position, i.e., no three endpoints are collinear. Since we are interesting on stabbing the segments of S, we can assume that three segments can meet, or one segment can be contained into another, or more generally, two segments can have a (non-input) segment as their intersection (the two segments are reduced to the intersection segment). Alineisatransversal of (or stabs)Sif it intersects each segment of Seven when it meets the segment only at an endpoint, and even when it contains the segment. Edelsbrunner et al. [10] presented a Θ(nlogn)time and O(n)space algorithm for solving the problem of constructing a representation of all transversal lines or stabbing lines of S. See Edelsbrunner [8] for an analysis of this problem from both a combinatorial and computational point of view. The lower bound from Edelsbrunner et al. [10] does not apply to the decision problem: determining if there exists a line stabber for S. Avis et al. [2] presented an Ω(nlogn)time lower bound in the fixed order algebraic decision tree model to determine the existence of a line stabber for S. For a set of nvertical segments, a stabbing line can be computed in Θ(n)time. A stabbing line for Sclassifies the endpoints of the segments in two classes: endpoints above , say red points; and endpoints below , say blue points. The endpoint on is classified according to the other endpoint. Thus, we can see the problem of stabbing Sas a problem of classifying the endpoints of the segments into disjoint monochromatic red and blue regions defined by the stabber, i.e., as a separability problem. Following this line of research, in this paper we deal with the *Corresponding author. E-mail addresses: [email protected] (M. Claverol), dg[email protected] (D. Garijo), [email protected] (C.I. Grima), [email protected] (A. Márquez), car[email protected] (C. Seara). 1Supported by project MTM2009-07242, and Gen. Cat. DGR2009GR1040. 2Supported by project MTM2008-05866-C03-01. 304 M. Claverol et al. / Computational Geometry 44 (2011) 303–318 Fig. 1. Stabbers from (a) to (d): line, wedge, double-wedge, zigzag. problem of finding stabbers for Ssatisfying the condition that there is no segment stabbed by more than one element of the stabber (Fig. 1). We call this condition the separability condition. So we look for stabbers for Ssuch that we can assign red and blue colors to the endpoints of the segments and split the plane into disjoint monochromatic regions. Hurtado et al. [14] classified red and blue points with separators which are similar to our stabbers. If there is no stabbing line for Sit is natural to ask for a stabbing wedge (two rays with a common endpoint) because it can be a good approximation to a stabbing line if its aperture angle is close to π. Thus, we consider the problem of computing the stabbing wedges for S. As a particular problem, we study the problem of finding a stabbing wedge for a set of parallel segments with equal length. We also look for other stabbers for Ssuch as: a double-wedge stabber formed by two intersecting lines, and a zigzag stabber formed by two non-intersecting rays and a segment joining the origins of the rays. Fig. 1 illustrates the kind of stabbers we will consider in this paper. The general goal is to design efficient algorithms for computing these stabbers for Sdepending on whether they satisfy the separability condition above, i.e., we ask for stabbers with the separability condition or stabbers without the separability condition. The time and space complexities of the algorithms are sensitive to some parameters of S, more concretely, they depend on the number of combinatorially different extreme lines, critical lines, and the number of different slopes that appear in S. Outline of the paper. In Section 2 we study the problem of computing a representation of the set of extreme lines of S. The extreme lines are a key tool for solving the problem of computing the set of stabbing wedges for Sin Section 3. The problem of finding a stabbing wedge for a set of parallel segments with equal length is considered in Section 4. Finally, in Section 5 we show efficient algorithms for the problem of computing a stabbing double-wedge for Sand for the problem of finding a stabbing zigzag for S.3 Related works. Stabbing problems have since been widely investigated and arise in many diverse problems in computational geometry. Claverol [6] as a part of her PhD thesis initiated the study here developed. In this paper we improve the complexities she obtained and some other stabbing problems are also considered. Atallah and Bajaj [1] presented an algorithm for line stabbing simple objects in the plane, where a simple object is an object which has constant store description. Edelsbrunner, Guibas and Sharir [11] showed how to construct a representation of the line stabbers of convex polygons. O’Rourke [19] presented an algorithm for finding a stabbing line of vertical line segments. Goodrich and Snoeyink [12] presented a natural variant considering another type of stabbers different from the lines by solving the problem of computing a transversal convex polygon for a set of parallel segments. Bhattacharya et al. [4] worked on the problem of computing the shortest transversal segment for a set of lines in the plane and also for a set of convex polygons. Lyons et al. [15] studied the problem of computing the minimum perimeter convex polygon which stabs a set of isothetic line segments. Rappaport [20] considered the problem of computing a simple polygon with minimum perimeter which stabs or contains a set of line segments. Mukhopadhyay et al. [16–18] considered the problem of computing the minimum area convex polygon which stabs a set of parallel line segments. 2. Extreme lines This section is devoted to the study of the set of extreme lines for Sfrom a computational and from a combinatorial point of view, since we shall design algorithms for determining stabbers for Swhose complexities depend on the computation of this set of lines. We also introduce some terminology that shall be used throughout this paper. Alineis an extreme line for Sif stabs a subset of segments S1⊆Swith S1= ∅, and the remaining segments S2=S\S1lie in only one of the open half-planes defined by .Otherwise,is a non-extreme line for S.Wedenoteby+ (−) the left (right) open half-plane defined by a directed line .IfthesegmentsofS2lie in −(+), we say that is a left-extreme (right-extreme)lineforS.Thus,is an extreme line for Sif and only if is either left-extreme or right-extreme for S. There are two types of non-extreme lines for S:eitherdoes not intersect the convex hull of S,denotedbyCH(S), or the line intersects CH(S), and both half-planes +and −contain at least one segment of S. 2.1. Properties of extreme lines Next we show some properties about extreme lines. All omitted proofs are straightforward. 3A preliminary version of this paper was presented in EuroCG’09 [7]. M. Claverol et al. / Computational Geometry 44 (2011) 303–318 305 Fig. 2. Extreme lines and non-extreme lines with the same slope. Lemma 1. There always exist extreme lines for S with a given slope. Sweeping with a line of a given slope, the two types of non-extreme lines for S can appear. An endpoint of a segment or the segment itself determines the change from extreme to non-extreme line. Fig. 2 illustrates an instance of extreme lines and non-extreme lines with the same slope just sweeping with a line parallel to 1or to 5. Lemma 2. Every extreme line for S intersects at least one segment of S with an endpoint in CH(S), but the converse is not true. Moreover, for every segment s ∈S with at least one endpoint in CH(S)there exists an extreme line that only intersects s. Proof. Suppose on the contrary that is an extreme line for Swhich intersects a subset of segments of S, but none of the endpoints of those segments are located in CH(S). Then the segments stabbed by belong to the interior of CH(S), which implies that there is at least one segment of Slocated in each of the half-planes, +and −, with an endpoint in CH(S). Hence is a non-extreme line, which leads to a contradiction. The line 3in Fig. 2 proves that the converse is not true. Consider a segment s∈Swith an endpoint qin CH(S). To prove that there exists an extreme line that only intersects s, it suffices to consider the supporting line of CH(S)passing through q.2 Lemma 3. Alineis a stabbing line for S if and only if is both a left-extreme and a right-extreme line for S. A key consequence of Lemma 3 is the following. Suppose that Sis not stabbed by a line, and consider a directed line with any orientation. Sweeping Swith , it is not possible to go from a left-extreme to a right-extreme line. Necessarily, a non-extreme line for Sis obtained between the two types of lines. Definition 1. An endpoint qof a segment of Sis a critical point of Sfor a given orientation m, if any sweeping directed line with orientation mis either left-extreme or right-extreme and becomes non-extreme once it crosses q. Note that Lemma 1 implies that there is a critical point for each orientation. Extreme lines 2and 4in Fig. 2 define critical points. Definition 2. An extreme line is a critical line for Sif passes through a critical point. Critical lines and critical points play an important role in the design of our algorithms. The following rotating process allow us to visualize the sequences of critical points and critical lines for S(Fig. 3). Consider a directed critical line  which rotates clockwise anchored at critical points of S. The first critical point corresponds to the vertical-upwards directed critical line. When bumps a new critical point, then changes the anchored point to the new critical point, and both critical points are consecutive in the sequence of critical points. Denote by qthe critical point in which is anchored at some moment of the process. Let r qand l qbe the right and left ray, respectively, from qcontained in according to the orientation of . The following result is straightforward. Lemma 4. The directed critical line only can become non-extreme line for S after the ray r qpasses through an endpoint p of a segment s ∈S strictly contained in +. In this case, p becomes the next critical point for S. If p is the endpoint of the segment pq ∈S and the ray l qpasses through p, then p becomes the next critical point for S. Consider the sequence F1of critical points obtained when a directed critical line follows the rotating process abovedescribed, starting from a vertical-upwards directed critical line to a vertical-downwards directed critical line. A sequence F2is obtained by interchanging the roles of vertical-upwards and vertical-downwards. Denote by D1and D2the respective 306 M. Claverol et al. / Computational Geometry 44 (2011) 303–318 Fig. 3. Critical points ( fi) and directed critical lines ()ofS. Fig. 4. (Left) Upper envelope of the lower rays, (right) lower envelope of the upper rays of the segment set in Fig. 3. sequences of directed critical lines passing through two consecutive critical points. In order to compute D1and D2we first recall the following tool. A standard geometric tool which will be used throughout this work is duality [10]: the geometric transform denoted by Dwhich maps a point into a non-vertical line and vice versa. Thus, the dual transform Dmaps a point p=(a,b) to the non-vertical line D(p):y=2ax −band vice versa, that is, it maps a non-vertical line :y=cx +dto the point D() =(c/2,−d). A segment si∈Sis determined by its endpoints. The endpoints are transformed by Dinto two lines. If siis not vertical, D(si)is a double-wedge which does not contain a vertical line in its interior. Thus, the double-wedge is formed by two upper rays and two lower rays. If siis a vertical segment, D(si)is a strip. The set of endpoints of the segments in Sis transformed by Dinto an arrangement of 2nlines denoted by A(S). The transform Dsatisfies the following properties: (i) Dmaintains the relative position (above/below) of points and lines; (ii) a line intersects a segment siif and only if the point D() lies in the double-wedge D(si); (iii) the stabbing lines of Sstand in one-to-one correspondence with the intersection points of their double-wedges, i.e., si∈SD(si). Rappaport [20] used duality to design an O(nlogn)time algorithm for computing D1and D2, although his goal was to use these sequences for a different problem. His algorithm is essentially based on the following lemma for which it is assumed, without loss of generality, that Scontains no vertical segments. Thus for every s∈S, the double-wedge D(s) determines two upper rays and two lower rays. This result is also the key tool used by Edelsbrunner et al. [10] to design an algorithm for computing a representation of the stabbing lines of S. Lemma 5. (See [10,20].) The sequence D1(D2)corresponds in A(S)to the sequence of vertices of the lower (upper)envelope of the set of upper (lower)rays of D(s). Both sequences D1and D2have linear complexity. The lower (upper) envelope of the upper (lower) rays of D(s), forms a (not necessarily convex) x-monotone polygonal chain P1(P2) with a linear number of edges (see Fig. 4 for an example). Using Lemma 5, Rappaport [20] and Edelsbrunner et al. [10] presented a divide and conquer algorithm to obtain the following result. Theorem 1. (See [10,20].) The sequences D1and D2, and the polygonal chains P1and P2can be computed in O (nlogn)time and O(n)space. Since a stabbing line for Sis both left-extreme and right-extreme, Edelsbrunner et al. [10] computed the intersection of both polygonal chains P1and P2to obtain the cells in A(S)which define the locus of stabbing lines for S.ThusifSis not stabbed by a line, then the polygonal chains P1and P2do not intersect. M. Claverol et al. / Computational Geometry 44 (2011) 303–318 307 Fig. 5. (Left) Segment set Sand sequences (F1and F2) of critical points, (right) the shaded regions are the locus Lof extreme lines for S.Bothendpoints of segments 1 and 2 are critical points. Segment 6 is in CH(S)and so its endpoints become critical points. The polygonal chain P1is not convex since part of the double-wedge containing segments 1 and 6 belongs to P1. Analogously for P2due to segment 2. 2.2. Computing a representation of extreme lines Two lines, 1and 2,aresaidtobecombinatorially different with respect to Sif either the subsets S1and S2of segments stabbed by 1and 2, respectively, are different; or if S1=S2then the subsets of endpoints of segments above (left of) 1 and 2are different. Denote by hSand gSthe numbers of combinatorially different extreme lines and non-extreme-lines, respectively, for S. Observe that two extreme (or non-extreme) lines for S,1and 2, are combinatorially different with respect to Sif and only if the points D(1)and D(2)lie in different cells of A(S). Thus, we shall present an algorithm which computes a representation of all the extreme lines for Sin A(S). This representation is the locus Lof points in the plane (union of cells in A(S)) which correspond in the primal to extreme lines for S. The number of cells in Lis exactly equal to hS.Our algorithm shall compute the boundary of Land the cells inside L. Because there is no stabbing line for S, the locus Lis formed by two disjoint regions. We call the top and bottom boundaries of the union of cells in Lthe exterior boundary of L, and the two boundaries (polygonal chains) which separate the two disjoint regions of the union of cells in L,theinterior boundary of L(see Fig. 5). Let L1and L2be the sequences of edges of the exterior boundary and the interior boundary of L, respectively. By Lemmas 1, 2, 3, and 4 we have the following result. Lemma 6. The dual of the directed supporting lines of CH(S)forms the exterior boundary L1. Analogously, the dual of the directed critical lines of S forms the interior boundary L2. The sequence L1is formed by the upper and lower envelopes of A(S),theedgesofL2come from the dual of the sequence of critical points of S, and L2is the boundary of the set of cells of non-extreme lines for S.Moreover,sinceL2is formed by P1and P2the following result is a straightforward consequence of Lemmas 5 and 6 and Theorem 1. Lemma 7. The boundary L2of L can be computed in O(nlogn)time and O(n)space. If there is no stabbing line for S, i.e., P1and P2do not intersect, then Lis the union of two disjoint regions in A(S):the upper region Rudelimited by P1, and the lower region Rldelimited by P2(Fig. 5). If P1and P2intersect, the representation in A(S)of the set of stabbing lines for Sis Ru∩Rl. Next we show how to construct Ruand Rl. Construction of Ruand Rl.(a) Properties: Since Ruis bounded by P1(the upper envelope of the lower rays), the apices of the double-wedges (dual to segments of S) are all below or on P1(analogously they are all above or on P2because P2is the lower envelope of the upper rays). For each ray of a double-wedge, we record each side with +or −depending on which side of the double-wedge lies on (later we will used it to determine the segments of Sstabbed by extreme lines). Recall that P1and P2are x-monotone polygonal chains, starting and ending with rays. We focus on the construction of Ru (the construction of Rlis analogous). Let m1be the complexity of P1which is linear in n. (b) Preprocess: The 2nupper rays of the double-wedges contribute to the cells of Ruif and only if they intersect P1. TheoriginofeachupperrayisbeloworonP1.WeformfromP1two bounded simple polygons, by intersecting it with a large bounding box enclosing all of its vertices; one polygon lies below P1and one above. Now, we use the ray-shooting algorithm from Hershberger and Suri [13], which can preprocess the two polygons in O(m1)time to support O(logm1)- time ray-shooting queries. Now, for every upper ray, we repeatedly use the data structure to identify all of its intersections 308 M. Claverol et al. / Computational Geometry 44 (2011) 303–318 Fig. 6. Constructing Ru. Fig. 7. (a) hS=O(n2),(b)hS=6, (c) non-intersecting segments. with P1, at the cost of O(logm1)per intersection. If the upper ray has more that one intersection point we compute the segments (with endpoints on P1) contained inside Ruformed by consecutive intersection points. All those segments will contribute to the arrangement of cells in Ru.Letm2(m3) be the number of rays (segments) obtained in this way. These sets of rays and segments can be computed in O((m2+m3)logm1)time. Note that m1and m2are linear in n,butm3can be quadratic since an upper ray can intersects P1many times (see Fig. 6). (c) Computation: The arrangement of cells in Ruis simple, that is, no three lines pass through the same point (which is true by the assumption that the endpoints of the segments in Sare in general position) and no two lines are parallel (assuming that no two endpoints of segments in Sshare the same vertical line: in O(nlogn)time we can rotate the coordinate system to achieve this). From the set of m1+m2+m3rays and segments we can compute the arrangement of the hScells in Ruusing topological sweep [9] (see also Balaban’s algorithm [3]) in O((m1+m2+m3)log(m1+m2+m3)+ hS)time and O(hS+n)space. The time complexity is slightly better than O(hSloghS)as hSis between m1+m2+m3 and Θ((m1+m2+m3)2). The cells in Rlare constructed similarly. We now describe the algorithm which computes a representation of all the extreme lines for S. Algorithm 1. Representation-extreme-lines Input:SetSof nsegments in the plane. Output:L1,L2, and the set of cells in L. 1. In O(nlogn)time, compute L1as the upper and lower envelopes of A(S). 2. Use Theorem 1 to compute L2in O(nlogn)time. L2is formed by P1and P2.IfP1and P2do not intersect, then Lis formed by the regions Ruand Rl. The complexities of P1,P2, and L2are O(n). 3. In O(hSloghS)time and O(hS)space, compute the set of hScells in Ruand Rlwhich forms L, i.e., the set of all the combinatorially different extreme lines for S. Theorem 2. A representation of the combinatorially different extreme lines for S can be computed in O(hSloghS+nlogn)time and O(hS+n)space. Notice that when hSis constant (as in Fig. 7(b)) or linear, the complexities of Algorithm 1 are O(nlogn)time and O(n) space. 2.3. Bounds for hSand gS Clearly, |CH(S)|⩽hSand the number hSis at most O(n2). A nice instance, showing that the upper bound is tight, is the segment set proposed by Claverol [6] (Fig. 7(a)). On the other hand, there are at least two combinatorially different non-extreme lines for S, the line which does not intersect CH(S)and CH(S)is either above or below .Thus,2⩽gS. Consider now the intersection graph G=(V,E)whose vertex set is V=S, and two segments s1and s2are adjacent if and only if s1∩s2= ∅.LetGc=(V,Ec)be the complementary graph of G.IfSis formed by pairwise non-intersecting segments, M. Claverol et al. / Computational Geometry 44 (2011) 303–318 309 Fig. 8. (a) Classifying the endpoints of a segment with respect to , (b) and (c) the two possible classifications of a given segment set where is parallel to segments s1,s2and s3. then every pair of segments gives rise to at least one non-extreme line (Fig. 7(c)) and hence gS⩽|Ec|=n 2=O(n2).Thus, 2⩽gS⩽O(n2)and the bounds are tight. 2.4. Computing a representation of critical lines As mentioned earlier, among extreme lines, critical lines play an important role in our algorithms. These lines are points in the cells of A(S), called critical cells, which have one edge in either P1or P2. Our next aim is to compute a representation of the combinatorially different critical lines. All the critical cells in Ruhave an edge in P1(analogously, critical cells in Rlhave an edge in P2), and two of them are adjacent if they share a segment (or ray) with endpoint in P1.SinceP1is an x-monotone polygonal chain, then we can walk on P1from one critical cell to an adjacent critical cell with the unique change of the shared edge according to the labels of the edge: crossing from +to −or from −to +. To do that we need to compute the intersection points of the upper rays above with P1and to sort them by increasing x-coordinate (because P1is x-monotone). Recall from above that there are O(m2+m3)intersection points, and they can be sorted in O((m2+m3)log(m2+m3)) time and O(m2+m3)space (see Fig. 6). As initial stage we need to compute the leftmost critical cell, or in other words, the set of endpoints on the left of the vertical-upwards directed critical line which is anchored in the first critical point. This can be done in O(nlogn)time. Now, walking from left to right along P1we visit all critical cells (the dual graph of the critical cells is a tree and we can cross a segment at most twice). Then computing a point from all the combinatorially different critical cells can be done in O((m2+ m3)log(m2+m3)+nlogn)time and O((m2+m3)+n)space. Note that m2+m3<cSbecause a ray or a segment contributes to at least one critical cell. Thus, O((m2+m3)log(m2+m3)) is slightly better than O(cSlog cS), and a representation of all the combinatorially different critical lines can be computed in O(cSlogcS+nlogn)time and O(cS+n)space. Theorem 3. A representation of the combinatorially different critical lines for S can be computed in O(cSlog cS+nlogn)time and O(cS+n)space. Note that cScan be quadratic, one can constructs examples where many upper rays intersect P1many times (see Fig. 6). 3. Stabbing wedge Let W={1, 2}be a stabbing wedge for S, where 1and 2are the two rays of W. The line containing iis denoted by  ifor i=1,2. The half-planes defined by  iare written as  i +and  i −. We can assume that Sis not stabbed by a line what implies that 1stabs a subset of segments S1Swith S1= ∅, and the set S2=S\S1is stabbed by 2. The aim of this section is to study the problem of computing stabbing wedges for Swith or without the separability condition. Denote by mithe slope of (the line containing) the segment si∈S,andbykSthe number of different slopes of the segments of S.Givenalineand a segment s, we can classify the endpoints of swith respect to whenever and the line containing sare not parallel. It suffices to do a parallel sweeping by a line until it crosses s, leaving one endpoint in +, and the other one in −. These endpoints are denoted by e+and e−, respectively (see Fig. 8(a)). If and the line containing sare parallel, the endpoints of scannot be classified. Indeed, there are two possible classifications of the endpoints of those segments: the endpoint with bigger y-coordinate of each segment is classified into e+and the other one into e−,orvice versa (Figs. 8(b) and 8(c)). Lemma 8. Any parallel sweeping by a line with a fixed slope gives rise to at most 2classifications of the endpoints of the segments of S. Proof. Consider a line with slope m.Ifm= mifor i=1,...,kS, then the endpoints of each segment can be classified into e+and e−giving rise to exactly one classification. Assume now that m=miand that there are some segments of Swith slope mi. Since these segments are parallel to , there are two possible classifications of the endpoints of those segments 310 M. Claverol et al. / Computational Geometry 44 (2011) 303–318 Fig. 9. A stabbing wedge for Sand the point sets S+ 1,S− 1,S+ 2,andS− 2. as we said above. For horizontal segments, consider the endpoint with bigger x-coordinate in order to distinguish the two possible assignments. 2 3.1. Stabbing wedges with the separability condition Let W={1, 2}be a stabbing wedge for Swith the separability condition, i.e., no segment can be stabbed by both rays. Let S+ i(S− i)fori=1,2, be the set of endpoints of the segments of Siclassified as e+(e−)withrespectto i.Thus,S− 1and S+ 2are contained inside the wedge W, and S+ 1and S− 2are located outside the wedge W(Fig. 9). These assignments {+,−} depend on the relative position of the lines  1and  2. We shall mainly concentrate on a general wedge as the one shown in Fig. 9. The following lemma is straightforward. Lemma 9. If W ={1, 2}is a stabbing wedge for S, then  1and  2are extreme lines for S, and at least half of the segments of S are stabbed by either 1or 2. The next two results use the following notation. The line  1is an extreme line for S.ThesetS1Swith S1= ∅,isthe segment subset stabbed by  1, and S2=S\S1.DenotebyS+ 1and S− 1the classification of the endpoints of the segments of S1given by  1according to Lemma 8. The sets S+ 2and S− 2are the classification of the endpoints of the segments of S2 obtained by sweeping with a line, say  2,withfixedslopemaccording to Lemma 8. Lemma 10. There exists a stabbing wedge W ={1, 2}for S with 1contained in  1if and only if S− 2is line separable from S− 1∪S+ 2 by the line  2. Proof. Given a stabbing wedge W={1, 2}for Swith 1stabbing S1and 2stabbing S2=S\S1, the line  2separates S− 2from S− 1∪S+ 2(see Fig. 9). Denote by mthe slope of the sweeping line  2according to Lemma 8. Since  1is an extreme line, we can assume that S2is contained in  1 −. Observe that S− 1∪S+ 2is contained in both half-planes  2 +and  1 −.Thus, the segments of Sare all stabbed by  1and by  2. The intersection point pof  1and  2is the apex of a stabbing wedge W={1, 2}for Ssuch that  icontains the half-line ifor i=1,2. Moreover, since S− 1∪S+ 2⊂ 2 +∩ 1 −then no segment of Sis stabbed by the two rays 1and 2.2 Lemma 11. The locus of apices of stabbing wedges W for S with respect to the classification of endpoints into S+ iand S− ifor i =1,2, can be computed in O(nlogn)time. The four interior supporting lines between CH(S+ 1)and CH(S− 1∪S+ 2), and between CH(S− 1∪S+ 2) and CH(S− 2)defineatmosttwo(possible unbounded and degenerate)convex quadrilateral Q whose interior points are apices of stabbing wedges for S. Proof. Clearly CH(S− 1∪S+ 2)is contained inside W.Thus,Wseparates the endpoints in CH(S− 1∪S+ 2)from the remaining endpoints. Hurtado et al. [14] show how to compute the locus of apices of all these separating wedges Win O(nlogn) time. 2 Definition 3. Two stabbing wedges W1and W2for Sare combinatorially different if the sets of endpoints of segments inside the wedges W1and W2are different. M. Claverol et al. / Computational Geometry 44 (2011) 303–318 311 Fig. 10. Two combinatorially different stabbing wedges with the same apex. It is easy to construct a segment set having two combinatorially different stabbing wedges with the same apex (Fig. 10). Thus, there is not a one-to-one correspondence between apices and combinatorially different stabbing wedges. Lemmas 9, 10, and 11 are the key tools to design the next algorithm for computing the set Wof combinatorially different stabbing wedges for Sand a set QWof convex quadrilaterals Qwhich are a representation of those stabbing wedges. Algorithm 2. Stabbing-wedges-with-separability-condition Input:SetSof nsegments in the plane. Output:Wand QW. 1. Preprocess: (a) In O(nlogkS)time, sort the kSdifferent slopes of the segments by increasing angular order. Denote them by m1,...,mkS. (b) Use Algorithm 1 to compute the set of hScells of Lin O(hSloghS+nlogn)time and O(hS+n)space. In O(hS) time compute the dual graph Gof Land do a traversal of Gobtaining a tree. Following the tree-traversal (visiting each edge of the tree at most twice) we can get a sequence of h S=O(hS)of nodes of the tree, i.e., a sequence C=(C1,...,Ch S)of adjacent cells of L: a sequence for the cells in Ru, and a sequence for the cells in Rl. (c) Select a point p(1,1)∈C1.LetD(p(1,1)):=  1,(1,1). Compute the set of segments stabbed by  1,(1,1),writtenasS1,(1,1), and S2,(1,1)=S\S1,(1,1). Classify the endpoints of the segments of S1,(1,1)with respect to  1,(1,1)obtaining the sets S+ 1,(1,1)and S− 1,(1,1).ComputeCH(S+ 1,(1,1))and CH(S− 1,(1,1)).Withtheslopem1determine the classification of the endpointsofthesegmentsinS2,(1,1), i.e., at most two pairs (S+ 2,(1,1),S− 2,(1,1)).ComputeCH(S+ 2,(1,1))and CH(S− 2,(1,1)). 2. For i=1,...,kSdo For j=1,...,h Sif iis odd and for j=h S,...,1ifiis even do (a) If i=j=1, use the data computed in Step 1c and go to Step 2d. (b) Select a point p(i,j)∈Cj.LetD(p(i,j)):=  1,(i,j). The difference between the segment sets stabbed by  1,(i,j−1)and  1,(i,j)is at most one segment ssince the cells Cj−1and Cjare adjacent. This segment scan be stabbed by  1,(i,j−1) and not by  1,(i,j)or vice versa. (c) From sand the sets S+ 1,(i,j−1),S− 1,(i,j−1),S+ 2,(i,j−1), and S− 2,(i,j−1), in constant time update: (1) S1,(i,j)is the set of segments stabbed by  1,(i,j)and S2,(i,j)=S\S1,(i,j);(2)thesetsofendpointsS+ 1,(i,j),S− 1,(i,j)classified with respect to  1,(i,j); and (3) the (at most two) pairs of sets of endpoints (S+ 2,(i,j),S− 2,(i,j))classified with respect the slope mi. For each pair proceed as follows. (d) In O(logn)time, update CH(S+ 1,(i,j)),CH(S− 1,(i,j)∪S+ 2,(i,j)), and CH(S− 2,(i,j))and check whether CH(S− 1,(i,j)∪S+ 2,(i,j)) and CH(S− 2,(i,j))are line separable by a line, say  2,(i,j). If so, by Lemma 10, there exists a stabbing wedge W(i,j)for Swith apex in the intersection point of  1,(i,j)and  2,(i,j).ComputethiswedgeW(i,j)={1,(i,j), 2,(i,j)}.AddW(i,j) to W. Compute the quadrilateral Q(i,j)defined by the interior supported lines between CH(S+ 1,(i,j))and CH(S− 1,(i,j)∪S+ 2,(i,j)) and the interior supported lines between CH(S− 1,(i,j)∪S+ 2,(i,j))and CH(S− 2,(i,j)).AddQ(i,j)to QW. Theorem 4. The set Wof combinatorially different stabbing wedges for S with the separability condition and the set QWcan be computed in O(hSkSlogn+nlogn)time and O(hS+n)space. Proof. Step 1 of Algorithm 2 can be done in O(hSloghS+nlogn)time and O(hS+n)space since its complexity is dominated by the complexity of Algorithm 1. The time complexity of Step 2 is O(kShSlogn)since convex hulls can be updated by insertions/deletions in O(logn)time [5]. The total cost is O(hSkSlogn+nlogn)time and O(hS+n)space. There are at most hScombinatorially different stabbing wedges for Ssince each one can be defined by an extreme line. 2 Corollary 1. The set Wof combinatorially different stabbing wedges for a set of n parallel segments with the separability condition and the set QWcan be computed in O(hSlogn+nlogn)time and O(hS+n)space. 318 References [1] M. Atallah, C. Bajaj, Efficient algorithms for common transversal, Inform. Process. Lett. 25 (1987) 87–91. [2] D. Avis, J.-M. Robert, R. Wenger, Lower bounds for line stabbing, Inform. Process. Lett. 33 (1989) 59–62. [3] I.J. Balaban, An optimal algorithm for finding segments intersections, in: 11th Sympos. on Comput. Geom., 1995, pp. 211–219. [4] B.K. Bhattacharya, J. Czyzowicz, P. Egyed, G. Toussaint, I. Stojmenovic, J. Urrutia, Computing shortest transversals of sets, in: Sympos. Comput. Geom., 1991, pp. 71–80. [5] G.S. Brodal, R. Jacob, Dynamic planar convex hull, in: Proceedings of the 43rd Annual IEEE Symposium on Foundations on Computer Science, 2002, pp. 617–626. [6] M. Claverol, Problemas geométricos en morfología computacional, PhD thesis, Universitat Politècnica de Catalunya, 2004. [7] M. Claverol, D. Garijo, C.I. Grima, A. Márquez, C. Seara, Stabbers of line segments in the plane, in: European Workshop of Computational Geometry, 2009. [8] H. Edelsbrunner, Algorithms in Combinatorial Geometry, EATCS Monographs on Theoretical Computer Science, vol. 10, Springer-Verlag, 1987. [9] H. Edelsbrunner, L.J. Guibas, Topologically sweeping an arrangement, J. Comput. System Sci. 38 (1989) 165–195; J. Comput. System Sci. 42 (1991) 249–251, Corrigendum. [10] H. Edelsbrunner, H.A. Maurer, F.P. Preparata, A.L. Rosenberg, E. Welzl, D. Wood, Stabbing line segments, BIT 22 (1982) 274–281. [11] H. Edelsbrunner, L.J. Guibas, M. Sharir, The upper envelope of piecewise linear functions: algorithms and applications, Report no. UIUCDCS-R-87-1390, University of Illinois, 1987. [12] M.T. Goodrich, J.S. Snoeyink, Stabbing parallel segments whit a convex polygon, in: Proc. 1st Workshop Algorithms and Data Structures, in: Lecture Notes in Computer Science, vol. 382, Springer-Verlag, 1989, pp. 231–242. [13] J. Hershberger, S. Suri, A pedestrian approach to ray shooting: shoot a ray, take a walk, J. Algorithms 18 (1995) 403–431. [14] F. Hurtado, M. Noy, P.A. Ramos, C. Seara, Separating objects in the plane by wedges and strips, Discrete Appl. Math. 109 (2000) 109–138. [15] K.A. Lyons, Henk Meijer, David Rappaport, Minimum polygon stabbers of isothetic line segments, Dept. of Computing and Information Science, Queen’s University, Canada, 1990. [16] A. Mukhopadhyay, C. Kumar, B.K. Bhattacharya, Computing an area-optimal convex polygonal stabber of a set of parallel line segments, in: 5th Canad. Conf. Comput. Geometry, 1993, pp. 169–174. [17] A. Mukhopadhyay, C. Kumar, E. Greene, B. Bhattacharya, On intersecting a set of parallel line segments with a convex polygon of minimum area, Inform. Process. Lett. 105 (2008) 58–64. [18] A. Mukhopadhyay, E. Greene, S.V. Rao, On intersecting a set of isothetic line segments with a convex polygon of minimum area, in: Workshop on Computational Geometry and Applications, 2007, pp. 41–54. [19] J. O’Rourke, An on-line algorithm for fitting straight lines between data ranges, Comm. ACM 24 (1981) 574–578. [20] D. Rappaport, Minimum polygon transversals of line segments, Internat. J. Comput. Geom. Appl. 5 (3) (1995) 243–256.