# MIT 6 854 - Geometry (13 pages)

Previewing pages 1, 2, 3, 4 of 13 page document
View Full Document

## Geometry

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

View Full Document
View Full Document

## Geometry

69 views

Pages:
13
School:
Massachusetts Institute of Technology
Course:
• 15 pages

• 5 pages

• 19 pages

• 4 pages

• 5 pages

• 6 pages

• 3 pages

• 2 pages

• 9 pages

• 16 pages

• 5 pages

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

Unlocking...