planesweep.pdf

Outline Orthogonal Segment Intersection Finding A Closest Pair Of Points The Plane Sweep Technique Rynard Badenhorst May 18, 2007 Rynard Badenhorst The Plane Sweep Technique Outline Orthogonal Segment Intersection Finding A Closest Pair Of Points Orthogonal Segment Intersection Finding A Closest Pair Of Points Rynard Badenhorst The Plane Sweep Technique Outline Orthogonal Segment Intersection Finding A Closest Pair Of Points Orthogonal Segment Intersection First problem solved using plane-sweep technique is that of finding all the intersecting pairs among a set of n line segments I Brute Force: O(n2) since number of pairs n(n ? 1)/2 or I Orthogonal Segments ? each segment in set is either horizontal or vertical I If s is the number of intersecting pairs, an algorithm using the plane-sweep technique runs in O(nlogn + s) time Rynard Badenhorst The Plane Sweep Technique Outline Orthogonal Segment Intersection Finding A Closest Pair Of Points Orthogonal Segment Intersection First problem solved using plane-sweep technique is that of finding all the intersecting pairs among a set of n line segments I Brute Force: O(n2) since number of pairs n(n ? 1)/2 or I Orthogonal Segments ? each segment in set is either horizontal or vertical I If s is the number of intersecting pairs, an algorithm using the plane-sweep technique runs in O(nlogn + s) time Rynard Badenhorst The Plane Sweep Technique Outline Orthogonal Segment Intersection Finding A Closest Pair Of Points But Before We Go On ... One-Dimensional Range Searching Revisited I Dynamically maintain a dictionary of numbers(points on a number line), subject to insertions and deletions and queries of the following form: I FindALLInRange(k1, k2): Return an enumeration of all the elements in D with key k, such that k1 ≤ k ≤ k2 To maintain the dictionary we can use any balanced binary search tree such as AVL tree or red-black tree. I O(logn) time for point insertion and removal I O(logn + s) time for answering above query I n is