6.838 Lecture 13

 (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

Read full article from 6.838 Lecture 13