DOC PREVIEW
Princeton COS 226 - Geometric Search

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

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 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 12 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 12 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 12 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Algorithms in Java, 4th Edition·Robert Sedgewick and Kevin Wayne·Copyright © 2009·January 26, 2010 8:49:21 AM6.3 Geometric Search‣range search‣space partitioning trees‣intersection searchGeometric objects. Points, lines, intervals, circles, rectangles, polygons, ...This lecture. Intersection among N objects.Example problems.•1D range search.•2D range search.•Find all intersections among h-v line segments.•Find all intersections among h-v rectangles.2Overview‣range search‣space partitioning trees‣intersection search341d range searchExtension of ordered symbol table.•Insert key-value pair.•Search for key k.•Rank: how many keys less than k?•Range search: find all keys between k1 and k2.Application. Database queries.Geometric interpretation.•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: implementationsOrdered array. Slow insert, binary search for lo and hi to find range.Hash table. No reasonable algorithm (key order lost in hash).BST. All operations fast.N = # keysR = # keys that matchdata structureinsertrankrange countrange searchordered arrayNlog Nlog NR + log Nhash table1NNNBSTlog Nlog Nlog NR + log NRange 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).Worst-case running time. R + log N (assuming BST is balanced).61d 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 BST72d orthogonal range searchExtension of ordered symbol-table to 2d keys.•Insert a 2d key.•Search for a 2d key.•Range search: find all keys that lie in a 2d range?Applications. Networking, circuit design, databases.Geometric interpretation.•Keys are point in the plane.•How many points in a given h-v rectangle.rectangle is axis-aligned82d 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.LBRT92d orthogonal range search: grid implementation costsSpace-time tradeoff.•Space: M2 + N.•Time: 1 + N / M2 per square examined, on average.Choose grid square size to tune performance.•Too small: wastes space.•Too large: too many points per square.•Rule of thumb: !N-by-!N grid.Running time. [if points are evenly distributed]•Initialize: O(N).•Insert: O(1).•Range: O(1) per point in range.M ~ !N LBRTGrid implementation. Fast, simple solution for well-distributed points.Problem. Clustering a well-known phenomenon in geometric data.Lists are too long, even though average length is short.Need data structure that gracefully adapts to data.10ClusteringGrid implementation. Fast, simple solution for well-distributed points.Problem. Clustering a well-known phenomenon in geometric data.Ex. USA map data.11Clusteringhalf the squares are emptyhalf the points arein 10% of the squares13,000 points, 1000 grid squares‣range search‣space partitioning trees‣intersection search12Use a tree to represent a recursive subdivision of 2D space.Quadtree. Recursively divide space into four quadrants.2d tree. Recursively divide space into two halfplanes. BSP tree. Recursively divide space into two regions.13Space-partitioning treesGrid2D treeQuadtreeBSP tree14Space-partitioning trees: applicationsApplications.•Ray tracing.•2d range search.•Flight simulators.•N-body simulation.•Collision detection.•Astronomical databases. •Nearest neighbor search. •Adaptive mesh generation.•Accelerate rendering in Doom.•Hidden surface removal and shadow casting. Grid2D treeQuadtreeBSP treeIdea. Recursively divide space into 4 quadrants. Implementation. 4-way tree (actually a trie).Benefit. Good performance in the presence of clustering.Drawback. Arbitrary depth!15Quadtreeabcefghdpublic class QuadTree{ private Quad quad; private Value val; private QuadTree NW, NE, SW, SE;}(01.., 00..)(0..., 1...)ab cd e f ghSENWSWNE16Quadtree: larger examplehttp://en.wikipedia.org/wiki/Image:Point_quadtree.svg17Quadtree: 2d range searchRange search. Find all keys in a given 2D range.•Recursively find all keys in NE quad (if any could fall in range).•Recursively find all keys in NW quad (if any could fall in range).•Recursively find all keys in SE quad (if any could fall in range).•Recursively find all keys in SW quad (if any could fall in range).Typical running time. R + log N.abcefghdab cdefgh18N-body simulationGoal. Simulate the motion of N particles, mutually affected by gravity. Brute force. For each pair of particles, compute force.F =Gm1m2r219Subquadratic N-body simulationKey idea. Suppose particle is far, far away from cluster of particles.•Treat cluster of particles as a single aggregate particle.•Compute force between particle and center of mass of aggregate particle.20Barnes-Hut algorithm for N-body simulation.Barnes-Hut.•Build quadtree with N particles as external nodes.•Store center-of-mass of subtree in each internal node.•To compute total force acting on a particle, traverse tree, but stop as soon as distance from particle to quad is sufficiently large.21Curse 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 100d space into 2100 centrants???Raytracing with octreeshttp://graphics.cs.ucdavis.edu/~gregorsk/graphics/275.htmlRecursively partition plane into two halfplanes.222d tree1234678910512871093465Implementation. BST, but alternate using x- and y-coordinates as key.•Search gives rectangle containing point.•Insert further subdivides the plane.232d treeeven levelsppointsleft of ppointsright of ppqpointsbelow qpointsabove qodd levelsq128710934651234678910512871093465Range search. Find all points in a query axis-aligned rectangle.•Check if point in node lies in given rectangle.•Recursively search left/top


View Full Document

Princeton COS 226 - Geometric Search

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 Search
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 Search 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 Search 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?