Syllabus - CS 164/266 - Computational Geometry
Michael T. Goodrich
http://www.ics.uci.edu/~goodrich/teach/geom/
- Course description.
Algorithms and data structures for geometric computation and graphics
programming. Fundamental problems of computational geometry such as
convex hulls, Voronoi diagrams, Delaunay triangulations, polygon
partitioning, arrangements, geometric searching, hidden surface
elimination, motion planning.
- Coursework. Coursework will consist of homeworks,
quizzes,
a midterm, and a final exam. The overall grade
will be determined 30% from the quizzes,
20% from homework, 25% from the midterm, and
25% from the final.
Group work on homeworks is permitted, but each
student must list his or her collaborators in writing for each problem.
If a student turns in a solution without listing
the others who helped produce this solution,
this act will be considered cheating (for it is plagarism).
Late homework assignments will not be accepted,
but for the overall total homework score,
the lowest homework score will be dropped.
- Quiz/Exam policy.
Quiz and exam performance must be 100% individual effort; no collaboration
is allowed on exams. Any collaboration or copying on quizzes or exams
will be considered cheating.
In addition to the procedures of the
ICS
Cheating Policy, students caught cheating on an exam or quiz will be given a
failing grade.
- Laptop policy.
Laptops may be brought to class, but should remain closed during lectures
and exams, unless necessary to accommodate a disability.
Here's one reason why.
Here is another.
- Textbook. de Berg, Cheong, van Kreveld, and Overmars,
Computational Geometry: Algorithms and Applications, Springer,
2008, 3rd edition.
Tentative Schedule
- Week 1:
-
Introduction.
Convex hulls.
- Reading: Chapter 1.
- Week 2:
-
Line segment intersections. Doubly-connected edge list. Boolean
operations.
- Reading: Chapter 2.
-
Week 3:
-
Polygon triangulation.
- Reading: Chapter 3.
-
Week 4:
-
Linear programming.
- Reading: Chapter 4.
-
Week 5:
-
Range searching.
- Reading: Chapter 5.
-
Week 6:
-
Point location.
- Reading: Chapter 6.
-
Week 7:
-
Voronoi diagrams.
- Reading: Chapter 7.
-
Week 8:
-
Arrangements and Duality.
- Reading: Chapter 8.
-
Week 9:
-
Delaunay triangulations.
3-D convex hulls.
- Reading: Chapters 9 and 11.
-
Week 10:
-
Geometric data structures.
- Reading: Chapter 10.
Copyright © 2023
Michael T. Goodrich, as to all lectures.
Students are prohibited from selling
(or being paid for taking) notes during this course to or by any
person or commercial firm without the express written permission of the
professor teaching this course or from Disabled Services Center (DSC).