6.838 Lecture 13: Douglas De Couto, Josh Napoli
March 18, 1998

Proximity and Ordering I: Indexing Objects

•  (Warmup) Indexing in one dimension (binary search trees):
1. Points
2. Segments
• Binary indexing in two dimensions:
1. Application: searching maps
2. Multiple 1D trees
• kD trees
1. Nice features
2. How to build them
3. How to use them
4. ``Not just for points any more!''
5. Application: 2D nearest neighbour & N-body problems
6. Application: colour reduction with 3D kD trees
7. Fixing them up dynamically
• QuadTrees
1. Presentation by Cyril.
• BSP trees
1. Nice Features
2. Building and using
3. Application: stabbing rays/mouse picking
4. Application: painter's algorithm and frustum culling
• Hierarchical triangulation (Dobkin/Kirpatrick hierarchy)
1. Built-in nearest neighbours
2. How to build and use in 2D
3. Application: convex polyhedron intersection in 3D