**Instructor**: Jack Snoeyink, Sitterson 333, snoeyink@cs.unc.edu

**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 ^{+}00Nov 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
^{2}) 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.

File translated from T

On 20 Aug 2001, 07:49.