Spring, 2004
Robert Hochberg
1. Art Gallery theorems
2. Convex hulls
3. Voronoi diagrams and Delaunay triangulations
4. Randomized algorithms and backward analysis
5. Planar point location and the Kirkpatrick hierarchy
6. Shortest path in the plane around polygonal obstacles
7. Project Presentations
| 4/15 | 4/20 |
4/22 |
| Evin
- Surround # |
Rob
- Duality Fred - Motzkin Tom - Polygon delooping |
Brooke
- Origami Brian - 4 colors Constantine - Holes |
There will be 4 assignments worth 100 points each. You will have the option on each assignment to follow the computational track or the theoretical track. In the former, you implement some algorithm in your favorite programming language, and in the latter you will solve some problems and prove some theorems. Grad students in this class will have the additional assignment of reading a paper and delivering a presentation at some point during the semester. I will select the papers.
Great animation of Fortune's Algorithm for computing Voronoi Diagrams.
Some screen shots of Fortune's Algorithm in action
Website of our textbook's author
The Open Problem Project at Smith College
My other web page
A note on image maps
A great geometry site
A Unit-Distance Graph is a graph which can be drawn in the plane so that every edge has length exactly 1. (Vertices are points in the plane...) Three unit-distance graphs are shown here.
It has been an open problem for about 50 years to decide if all unit-distance graphs can be 4-colored. That is, is it possible to assign a color to each vertex so that vertices with an edge between them are given different colors. It is known that 7 colors suffice, but it is not known for 4, 5 or 6 colors.
Given n lines in the plane which do not all pass through a single common point, prove that there must be some line with at least (n - 1)/2 points of intersection. Please! Nobody can do this!
The arrangement shown at the top of this page is an extreme example: 11 lines, and no more than 5 points of intersection on any line. Since line arrangements are duals of point arrangements, it is equivalent to consider the point version of this open problem: Given n points in the plane which do not all lie on a single line, show that there must be some point which has at least (n - 1)/2 induced lines passing through it (induced by passing through other points in the set).
