Computational Geometry

Credits
6
Types
  • GRAU: Elective
  • GCED: Elective
Requirements
This subject has not requirements , but it has got previous capacities
Department
MAT
Web
https://dccg.upc.edu/courses-geoc/
Mail
rodrigo.silveira@upc.edu
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

Others

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.