2.1 Material Covered

We will cover many of the following subjects:

1. Intro.
2. Paradigms.
3. Double connected edge list.
4. Range searching.
5. Segment tree.
6. K. Mulmuley, A Fast Planar Partition Algorithm
7. Las Vegas randomization.
8. Clarkson, fast randomized linear programming
9. Convex Hulls.
   • Graham scan
   • Jordan March
   • Fast Expected Algorithms
10. Voronoi diagrams.
    • Nearest point searching
    • Farthest point searching
    • Transformation to convex hulls
    • Fortune's sweep-line algorithm and implementation
    • Roos's dynamic algorithm and implementation -- you watch the Voronoi diagram changing as the points move.
11. Sweep line intersection.
12. Chazelle & Edelsbruner: optimal line xsect
13. Edelsbrunner & Mucke: Simulation of simplicity.
14. Uniform grids.
15. Franklin: efficient polyhedron intersection.
16. Milenkovic: approximate geometry.
17. Dobkin and Silver: ditto.
18. Hoffman, Hopcroft, and Karasick, ditto.
19. Geometry data structures in the Leda C++ package.
20. Geometry material at U Minn.