Introduction to Algorithms February 3, 2005 L2.1© 2003 by Piotr IndykSegment IntersectionPiotr IndykIntroduction to Algorithms February 3, 2005 L2.2© 2003 by Piotr IndykComputational Geometry ctd.• Segment intersection problem:– Given: a set of n distinct segments s1…sn, represented by coordinates of endpoints– Detection: detect if there is any pair si≠ sjthat intersects– Reporting: report all pairs of intersecting segmentsIntroduction to Algorithms February 3, 2005 L2.3© 2003 by Piotr IndykSegment intersection• Easy to solve in O(n2) time• Is it possible to get a better algorithm for the reporting problem ?•NO(in the worst-case)• However:– We will see we can do better for the detection problem– Moreover, the number of intersections P is usually small. Then, we would like an output sensitive algorithm, whose running time is low if P is small.Introduction to Algorithms February 3, 2005 L2.4© 2003 by Piotr IndykResult• We will show:– O(n log n) time for detection– O( (n +P) log n) time for reporting• We will use line sweep approach– Many other applications, e.g.,Voronoidiagrams, motion planningIntroduction to Algorithms February 3, 2005 L2.5© 2003 by Piotr IndykOrthogonal segments• All segments are either horizontal or vertical• Assumption: all coordinates are distinct• Therefore, only vertical-horizontal intersections existH-segmentV-segmentIntroduction to Algorithms February 3, 2005 L2.6© 2003 by Piotr IndykOrthogonal segments• Sweep line:–A vertical line sweeps the plane from left to right– It “stops” at all “important”x-coordinates, i.e., when it hits a V-segment or endpoints of an H-segment– Invariant: all intersections on the left side of the sweep line have been already reportedIntroduction to Algorithms February 3, 2005 L2.7© 2003 by Piotr IndykOrthogonal segments ctd.• We maintain sorted y-coordinates of H-segments currently intersected by the sweep line (using a balanced BST V)• When we hit the left point of an H-segment, we add its y-coordinate to V• When we hit the right point of an H-segment, we delete its y-coordinate from V1712Introduction to Algorithms February 3, 2005 L2.8© 2003 by Piotr IndykOrthogonal segments ctd.• Whenever we hit a V-segment having coord. ytop, ybot), we report all H-segments in V with y-coordinates in [ytop, ybot]ytopybot1712Introduction to Algorithms February 3, 2005 L2.9© 2003 by Piotr IndykAlgorithm• Sort all V-segments and endpoints of H-segments by their x-coordinates – this gives the “trajectory” of the sweep line• Scan the elements in the sorted list:– Left endpoint: add segment to tree V– Right endpoint: remove segment from V– V-segment: report intersections with the H-segments stored in VIntroduction to Algorithms February 3, 2005 L2.10© 2003 by Piotr IndykAnalysis• Sorting: O(n log n)• Add/delete H-segments to/from vertical data structure V: –O(logn)per operation–O(nlog n)total• Processing V-segments:–O(logn)per intersection - SEE NEXT SLIDE– O(P log n) total• Overall: O( (P+ n) log n) time• Can be improved to O(P +n log n)Introduction to Algorithms February 3, 2005 L2.11© 2003 by Piotr IndykAnalyzing intersections• Given:–A BST V containing y-coordinates– An interval I=[ybot,ytop]• Goal: report all y’s in V that belong to I • Algorithm:–y=Successor(ybot)– While y≤ytop• Report y•y:=Successor(y)–End• Time: (number of reported y’s)*O(logn) + O(logn)Introduction to Algorithms February 3, 2005 L2.12© 2003 by Piotr IndykThe general case• Assumption: all coordinates of endpoints and intersections distinct• In particular:– No vertical segments– No three segments intersect at one pointIntroduction to Algorithms February 3, 2005 L2.13© 2003 by Piotr IndykSweep line• Invariant (as before): all intersections on the left of the sweep line have been already reported• Stops at all “important” x-coordinates, i.e., when it hits endpoints or intersections• Problem I: Do not know the intersections in advance !• The list of intersection coordinates is constructed and maintained dynamically(in a “horizontal” data structure H)Introduction to Algorithms February 3, 2005 L2.14© 2003 by Piotr IndykSweep line• Also need to maintain the information about the segments intersecting the sweep line• Problem II: Cannot keep the values of y-coordinates of the segments !• Instead, we will maintain their order.I.e., at any point, we maintain all segments intersecting the sweep line, sorted by the y-coordinates of the intersections(in a “vertical” data structure V)• Key idea: check only for the intersections of segments that are neighbors in VHVIntroduction to Algorithms February 3, 2005 L2.15© 2003 by Piotr IndykJava applet• http://www.lems.brown.edu/~wq/projects/cs252.html• Example used in the lecture:Introduction to Algorithms February 3, 2005 L2.16© 2003 by Piotr IndykAlgorithm• Initialize the “vertical” BST V (to “empty”)• Initialize the “horizontal” priority queue H (to contain the segments’ endpoints sorted by x-coordinates)• Repeat– Take the next “event” p from H:// Update V– If p is the left endpoint of a segment, add the segment to V– If p is the right endpoint of a segment, remove the segment from V– If p is the intersection point of s and s’, swap the order of s and s’ in V, report p(continued on the next slide)Introduction to Algorithms February 3, 2005 L2.17© 2003 by Piotr IndykAlgorithm ctd.// Update H– For each new pair of neighbors s and s’ in V:• Check if s and s’ intersect on the right side of the sweep line• If so, add their intersection point to H• Remove the possible duplicates in H• Until H is emptyIntroduction to Algorithms February 3, 2005 L2.18© 2003 by Piotr IndykAnalysis• Initializing H: O(n log n)• Updating V: –O(logn)per operation– O( (P+n) log n) total• Updating H:–O(logn)per intersection– O(P log n) total• Overall: O( (P+ n) log n) timeIntroduction to Algorithms February 3, 2005 L2.19© 2003 by Piotr IndykCorrectness• All reported intersections are correct• Assume there is an intersection not reported. Let p=(x,y)be the first such unreported intersection (of s and s’ )• Let x’ be the last event before p. Observe that:– At time x’ segments s and s’ are neighbors on the sweep line– Since no intersections were missed till then, Vmaintained the right order of