Computational Geometry: COMP 290-079                    

Instructor: Jack Snoeyink, Sitterson 333,

Lectures: MW 9:30-10:45, Sitterson 325

Office hours: Tues 2-3pm; Mon 4-5:30 when no colloquium; other times by appointment.

Overview: The field of computational geometry seeks to design and analyze algorithms and data structures for problems that are best stated in a geometric form. It finds natural applications in areas such as graphics, CAD/CAM, robotics, GIS, and molecular biology. Computational geometry also illustrates paradigms of algorithm design and analysis, shows the importance of choosing correct computational primitives, and allows one to prove lower bounds and algorithm optimality.

This course will give an overview of the concepts and methods of computational geometry and its applications using ``Computational Geometry: Algorithms and Applications,'' by de Berg, van Kreveld, Overmars, and Schwarzkopf (2nd ed, Springer Verlag, 2000). Supplementary papers are available on the class website.

Prerequisite: An undergraduate-level analysis of algorithms course (e.g. COMP 122) or permission of the instructor.

Evaluation: Grades will be based on regular homework problem sets and in-class presentations. I may use some in-class tests during the term, but there will be no final exam.

Web site: Go to http://blackboard.unc.edu and search for comp290.079. I am using UNC's Blackboard tools to provide access to handouts, class email, discussion boards, an assignment drop box, and grade records. You will therefore need an ATN account and password (onyen); if you don't already have one, visit http://onyen.unc.edu to create an ATN account, and to set your email forwarding. (Having an ATN account has additional benefits such as modem pools, @unc.edu email address, and mass storage.) Forgotten passwords can be changed in the basement of Wilson if you bring your ID card.

Problem sets: Assigned problems are due on Monday, either in class, under my door, or via the drop box on the web site. (Monday extends until midnight. Once grading has begun, I will generally not consider late assignments.) My intention is that a problem set will typically take two to four pages of writing.

Wednesday presentations: For each week, I have identified a recent or classic paper in computational geometry. Each student is expected to give a 15 or 20 minute conference-style presentation on one of these. I will assign a presenter and a helper to paper. Each presenter must, and helper should, meet with me before the presentation. Other helpers may be recruited.

Collaboration: Collaboration is encouraged, but anything that you hand in must be your own writing/typing. Good scholarship requires that all collaboration must be acknowledged. Thus, if you collaborate on the solution of a problem set, I expect that you name your collaborators at the top of the page. Helpers for a presentation should be acknowledged in the presentation.

Weekly Schedule:

Week of	Topic	Readings (by Mon/Wed)	Weds Paper
Aug 22	Intro: line simplification
Aug 27	Convex hulls	M:ch 1	Cha96
Sept 5	Art Gallery & Triangulation	W:ch 3	Fis78
Sept 10	Line segment intersection	M:2.1	MS01,GGHT97
Sept 17	DCEL and Quadedge	M:2.2-2.5	Ket99
Sept 24	Arrangements & Duality	M:ch 8. W:4.1-4.4	ES95,GO95
Oct 1	Linear programming in low dimensions	M: 4.5-4.8	Wel91
Oct 8	Point location	M:6.1-6.2. W:6.3	ST86
Oct 15	Voronoi diagram	M: 7.1. W:9.1-9.2	ABE98
Oct 22	Delaunay triangulation	M:9.3-9.6	She96a
Oct 29	Random sampling and e-nets	ch 11	CS89
Nov 5	Voronoi & Delaunay applications		FGK+00
Nov 12	Geometric data structures	M:ch 5. W:ch 10.	YZ01
Nov 19	Binary Space partitions	M:ch 12	Tot01
Nov 26	Simplex range searching	M:ch 16	Szé97
Dec 3	Non-uniform mesh generation	M:ch 14	She00

First five problem sets:

1. due Aug 27: dBvKOS page 15: 1.1, 1.4.

2. due Sept 10: For each yes/no question, if the answer is `yes' then describe an algorithm that adds edges (line segments between the given points/endpoints), and if the answer is `no' then give an example.

