6.006Introduction to AlgorithmsLecture 24: GeometryProf. Erik DemaineToday• Computational geometry• Line‐segment intersection– Sweep‐line technique• Closest pair of points– Divide & conquer strikes back!Motivation: Collision Detectionphoto by fotios lindiakoshttp://www.flickr.com/photos/fotios_lindiakos/342596118/Motivation: Collision Detectionphoto by fotios lindiakoshttp://www.flickr.com/photos/fotios_lindiakos/342596118/“GTA 4 Carmageddon!” by dot12321http://www.youtube.com/watch?v=4-620xx7yToLine‐Segment Intersection• Input: line segments in 2D• Goal: Find the intersectionsObvious Algorithmfor every pair of line segments:check for intersectionSweep‐Line Technique• Idea: Sweep a vertical line from left to right• Maintain intersection of line with inputSweep‐Line IntersectionsSweep‐Line Events• Discretize continuous motion of sweep line• Events when intersection changes– Segment endpoints – IntersectionsSweep‐Line Algorithm Sketch• Maintain sweep‐line intersection• Maintain priority queue of (possible) event times (coordinates of sweep line)• Until queue is empty:– Delete minimum event time from priority queue– Update sweep‐line intersection from to – Update possible event times in priority queue“Discrete‐event simulation”Inte rsection Data Structure• Balanced binary search tree (e.g., AVL tree) to store sorted () order of intersectionsEndpoint Events• For each line segment :– At : insert (binary search for neighbors then)– At : deleteInte rsection Events?• How to know when have intersection events?• This is the whole problem!Inte rsection Events• Compute when neighboring segments would intersect, if nothing changes meanwhile• If such an event is next, then it really happenswhile is not empty:if is :insert into (binary searching with )elifis :delete from elif is :report intersection between and swap contents of nodes for and in for each node changed or neighboring changed in :delete all events involving from add & to Sweep‐Line AlgorithmSweep‐Line Analysis• Running time = • Number of endpoint events = • Number of meet events =number of intersections = size of output• Running time = • Output sensitive algorithm:running time depends on size of output• Best algorithm runs in timeClosest Pair of Points• Input: points in 2D• Goal: find two closest pointsObvious Algorithmmin(distancefor every pair of points)Divide‐and‐Conquer Idea• Initially sort points by coordinate• Split points into left half and right half• Recurse on each half: find closest pair• return min{closest pair in each half,closest pair between two halves}Closest PairBetween Two Halves?• Let = min{closest pair in each half}• Only interested in pairs with distance • Restrict to window of width around middleClosest PairBetween Two Halves• For each left point, interested in points on right within distance • Points on right side can’t be within of each other• So at most three right points to consider for each left point– Ditto for each right point• Can compute in timeby merging two sorted arraysDivide‐and‐Conquerpresort points by def :sort by sort by merge and find closest pair between two listsreturn min{, closest distance from merge}Faster Divide‐and‐Conquer[Shamos & Hoey 1975]presort points by and , and cross link pointsdef:map to ypoints & find closest pair between listsreturn min{, closest distance from merge}Other Computational Geometry Problems• Convex hull• Voronoi diagram• Triangulation• Point location• Range searching• Motion planning• …6.850: Geometric
View Full Document
Unlocking...