Computational Geometry

You are here

Home » Studies » Bachelor's degrees » Bachelor Degree in Informatics Engineering » Curriculum » Syllabus » Computational Geometry
Credits
6
Types
Elective
Requirements
This subject has not requirements, but it has got previous capacities
Department
MAT
Web
https://dccg.upc.edu/courses-geoc/
Mail
In this course we present the most frequent geometric algorithms behind many computer science applications in fields such as computer graphics, visualization, shape reconstruction, computer vision, geographical information systems, robotics, etc.

You will learn the appropriated tools for dealing with massive geometric data (algorithms and data structures) and will exploit the geometric properties of the problems posed, to find optimal solutions.

Teachers

Person in charge

  • Rodrigo Ignacio Silveira ( )

Weekly hours

Theory
2
Problems
1.1
Laboratory
0.9
Guided learning
0
Autonomous learning
6

Competences

Transversal Competences

Third language

  • G3 [Avaluable] - To know the English language in a correct oral and written level, and accordingly to the needs of the graduates in Informatics Engineering. Capacity to work in a multidisciplinary group and in a multi-language environment and to communicate, orally and in a written way, knowledge, procedures, results and ideas related to the technical informatics engineer profession.
    • G3.2 - To study using resources written in English. To write a report or a technical document in English. To participate in a technical meeting in English.

Objectives

  1. Learn the several kinds of problems in Computational Geometry, as well as their applications.
    Related competences:
  2. Learn the capacity of combining geometric tools with the appropriated data structures and algorithmic paradigms.
    Related competences:
  3. See in action several algorithmic paradigms and data structures useful in geometric problems.
    Related competences:
  4. Apply geometric results to real problems.
    Related competences:
  5. Ability to solve basic problems that appear in computational geometry.
    Related competences:
  6. Ability to implement the solutions proposed in the class, as well as those that can be found in the basic references of the course.
    Related competences:
  7. Ability to recognize the geometric problems behind the applications, and to propose adequate algorithmic tools to solve them.
    Related competences:
  8. Practice and improve the capability of working in a English speaking professional surrounding
    Related competences: G3.1, G3.2, G3.3,

Contents

  1. Introduction to Computational Geometry
    The problems studied in Computational Geometry. Applications. Terminology. Basic Tools.
  2. A basic tool
    Oriented area. Left/right. Intersection of two lines. Intersection of two segments. Oriented turn.
  3. Sweep line algorithms
    Bentley-Ottmann algorithm
  4. Basic geometric problems on polygons
    Line/polygon intersection, point location in a polygon, supporting lines to a polygon from a point, etc.
  5. Convex hull
    Algorithms for the construction od the convex hull of 2D point sets.
  6. Duality. Intersection of halfplanes.
    Geometric duality. The parabola duality. Intersection of halfplanes and convex hulls.
  7. Polygon triangulation
    Triangulation of monotone polygons, decomposition of a polygon into monotone polygons.
  8. Proximity
    Voronoi diagrams and their applications
  9. Triangulations of point sets
    Delaunay triangulation
  10. Line and plane arrangements
    Description, properties, and construction. Levels. Relationship with Voronoi diagrams.
  11. Point location in planar subdivisions
    Variety of strategies. Preprocessing complexity vs query efficiency.
  12. Shape reconstruction
    Alpha-shapes, crust, anti-crust and beta-skeletons.
  13. Students presentations of further subjects
    Extensions of the course contents.

Activities

Activity Evaluation act



Solving problems

Only some of the sessions will be run by the instructor. The remaining ones will consist of presentation and discussion of the solutions of problems, done by the students.
Objectives: 5 7 8
Contents:
Theory
0h
Problems
16.5h
Laboratory
0h
Guided learning
0h
Autonomous learning
25h

Lab

Implementing geometric algorithms
Objectives: 4 6 8
Contents:
Theory
0h
Problems
0h
Laboratory
13.5h
Guided learning
0h
Autonomous learning
45h


Teaching methodology

Theory classes will set out the contents of the course, oriented to the resolution of examples and applications.

Exercise classes will be centered in the resolution of problems by the instructors as well as by the students. Students will be assigned problems and will have enough time to think about them in advance, so that they will be able to propose their solutions during the class. The problems will be mainly algorithmic.

The purpose of the lab classes is to implement the solutions discussed in the theory and exercices classes, the effective solution of problems being one of the goals of the course. The problems to be solved in the lab classes will start being of elementary complexity, and will end with the resolution of a problem, preferably applied and real.

Evaluation methodology

The evaluation will be based on the work done by the student along the course. The four components to be considered will be:

Problems presented in class (P)
Final presentation of the chosen subject (T)
Lab exercises (L)
Exam (E)

The final course grade will be calculated as follows:

Final grade = 0.2*P + 0.2*T + 0.35*L + 0.25*E

Bibliography

Basic:

Complementary:

Web links

Previous capacities

- Programming
- Basic knowledge of data structures
- Basic knowledge of algorithmic techniques

This course is recommended for students with knowledge and interest in computation. Students with other specializations of without any specialization are kindly asked to take this into account before enrolling.

Students need to do their presentations in English. This course is not recommend for students with very rudimentary English skills.