a.

Can every set of n points in the plane be connected to form a simple polygon? (No edges crossing.)

b.

Can every set of n non-crossing line segments in the plane be connected to form a simple polygon? (The line segments must become edges, and you may add other edges as long as no edges are crossing.)

c.

Can every set of n non-crossing line segments in the plane be completed to a triangulation of the convex hull of their endpoints?

3. due Sept 17: dBvKOS page 42: 2.1. page 61: 3.8, 3.10.

4. due Sept 24: dBvKOS page 42: 2.5, 2.8.

5. due Oct 1: dBvKOS page 180: 8.12. page 92: 4.2, 4.14.

[ABE98] Nina Amenta, Marshall Bern, and David Eppstein. The crust and the b-skeleton: Combinatorial curve reconstruction. Graphical Models and Image Processing, 60:125-135, 1998.

[Cha96] Timothy M. Chan. Optimal output-sensitive convex hull algorithms in two and three dimensions. Discrete Comput. Geom., 16:361-368, 1996.

[CS89] K. L. Clarkson and P. W. Shor. Applications of random sampling in computational geometry, II. Discrete Comput. Geom., 4:387-421, 1989.

[ES95] J. Erickson and R. Seidel. Better lower bounds on detecting affine and spherical degeneracies. Discrete Comput. Geom., 13:41-57, 1995.

[FGK⁺00] A. Fabri, G.-J. Giezeman, L. Kettner, S. Schirra, and S. Schönherr. On the design of CGAL a computational geometry algorithms library. Softw. - Pract. Exp., 30(11):1167-1202, 2000.

[Fis78] S. Fisk. A short proof of Chvátal's watchman theorem. J. Combin. Theory Ser. B, 24:374, 1978.

[GGHT97] M. Goodrich, L. J. Guibas, J. Hershberger, and P. Tanenbaum. Snap rounding line segments efficiently in two and three dimensions. In Proc. 13th Annu. ACM Sympos. Comput. Geom., pages 284-293, 1997.

[GO95] A. Gajentaan and M. H. Overmars. On a class of O(n²) problems in computational geometry. Comput. Geom. Theory Appl., 5:165-185, 1995.

[Ket99] L. Kettner. Using generic programming for designing a data structure for polyhedral surfaces. Comput. Geom. Theory Appl., 13:65-90, 1999.

[Lis94] Dani Lischinski. Incremental Delaunay triangulation. In Paul Heckbert, editor, Graphics Gems IV, pages 47-59. Academic Press, Boston, MA, 1994.

[MS01] Andrea Mantler and Jack Snoeyink. Intersecting red and blue line segments in optimal time and precision. In Discrete and Computational Geometry, number 2098 in Lecture Notes in Computer Science. Springer-Verlag, 2001.

[She96a] J. R. Shewchuk. Triangle: engineering a 2d quality mesh generator and Delaunay triangulator. In First Workshop on Applied Computational Geometry. Association for Computing Machinery, May 1996.

[She00] Jonathan R. Shewchuk. Mesh generation for domains with small angles. In Proc. 16th Annu. ACM Sympos. Comput. Geom., pages 1-10, 2000.

[ST86] N. Sarnak and R. E. Tarjan. Planar point location using persistent search trees. Commun. ACM, 29(7):669-679, July 1986.

[Szé97] L. A. Székely. Crossing numbers and hard Erdos problems in discrete geometry. Combinatorics, Probability and Computing, 6:353-358, 1997.

[Tót01] Csaba D. Tóth. A note on binary plane partitions. In Proc 17th ACM Symp. Computational Geometry, pages 151-156, 2001.

[Wel91] Emo Welzl. Smallest enclosing disks, balls and ellipsoids. Report B 91-09, Fachbereich Mathematik, Freie Universität Berlin, Berlin, Germany, 1991.

[YZ01] Chee Yap and Yunyue Zhu. Yet another look at fractional cascading: B-graphs with application to point location. In Proc 13th CCCG, pages 173-176, Waterloo, Ont, Canada, 2001.