Introduction to Algorithms, Lecture 5 September 24, 2001© 2001 by Charles E. Leiserson 1CS 445Computational GeometryAlon EfratSlides courtesy of Erik Demaine with small changes by Carola WenkComputational geometryAlgorithms for solving “geometric problems”in 2D and higher.Fundamental objects:point line segment lineBasic structures:polygonpoint setComputational geometryAlgorithms for solving “geometric problems”in 2D and higher.Fundamental objects:point line segment lineBasic structures:convex hulltriangulationLine-segment intersectionGiven n line segments, •does any pair intersect? •Report all intersections pairs (not in this course) •Require a slght massaging of the algorithm, Obvious algorithm: O(n2) – checking all pairs.Line-sweep – O(n log n) to decide if there is an intersection.abcdefApplications 1: Checking VLSI design correctness Need to decide if two components intersect (bug in desion)Applications 2: computing allintesrction points Applications: Map overlaying: compute all points at which a road crosses a river.cIntroduction to Algorithms, Lecture 5 September 24, 2001© 2001 by Charles E. Leiserson 2Assumptions-general position• No vertical segment• No two endpoints of segments have the same y-coordinate.• The line containing a segment does not contain the endpoint of another segment• If the segments satisfies all assumptions, we say that they are in general positioIf the segments satisfies all assumptions, we say that they are in a general position. 2-segment intersection• Test whether segments (a,b) and (c,d) intersect. How do we do it?• Method 1: Write down the equations of the lines through the segments:•Express the line through thefirst segment as y=mx+n •Express the line through the second segment as y=m’x+n’•Find intersection point between the lines. •Check if the intersection point lies on the segments. O(1) time.2-segment Intersection• An alternative (and safer) approach is based in the notion of orientation of an ordered triplet of points in the planePrimitive operations:CrossproductGiven two vectors v1= (x1, y1) and v2= (x2, y2),is their counterclockwise angle θ• convex (< 180º),• reflex (> 180º), or• borderline (0 or 180º)?v1v2θv2v1θconvex reflexCrossproduct v1× v2= x1y2– y1x2= |v1| |v2| sin θ .Thus, sign(v1× v2) = sign(sin θ) > 0 if θ convex,< 0 if θ reflex,= 0 if θ borderline.Primitive operations:Orientation testGiven three points p1, p2, p3are they• in clockwise (cw) order,• in counterclockwise (ccw) order, or• collinear?(p2– p1) × (p3– p1)> 0 if ccw< 0 if cw= 0 if collinearp1p3p2cwp1p2p3ccwp1p2p3collinearPrimitive operations:Sidedness testGiven three points p1, p2, p3are they• in clockwise (cw) order,• in counterclockwise (ccw) order, or• collinear?Let L be the oriented line from p1to p2.Equivalently, is the point p3• right of L,• left of L, or• on L?p1p3p2cwp1p2p3ccwp1p2p3collinearLLIntroduction to Algorithms, Lecture 5 September 24, 2001© 2001 by Charles E. Leiserson 3Intersection and Orientation• Two segments (p1q1) and (p2,, q2) intersect if and only if the following two conditions are satisfied• General case:– p2and q2are on different sides of the line passing through p1and q1,• and– p1and q1 are on different sides of the line passing through p2and q2Intersection and Orientation• Two segments (p1,q1) and (p2, q2) intersect iff– (p1,q1,p2) and (p1,q1,q1) have different orientations • and– (p2,q2,p1) and (p2,q2,q1) have different orientationsabcdefPlanned events (left/right endpoints)Sweep-line algorithmabcdSweep a vertical line from left to rightThe line “knows” which segment it intersect and at which order (conceptually replacing x-coordinate with time).Sweep-line algorithm• Sweep a vertical line from left to right(conceptually replacing x-coordinate with time).• Maintain dynamic set S of segmentsthat intersect the sweep line, ordered(tentatively) by y-coordinate of intersection.• Order changes when• new segment is encountered (left endpoints),• existing segment finishes (right endpoint)•Event points are therefore segment endpoints.abcdefaabbca abcdbdcbedbdceSPlanned events (left/right endpoints)The status of the linesweep abcdeS={d,b,a,c,e}The status S is the list of segments that linesweep lintersects (in the order from bottom to top). Definintion: an event happens when l start/stop intersecting a segment.Note: the status is not changed between events, so l can jump from an event to the next event. lIntroduction to Algorithms, Lecture 5 September 24, 2001© 2001 by Charles E. Leiserson 4Algorithm - overview • Sweep with vertical line l from left to right(I.e. scan the endpoints in increasing ordered of x-coordinate)• Each time that l meets an endpoint –1. Update the status 2. Check segments intersection as described in the next slides.Left endpoint event: Process event points in order by sorting segmentendpoints by x-coordinate and looping through:• For a left endpoint of segment s:• Add segment s to dynamic set S.• Check for intersection between sand its neighbors in S.abcdeExample: a is checked for intersection with c and intersection with b.S={d,b,a,c,e}Right endpoint eventProcess event points in order by sorting segmentendpoints by x-coordinate and looping through:• For a right endpoint of segment s:• Delete segment s from dynamic set S.• Check for intersection between neighbors sand its neighbors in S.abcdeExample: c is checked for intersection with b.S={d,b,a,c,e}Proof: Let X be the leftmost intersection point.At some point before we reach X,c and b become consecutive in the order of S.If they are not consecutive on the linesweep, it is because another segment, say a separates between them. Theorem: If there is an intersection,the algorithm finds it.abcdBut then either a intersects bor c at a point to the left of X, or a has a right endpoint to the left of X. aXMaintaining the status SabcdfTlabdfWe maintain the list of segment that intersect l in a sorted search tree T, sorted by the order they appear along l. When we insert a segment, we compare y-coordinates of intersections of segments with l.Note: The y-coordinate change as l moves, but the order is changing only at events. cggOperations on the treeabcdfTlabdfInsert(T,s) - Insert the segment s into the Tree T. Delete(T,s) Above(T,s) - Find the segment just below s. Example Above(T,b) = c. (successor oprtaion in T)Below(T,s)–