Algorithms, 4th Edition·Robert Sedgewick and Kevin Wayne·Copyright © 2002–2012·March 17, 2012 11:51:02 AMAlgorithmsFOUR T H EDIT IONR O B E R T S EDG EWICK K EVIN W A Y N EGEOMETRIC APPLICATIONS OF BSTS‣1d range search‣line segment intersection‣kd trees‣interval search trees‣rectangle intersectionThis lecture. Intersections among geometric objects.Applications. CAD, games, movies, virtual reality, VLSI design, databases, .…Efficient solutions. Binary search trees (and extensions).2Overview2d orthogonal range search orthogonal rectangle intersection‣1d range search‣line segment intersection‣kd trees‣interval search trees‣rectangle intersection341d range searchExtension of ordered symbol table.•Insert key-value pair.•Search for key k.•Delete key k.•Range search: find all keys between k1 and k2.•Range count: number of keys between k1 and k2.Application. Database queries.Geometric interpretation.•Keys are point on a line.•Find/count points in a given 1d interval.insert B Binsert D B Dinsert A A B Dinsert I A B D Iinsert H A B D H Iinsert F A B D F H Iinsert P A B D F H I Pcount G to K 2search G to K H I51d range search: implementationsUnordered array. Fast insert, slow range search.Ordered array. Slow insert, binary search for k1 and k2 to do range search.Parameters.•N = number of keys.•R = number of keys that match.data structureinsertrange countrange searchunordered array1NNordered arrayNlog NR + log Ngoallog Nlog NR + log Nrunning time is output sensitive(number of matching keys can be N)order of growth of running time for 1d range search61d range count: BST implementation1d range count. How many keys between lo and hi ?Proposition. Running time is proportional to log N (assuming BST is balanced).Pf. Nodes examined = search path to lo + search path to hi.public int size(Key lo, Key hi) { if (contains(hi)) return rank(hi) - rank(lo) + 1; else return rank(hi) - rank(lo); } number of keys < hiAA C E H M R S XCEHMRSXAA C E H M R S XCEHMRSX2658811111132222node count NTwo BSTs that representthe same set of keys1d range search. Find all keys between lo and hi.•Recursively find all keys in left subtree (if any could fall in range).•Check key in current node.•Recursively find all keys in right subtree (if any could fall in range).Proposition. Running time is proportional to R + log N (assuming BST is balanced).Pf. Nodes examined = search path to lo + search path to hi + matching keys.71d range search: BST implementationblack keys arein the rangered keys are used in comparesbut are not in the rangeACEHLMPRSXsearching in the range [F..T]Range search in a BST‣1d range search‣line segment intersection‣kd trees‣interval search trees‣rectangle intersection89Orthogonal line segment intersection searchGiven N horizontal and vertical line segments, find all intersections.Nondegeneracy assumption. All x- and y-coordinates are distinct.Quadratic algorithm. Check all pairs of line segments for intersection.Sweep vertical line from left to right.•x-coordinates define events.•h-segment (left endpoint): insert y-coordinate into BST.10Orthogonal line segment intersection search: sweep-line algorithmy-coordinates012301324Sweep vertical line from left to right.•x-coordinates define events.•h-segment (left endpoint): insert y-coordinate into BST.•h-segment (right endpoint): remove y-coordinate from BST.11Orthogonal line segment intersection search: sweep-line algorithm0123y-coordinates0134Sweep vertical line from left to right.•x-coordinates define events.•h-segment (left endpoint): insert y-coordinate into BST.•h-segment (right endpoint): remove y-coordinate from BST.•v-segment: range search for interval of y-endpoints.12Orthogonal line segment intersection search: sweep-line algorithm1d rangesearch40123y-coordinates01313Orthogonal line segment intersection search: sweep-line algorithm analysisProposition. The sweep-line algorithm takes time proportional to N log N + Rto find all R intersections among N orthogonal line segments.Pf.•Put x-coordinates on a PQ (or sort).•Insert y-coordinates into BST.•Delete y-coordinates from BST.•Range searches in BST.Bottom line. Sweep line reduces 2d orthogonal line segment intersection search to 1d range search.N log NN log NN log NN log N + R14General line segment intersection searchSweep-line algorithm.•Maintain segments that intersect sweep line ordered by y-coordinate.•Intersections can only occur between adjacent segments.•Delete/add line segment ⇒ one/two new pairs of adjacent segments.•Intersection ⇒ swap adjacent segments.order of segments that intersect sweep lineACBABC ACBDACD CADAABinsert segmentdelete segmentintersectionACBDCAA15General line segment intersection search: implementationSweep-line algorithm.•Maintain PQ of important x-coordinates: endpoints and intersections.•Maintain set of segments intersecting sweep line, in BST sorted by y-coordinates.Proposition. The sweep-line algorithm takes time proportional toR log N + N log N to find all R intersections among N orthogonal line segments.Implementation issues.•Degeneracy.•Floating-point precision.•Must use PQ, not presort (intersection events are unknown ahead of time).to support "next largest" and"next smallest" queries‣1d range search‣line segment intersection‣kd trees‣interval search trees‣rectangle intersection16172-d orthogonal range searchExtension of ordered symbol-table to 2d keys.•Insert a 2d key.•Delete a 2d key.•Search for a 2d key.•Range search: find all keys that lie in a 2d range.•Range count: number of keys that lie in a 2d range.Geometric interpretation.•Keys are point in the plane.•Find/count points in a given h-v rectangle.Applications. Networking, circuit design, databases.rectangle is axis-aligned182d orthogonal range search: grid implementationGrid implementation.•Divide space into M-by-M grid of squares.•Create list of points contained in each square.•Use 2d array to directly index relevant square. •Insert: add (x, y) to list for corresponding square.•Range search: examine only those squares that intersect 2d range query.LBRT192d orthogonal range search: grid implementation costsSpace-time tradeoff.•Space: M 2 + N.•Time: 1 + N / M 2 per square examined, on average.Choose grid square size to tune performance.•Too small: wastes space.•Too large: too many points
View Full Document
Unlocking...