PhD in Computing

42022 - Computational Geometry (GCOM)


  • Type: Elective
  • Semester: S3
  • ECTS: 5
  • Teaching points: 12
  • Offer: Annual
  • Responsible Unit:
  • Responsible: J.Antoni Sellarès
  • Language: English
  • Requirements: The student will be presented with the intrinsic problems of unstructured geometric models (or "thinly-structured" models), typically triangle soups and point-based models, with an emphasis on large models. Upon completion, the student will know --both from a theoretical and a practical standpoint-- the main techniques used in acquiring, manipulating and visualizing these models, and some of their applications.


GOALS
The field of Computational Geometry seeks to design and analyze algorithms and data structures to efficiently solve problems on geometric data. Computational geometry allows one to prove problem lower bounds and algorithm optimality.
Upon completion of the course students should be able to: master key foundations of Computational Geometry, become familiar with Computational Geometry current techniques and tools, develop a methodical approach to solving geometric computational problems.


CONTENTS
1. Plane-Sweep Algorithms: intersection of segments and polygons.
2. Convex hulls in two and three dimensions.
3. Halfplane and halfsapce intersections.
4. Linear programming in two and three dimensions. Optimization problems.
5. Proximity. Voronoi diagrams in two and three dimensions.
6. Triangulation of a polygon. Triangulation of a set of points. Delaunay triangulation.
7. Tetrahedralization of a polyhedron. Tetrahedralization of a set of points. Delaunay tetrahedralization.
8. Mesh generation in two and three dimensions.
9. Visibility problems in two and three dimensions.
10. Geometric range query structures.


DOCENT METHODOLOGY
Diffferent sorts of activities will take place along the course: lecture hearing, reading and studying materials (articles, book chapters, etc.), solving problems, actively participating in group discussions.
A project on one topic related to the module’s subjects is compulsory. The topic will be agreed between each student and the teacher.
At theoretical and problem solving lessons, the fundamental concepts of the subject’s programme will be developed, combining the teacher’s exposition with group discussion and problem solving. Before each lesson, students should have read the materials that they have been provided with, and they must put an effort to solve the proposed problems.
Student work is divided this way:
  • 35% of work derivates from theoretical classes
  • 35% of work comes from time dedicated to problem solving
  • 30 % of work is dedicated to working on a project.

EVALUATION METHODOLOGY
An average will be calculated taking into account the different activities done along the course: attendance to lessons, materials reading, solving problems, active participation in class and a project.

BIBLIOGRAPHY
M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf. Computational Geometry,
Algorithms and Applications. Springer, 2000.

J. O'Rourke. Computational Geometry in C. Cambridge Univ. Press, 1998.
H. Edelsbrunner. Geometry and Topology for Mesh Generation. Cambridge Univ.
Press, England, 2001.

RESOURCES
Students will find the materials made by the teacher at the course website.

  • What are Geometry Algorithms ? http://geometryalgorithms.com/overview.htm
  • Computational Geometry Course, by D. Mount

  • Course 2002: http://www.cs.umd.edu/~mount/754/
  • Course 2005: http://www.cs.umd.edu/class/fall2005/cmsc754/lectures.shtml

WEBSITE