1. W1-17-96 * Handouts 1 and 2.
* Course intro.
* Brief history of geometry: Euclid, Descartes, Euler,
Peano.
* Isosceles triangle paradox.
2. M1-22-96 * Lee & Preparata thru locus method.
3. W1-24-96 * Lee & Preparata ctd thru divide and conquer.
* Sweep line edge intersection in detail, with heaps and
tree rotation.
* Recurrence relations.
4. M1-29-96 * Lee & Preparata ctd into intersections.
* Intro to Megiddo & Dyer linear time LP.
5. W1-31-96 * Lee & Preparata ctd into range search, with
excursions:
* Intersecting convex polygons,
* Intersecting general polygons,
* Testing point inclusion in a polygon by the Jordan
curve method,
* The special cases of two coincident vertices or a
vertex on the other polygon's edge,
* Solving recurrence relations such as Fibonacci using
powers.
* 1-D range search with segment tree
* 2-D range search: N5 and then N3 methods.
* Handout 3.
6. M2-5-96 * Lee & Preparata ctd thru range search, with
excursions:
* 1-D data structures: binary search trees, digital
search trees (tries),
* 2-D data structures: quadtrees, k-d trees.
* Refs to Preparata and Shamos
* Handout 3.
7. W2-7-96 * Lee & Preparata ctd thru into point location.
* Planar graph data structures, including DCEL.
* Point location methods: slab, chain.
* Refs to Preparata and Shamos.
8. M2-12-96 * Lee & Preparata ctd into Voronoi diagrams.
* Refs to Preparata and Shamos.
9. W2-14-96 * Number of polytopes of the generalized tetrahedron,
cube, octahedron types.
* Voronoi properties and applications.
10. "M"2-21-96 * Attempt to demo xvoronoi.
* Demo U. Minn. interactive geometry.
* Voronoi diagram construction by
o divide and conquer, plus implementation problems
o reduction to convex hull in one dimension higher
11. M2-26-96 * Show xvoronoi slides.
* GPS.
* Using reduction to convex hull to do K-nearest
neighbor Vord.
12. W2-28-96 * Vords ctd.
* Vords for interpolation of scattered data (Gold).
* Handout 4.
13. M3- 4-96 * Handouts 6 to 8.
* Vords on other metrics.
* Randomized search tree.
14. W3- 6-96 * Handouts 9 to 11.
* Data structures for storing all US streets on a CD.
* Fortune alg ctd.
* Triangulations in 2D and 3D: in 3D the number is
variable, and Steiner points may be necessary, and
knowing whether is hard.
* Intro to Guibas and Stolfi.
* Vord by edge flipping.
15. M3-18-96 * More points from Fortune's paper
* My uniform grid paper
16. W3-20-96 * Handouts 10, 13, 14, 15.
* discuss my Steensel paper.
* discuss my hidden surface papers.
15. M3-25-96 * Geometry algorithms animation videos
* Decomposing a polygon into a boolean expression on the
halfplanes defined by its edges, with each edge used
only once.
* That can't be done in 3D.
16. W3-27-96 * Faculty job market.
* Guibas & Stolfi paper: topology, quadedges, etc.
* Handouts 16 to 19.
17. M4- 1-96 * More geometry videos.
* Break early for Vollmer Fries talk by Moog.
18. W4- 3-96 * Wesley papers on fleshing out wireframes and
projections.
19. M4- 8-96 * Handouts 20 and 21.
* Simulation of Simplicity.
* Guest lecture :-) Mandlebrot on fractals.
No Real Programmer works 9 to 5 (unless it's the ones at night).
April 11, 1996
, 
: 
/dept/ecse/compeom/ho22.tex