COMPUTATIONAL GEOMETRY

95.508 Fall 1997 Instructor: Anil Maheshwari School of Computer Science Carleton University E-mail: maheshwa@scs.carleton.ca

September 10, 1997

1 Purpose

The purpose of this course is to become familiar with the field of Computational Geometry. During this course we will cover fundamental geometric algorithms, which include convex hulls, Voronoi Diagrams, Trapezoidation, Delaunay triangulation, line segment intersection, range searching, point location, arrangements. Also, we will learn about important techniques such as Plane Sweep, Randomized Incremental Construction, Randomized Divide and Conquer and Linear Programming.

2 References

1. Preparata and Shamos, An introduction to Computational Geometry, Springer-Verlag, 1985.

2. Ketan Mulmuley, Computational Geometry: An introduction using randomization, Prentice Hall, 1994.

3. M. de Berg et al., Computational Geometry: Algorithms and Applications, 4. Mount, Class notes, <http://www.cs.umd.edu>, Spring 1994.

5. Several Research Articles, mainly appearing in following Journals and Conferences: Discrete and Computational Geometry Computational Geometry: Theory and Applications Algorithmica SIAM Jl. Computing ACM CG CCCG SODA ESA FOCS STOC.

6. Feller, An Introduction to probability theory and its applications, Vols 1 & 2, New York, Wiley.

3 Evaluation

There will be four components, with the following weights.

1. Seminar 20%.

2. Report 20%.

3. Assignments 20%.

4. Final 40%.

There will be a Seminar of about 1 hour or more (depends upon the number of students) and I will give out the topic/and references. You need to write a detailed report on your seminar in LaTeX. I will let you know more on this, i.e. its format, depth, etc.

4 Contact Hours

Wednesdays: 2:30 to 5:30pm. I won’t keep a fixed office hour. Its best to send me an e-mail and we can fix-up a meeting (please avoid Tuesdays for office hours).

5 Tentative Time Table

1. Introduction, What is CG, Examples of CG Problems, Model of Computation, Convex Hulls.

2. Arrangement of Lines. Plane Sweep - Trapezoidation and Closest Pair.

3. Skip Lists and Randomized Incremental Construction. Trapezoidation Revisted.

4. Voronoi Diagrams and Delaunay Triangulation.

5. Planar Point Location.

6. Visibility Problems.

7. Motion Planning Problems/Spanners.

8. Range Searching.

9. Linear Programming.

10. Random Sampling.

11. Parallel Algorithms in Computational Geometry.

12. External Memory Algorithms in Computational Geometry.