MIT 6 854 - Geometry (13 pages)

Previewing pages 1, 2, 3, 4 of 13 page document View the full content.
View Full Document

Geometry



Previewing pages 1, 2, 3, 4 of actual document.

View the full content.
View Full Document
View Full Document

Geometry

69 views


Pages:
13
School:
Massachusetts Institute of Technology
Course:
6 854 - Advanced Algorithms

Unformatted text preview:

1 Geometry Field We have been doing geometry eg linear programming But in computational geometry key di erence in focus low dimension d Lots of algorithms that are great for d small but exponential in d 1 1 Range Trees for Orthogonal Range Queries One key idea in CG reducing dimension Do some work that reduces problem to smaller dimension Since few dimensions work doesn t add up much What points are in this box goal O n space query time O log n plus number of points can t beat log n even for 1d 1d solution binary tree Find leftmost in range Walk tree till rightmost Generalize Solve in each coordinate separately Idea 1 solve each coord intersecting Too expensive maybe large solution in each coord none in intersection Idea we know x query will be an interval so build a y range structure on each distinct subrange of points by x Use binary search to locate right x interval Than solve 1d range search on y Problem n2 distinct intervals So n3 space and time to build Re ne idea Build binary search tree on x coords 1 Each internal node represents an interval containing some points Our query s x interval can be broken into O log n tree intervals We want to reduce dimension on each subinterval range search y coords only amound nodes in that x interval Solution each internal node has a y coord search tree on points in its subtree Size O n log n since each point in O log n internal nodes Query time nd O log n nodes range search in each y tree so O log2 n plus output size more generally O logd n fractional cascading improves to O log n Dynamic maintenance Want to insert delete points Problem to maintain tree balance When insert x coord may want to rebalance Rotations are obious choice but have to rebuild auxiliary structures Linear cost to rotate a tree Remember treaps 2 We showed expect 1 rotation Can show expected size of rotated tree is small Then insert y coord in O log n auxiliary structures So O log2 n update cost Sweep Algorithms Another key idea dimension is low so worth



View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Geometry 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 Geometry 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?