COMP290-72: Computational Geometry and Applications
Department of Computer Science
College of Arts and Sciences
The University of North Carolina at Chapel Hill
COMP 290-72: COMPUTATIONAL GEOMETRY AND APPLICATIONS
Ming C. Lin
- Time and place:TR 2:00pm - 3:15pm, SN 325
- Prerequisites: An advanced undergrad course in algorithms (COMP122 or equivalent)
Computational Geometry (Algorithms and Applications), by de Berg,
van Kreveld, Overmars and Schwarzkofp, Springer-Verlag, 1997 (377 pages;
The goal of the class is to get an appreciation of geometric algorithms, to
understand the various considerations and tradeoffs used in designing
geometric algorithms (e.g. time, space, robustness, and generality)
for various applications. We will cover some basic geometric data
structures and algorithms, their complexity, implementation and applications.
Topics to be covered will vary depending on the interests of students and
possible guest lectures. The preliminary topic list includes:
The lectures will also focus on the applications of geometric algorithms
and data structures in the following areas:
Each topic will be motivated by an interesting example, then studied
in couple lectures about its basic concepts and followed by applications.
Each student will also be expected to give a presentation on one of these
topics or other topics on geometric computing under the instructor's guidance.
Lectures and Approximate Schedule
Here is a list of TENTATIVE lecture topics (subject to
changes). Schedule and information on each topic (e.g. readings, web
pointers) will be added during the semester before each class.
Assignments and Projects
The class grade of each student is determined by
Geometric Algorithms and Softwares Available on the Web:
Here are just some possible locations to find geometric software/libraries
and algorithmic toolkits you may need:
More Pointers to the Web on Geometry:
Here are some good starting points to navigate among the webs of the Web......
Additional Reference Materials
Other reference books:
Other reference papers used in lectures:
* Delaunay Triangulation and Applications *
* Query Image Database *
For more information, contact
Ming C. Lin,
Personal use of this material is permitted. However, permission to
reprint/republish this material for advertising or promotional purposes
or for creating new collective works for resale or redistribution to servers or
lists, or to reuse any copyrighted component of this work in other works
must be obtained from the author.
This material is presented to ensure timely dissemination of scholarly
and technical work. Copyright and all rights therein are retained by authors or
by other copyright holders. All persons copying this information are
expected to adhere to the terms and constraints invoked by each author's
copyright. In most cases, these works may not be reposted without the
explicit permission of the copyright holder.