View Full Document

Geometric Algorithms



View the full content.
View Full Document
View Full Document

2 views

Unformatted text preview:

Geometric Algorithms range search quad and kd trees intersection search VLSI rules check References Algorithms in C 2nd edition Chapters 26 27 http www cs princeton edu introalgsds 73range http www cs princeton edu introalgsds 74intersection 1 Overview Types 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 2 range search quad and kd trees intersection search VLSI rules check 3 1D Range Search Extension 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 k 1 and k2 Application database queries Geometric intuition Keys are point on a line How many points in a given interval insert B B insert D BD insert A ABD insert I ABDI insert H ABDHI insert F ABDFHI insert P ABDFHIP count G to K 2 search G to K H I 4 1D Range search implementations Range 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 insert count range ordered array N log N R log N hash table 1 N N BST log N log N R log N N records R records that match nodes examined within interval not touched 5 2D Orthogonal Range Search Extension 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 6 2D Orthogonal range Search Grid implementation Grid implementation Sedgewick 3 18 Divide



Access the best Study Guides, Lecture Notes and Practice Exams

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