6 006 Introduction to Algorithms Lecture 24 Geometry Prof Erik Demaine Today Computational geometry Line segment intersection Sweep line technique Closest pair of points Divide conquer strikes back Motivation Collision Detection photo by fotios lindiakos http www flickr com photos fotios lindiakos 342596118 Motivation Collision Detection photo by fotios lindiakos http www flickr com photos fotios lindiakos 342596118 GTA 4 Carmageddon by dot12321 http www youtube com watch v 4 620xx7yTo Line Segment Intersection Input line segments in 2D Goal Find the intersections Obvious Algorithm for every pair of line segments check for intersection Sweep Line Technique Idea Sweep a vertical line from left to right Maintain intersection of line with input Sweep Line Intersections Sweep Line Events Discretize continuous motion of sweep line Events when intersection changes Segment endpoints Intersections Sweep Line Algorithm Sketch Maintain sweep line intersection Maintain priority queue of possible event coordinates of sweep line times Until queue is empty Delete minimum event time from priority queue to Update sweep line intersection from Update possible event times in priority queue Discrete event simulation Intersection Data Structure Balanced binary search tree e g AVL tree to store sorted order of intersections Endpoint Events For each line segment At At insert binary search for neighbors then delete Intersection Events How to know when have intersection events This is the whole problem Intersection Events Compute when neighboring segments would intersect if nothing changes meanwhile If such an event is next then it really happens Sweep Line Algorithm while if is not empty is insert into binary searching with elif is 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 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 time Best algorithm runs in Closest Pair of Points Input points in 2D Goal find two closest points Obvious Algorithm min distance for 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 Pair Between Two Halves Let min closest pair in each half Only interested in pairs with distance Restrict to window of width around middle Closest Pair Between 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 time by merging two sorted arrays Divide and Conquer presort points by def sort by sort by merge and find closest pair between two lists return min closest distance from merge Faster Divide and Conquer Shamos Hoey 1975 presort points by and and cross link points def map to ypoints find closest pair between lists return min closest distance from merge Other Computational Geometry Problems Convex hull Voronoi diagram Triangulation Point location Range searching Motion planning 6 850 Geometric Computing
View Full Document
Unlocking...