Home Page for CMSC 754 (Computational Geometry)

Office Hours: Tuesday 2:00--3:00, and Friday 11:00--12:00. If you cannot make these hours, please make an appointment to see me at a different time.

OFFICE HOURS THIS WEEK:

Wed: 10--11

Thu: 3--5

Fri: 11--12 and 3:30 --4:30

Teaching Assistant: Michael Murphy Office: AVW 3228. Office phone: 405--2717. E-mail: murphy@cs.umd.edu.

Office Hours: Tuesday 10:00--11:30, and Thursday 4:30--5:30. If you cannot make these hours, please make an appointment to see Michael at a different time.

I hope to maintain this page and update it every week this semester. I will place all homeworks as well as solutions to homeworks here. If you have any trouble accessing them, please let me know.

Class Time: Monday and Wednesday 11.00--12.15, Room: CLB 0109.

Course Overview: Introduction to algorithms and data structures for computational problems in discrete geometry (for points, lines, and polygons) primarily in 2 and 3 dimensions. Topics include triangulations and planar subdivisions, geometric search and intersection, convex hulls, Voronoi diagrams, Delaunay triangulations, line arrangements, visibility, and motion planning.

Text: We will use more than one book. The first one (O'Rourke) will be the main text for the course. We will also use the second one from time to time (Preparata and Shamos). The other two books are mostly for your entertainment.

• Computational Geometry in C, Joseph O'Rourke, Cambridge University Press, 1994.
• Computational Geometry: An Introduction, F. P. Preparata and M. I. Shamos, Springer-Verlag, 1985.
• Algorithms in Combinatorial Geometry, H. Edelsbrunner Springer-Verlag, 1987.
• Computational Geometry: An Introduction through Randomized Algorithms, by Ketan Mulmuley, Prentice Hall, 1994.

Suggested Syllabus: This is only a rough outline -- we may do things in a different order.

• Preliminaries: Mathematical and geometric review. Review of algorithm analysis techniques, mathematical models of computation, randomized algorithms and probabilistic analysis techniques, representation of basic geometric objects, convexity, polytopes.
• Spatial decompositions: Planar subdivisions, triangulations, trapezoidal decompositions.
• Geometric searching: Point location, interval and segment trees, data structures for nearest neighbors, range searching, multi-dimensional search trees.
• Convex hulls: Geometric duality, deterministic and randomized algorithms for two and higher dimensional convex hulls, linear programming.
• Proximity problems: Closest pair, Voronoi diagrams and Delaunay triangulations, relationship to convex hulls, and applications.
• Arrangements: Line, hyperplane, and line segment arrangements, incremental construction techniques, complexity of lower envelopes, duality.
• Visibility and motion planning: Visibility graphs, shortest paths, ray shooting.

Grading: Final grades will be based on homework assignments, the midterm exam, and the final exam. The relative weights of these will be 30% for the homework total, 30% for the midterm, and 40% for the final exam.

REMINDER: Midterm on March 11. Skinner 0200 11:00-12:15.

REMINDER: Final on May 11 (sat). AVW 1112/1152 9:30-12:00.

Class Handout

Handout on Ultimate Convex Hull Alg

Handout on Randomized Incremental Construction of Convex Hull's

Handout on Applications of Geometric Duality

Handout on Davenport-Schinzel Sequences

Handout on Visibility Graphs

Lectures

Homeworks:

• Homework 1 Due on 2/14/96 Solution 1.
• Homework 2 Due on 2/28/96 Solution 2. Hints: For problem (2) sort all lines by slope, and prove that we only need to generate the intersection points of two lines that are adjacent in the circular sorted order (by slope). For problem (3) maintain two shortest paths (taut string paths) as you walk down the series of triangles.
• Homework 3 Due on 3/25/96. Instructions.
• Homework 4 Due on 4/3/96. Solution 4.
• Homework 5 Due on 4/24/96. Solution 5.
• Homework 6 Due on 5/6/96.

Other Interesting Stuff:

Computational Geometry Talk at Johns Hopkins on Fri 23rd Feb.

Computational Geometry Day at NYU, New York on Fri 26th Apr.

Computational Geometry Job

Application Challenges to Computational Geometry