DOC PREVIEW
Princeton COS 226 - Geometric Algorithms

This preview shows page 1-2-3 out of 9 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Robert Sedgewick and Kevin Wayne • Copyright © 2005 • http://www.Princeton.EDU/~cos226Geometric AlgorithmsReference: Chapters 26-27, Algorithms in C, 2nd Edition, Robert Sedgewick.2Geometric search: OverviewTypes of data. Points, lines, planes, polygons, circles, ...This lecture. Sets of N objects.Geometric problems extend to higher dimensions.! Good algorithms also extend to higher dimensions.! Curse of dimensionality.Basic problems.! Range searching.! Nearest neighbor.! Finding intersections of geometric objects.Robert Sedgewick and Kevin Wayne • Copyright © 2005 • http://www.Princeton.EDU/~cos2267.3 Range Searching41D Range SearchExtension to symbol-table ADT with comparable keys.! Insert key-value pair.! Search for key k.! How many records have keys between k1 and k2?! Iterate over all records with keys between k1 and k2.Application: database queries.Geometric intuition.! Keys are point on a line.! How many points in a given 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 ImplementationsRange search. How many records have keys between k1 and k2?Ordered array. Slow insert, binary search for k1 and k2 to find range.Hash table. No reasonable algorithm (key order lost in hash).BST. In each node x, maintain number of nodes in tree rooted at x.Search for smallest element ! k1 and largest element " k2.log NNlog Ncountinsert rangeordered array N R + log Nhash table 1 NBST log N R + log Nnodes examinedwithin intervalnot touchedN = # recordsR = # records that match62D Orthogonal Range SearchExtension to symbol-table ADT with 2D keys.! Insert a 2D key.! Search for a 2D key.! Range search: find all keys that lie in a 2D range?! Range count: how many keys lie in a 2D range?Applications: networking, circuit design, databases.Geometric interpretation.! Keys are point in the plane.! Find all points in a given h-v rectangle?72D Orhtogonal Range Search: Grid ImplementationGrid implementation. [Sedgewick 3.18]! Divide space into M-by-M grid of squares.! Create linked list for each square.! Use 2D array to directly access relevant square.! Insert: insert (x, y) into corresponding grid square.! Range search: examine only those grid squares that could havepoints in the rectangle.LBRT82D Orthogonal Range Search: Grid Implementation CostsSpace-time tradeoff.! Space: M2 + N.! Time: 1 + N / M2 per grid cell examined on average.Choose grid square size to tune performance.! Too small: wastes space.! Too large: too many points per grid square.! Rule of thumb: ! N by ! N grid.Time costs. [if points are evenly distributed]! Initialize: O(N).! Insert: O(1).! Range: O(1) per point in range.LBRT9ClusteringGrid implementation. Fast, simple solution for well-distributed points.Problem. Clustering is a well-known phenomenon in geometric data.Ex: USA map data.! 80,000 points, 20,000 grid squares.! Half the grid squares are empty.! Half the points have ! 10 others in same grid square.! Ten percent have ! 100 others in same grid square.Need data structure that gracefully adapts to data.10Space Partitioning TreesSpace partitioning tree. Use a tree to represent the recursivehierarchical subdivision of d-dimensional space.BSP tree. Recursively divide space into two regions.Quadtree. Recursively divide plane into four quadrants.Octree. Recursively divide 3D space into eight octants.kD tree. Recursively divide k-dimensional space into two half-spaces.Applications.! Ray tracing.! Flight simulators.! N-body simulation.! Collision detection.! Astronomical databases.! Adaptive mesh generation.! Accelerate rendering in Doom.! Hidden surface removal and shadow casting.GridQuadtreekD treeBSP tree11Quad TreesQuad tree. Recursively partition plane into 4 quadrants.Implementation: 4-way tree.Good clustering performance is a primary reason to choose quad treesover grid methods.abcefghda hd geb cfpublic class QuadTree { Quad quad; Value value; QuadTree NW, NE, SW, SE;}12Curse of DimensionalityRange search / nearest neighbor in k dimensions?Main application. Multi-dimensional databases.3D space. Octrees: recursively divide 3D space into 8 octants.100D space. Centrees: recursively divide into 2100 centrants???Raytracing with octreeshttp://graphics.cs.ucdavis.edu/~gregorsk/graphics/275.html132D Trees2D tree. Recursively partition plane into 2 halfplanes.Implementation: BST, but alternate using x and y coordinates as key.! Search gives rectangle containing point.! Insert further subdivides the plane.even levelsqppointsleft of ppointsright of ppointsbelow qpointsabove qodd levels14kD TreeskD tree. Recursively partition k-dimensional space into 2 halfspaces.Implementation: BST, but cycle through dimensions ala 2D trees.Efficient, simple data structure for processing k-dimensional data.! Adapts well to clustered data.! Adapts well to high dimensional data.! Discovered by an undergrad in an algorithms class!level ! i (mod k)pointswhose ithcoordinateis less than p’spointswhose ithcoordinateis greater than p’sp15SummaryBasis of many geometric algorithms: search in a planar subdivision.grid 2D treeVoronoidiagramintersectinglinesbasis #N h-v lines N points N points #N linesrepresentation2D arrayof N listsN-node BSTN-nodemultilist~N-node BSTcells ~N squares N rectangles N polygons ~N trianglessearch cost 1 log N log N log Nextend to kD? too many cells easycells toocomplicateduse (k-1)DhyperplaneRobert Sedgewick and Kevin Wayne • Copyright © 2005 • http://www.Princeton.EDU/~cos2267.4 Geometric Intersection17Geometric IntersectionProblem. Find all intersecting pairs among set of N geometric objects.Applications. CAD, games, movies, virtual reality.Simple version: 2D, all objects are horizontal or vertical line segments.Brute force. Test all $(N2) pairs of line segments for intersection.Sweep line. Efficient solution extends to 3D and general objects.18Sweep vertical line from left to right.! Event times: x-coordinates of h-v line segments.! Left endpoint of h-segment: insert y coordinate into ST.! Right endpoint of h-segment: remove y coordinate from ST.! v-segment: range search for interval of y endpoints.Orthogonal Segment Intersection: Sweep Line Algorithmrange searchinsert ydelete y19Orthogonal Segment Intersection: Sweep Line AlgorithmSweep line: reduces 2D orthogonal segment intersection problem to1D range


View Full Document

Princeton COS 226 - Geometric Algorithms

Documents in this Course
QUICKSORT

QUICKSORT

14 pages

QUICKSORT

QUICKSORT

55 pages

STRINGS

STRINGS

69 pages

Lecture

Lecture

4 pages

STRINGS

STRINGS

18 pages

Hashing

Hashing

7 pages

MERGESORT

MERGESORT

14 pages

Quicksort

Quicksort

12 pages

Strings

Strings

10 pages

Overview

Overview

15 pages

Hashing

Hashing

13 pages

Mergesort

Mergesort

15 pages

Tries

Tries

13 pages

Final

Final

12 pages

Final

Final

12 pages

Mergesort

Mergesort

13 pages

Final

Final

10 pages

Load more
Download Geometric Algorithms
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Geometric Algorithms and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Geometric Algorithms 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?