Computational Geometry

Computational Geometry – GEI

Bachelor Degree in Informatics Engineering (GEI)
Departament de Matemàtiques
Facultat d’Informàtica de Barcelona
Universitat Politècnica de Catalunya

Instructors

Goal of the course

The Computational Geometry course has an algorithmic and applied flavor. Its contents are oriented to dealing with massive geometric data, and the lab exercises are intended to make students familiar with real problems coming from computer graphics, geographic information systems, robotics, land planning, etc. The goal of the course is to present the most frequent geometric algorithms that one can find behind all sorts of software having a geometric component. We want the student to learn how to optimally construct optimal solutions to this kind of problems by combining a) the geometric properties of the problem, b) an efficient algorithmic paradigm, and c) the most convenient data structure.

What is Computational Geometry?

Just for starting, here are some links that can help you getting an idea of what Computational Geometry is.

For those who want to see it in action, many applets (somewhat old, but still interesting) made by the Computational Geometry students of the Facultad de Informática de Madrid.

For those who want to know it all, here are some web pages with more information: Computational Geometry pages (Jeff Erickson), Geometry in Action (David Eppstein), Computational Geometry links (Godfried Toussaint).

Material for the course

The general information related to a specific semester of  the course (calendar, schedule, class rooms, evaluation, etc.) can be found at the FIB web page. Announcements along the semester will be done at the FIB corner (Racó). In this web page (which is always under construction) you will find most of the material for the course.

In this space, as the course advances, we will post presentations and links related to the several subjects that we will work through in class. If you wish to download the latest updated version of the slides, do it as each class approaches (ideally, after the class), do not do it too early.

  1. Presentation of the course
  2. Background
  3. Basic tools
  4. A classical sweep-line algorithm: Intersecting line-segments: Bentley-Ottmann’s algorithm
  5. Basic problems on polygons
  6. Convex hull of a set of points
  7. Duality. Intersection of half-planes
  8. Triangulating polygons
  9. Proximity
  10. Triangulating point sets
  11. Arrangements of lines
  12. Point location in planar decompositions
  13. Extra topics
  14. Students’ presentations

Problems

Each student must solve and turn in a number (to be discussed and agreed in class) of exercises from the problems list. Once solved and turned-in, you will have to present the solution of your problem in class. Make sure that you do so in a clear and succint way (consider preparing a short presentation).

To know which problems are available and choose your problems, follow the link that will be provided through the FIB corner (Racó).

Lab exercises

Each student must solve and present 5 lab exercises of increasing complexity. Their statements are made available through the FIB corner (Racó).

Theory presentations

Each student must prepare a video that cannot be more than 10 minutes long, covering a specific topic to be chosen from the list of the proposed presentation topics. The student will present the video in class and answer questions about it. Please recall that the goal of these presentations is to illustrate the entire class about the chosen topics. To know which subjects have been already taken and choose your subject, follow the link that will be provided through the FIB corner (Racó). You can also choose a subject different from the ones proposed. In this case, you must send me a proposal, so that I can evaluate its difficulties and its adequacy to the course, before accepting it.

Some recommendations about the (video) presentations

From our experience, local students have some expertise in carrying out lab exercises and preparing their corresponding documentation, but they have less experience in preparing and doing presentations. Here are some hints that may be useful:

  1. The first thing to do is to seriously study the subject, without thinking of its presentation, but just of understanding the subject.
  2. In order to do that, please use the proposed references, do not replace them by other sources of information without consulting me first.
  3. Once this done, and before designing the presentation, it is convenient to answer the following questions:
    • Which are the main ideas behind the subject that I studied?
    • What can the audience understand, given their knowledge of the topic and the time that I have to make my presentation?
    • Which is the message that I want to transmit in my presentation?
    • How can I do it?
  4. There is no unique presentation model. The same topic can be presented by giving a lot of technical details of a given aspect, if this is what we want to underline because of its importance, as well as giving an overall vision by skimming the subject, if what matters is that the audience gets a global vision and the general flavor of the subject. One can make a very formal presentation (giving rigorous details of each step of an algorithm, for example), and a very intuitive one (by showing a demo of the same algorithm). It all depends on the goal of the presentation and the previous knowledge of the audience on the subject. In any case, it is convenient that you take into account some things:
    • Whatever your option is, it is important, for a good comprehension from your public, that in your presentation you make as explicit and clear as possible what the goal is of the topic that you will present.
    • Your video must be clear and easy to watch. If you are basing it on a presentation with slides, make sure not to have much text in each slide!
    • Do not forget to also indicate which references you are based on.
  5. When the script of your video is ready, I recommend that you rehearse it at least once before producing the video. Rehearsing should help you to evaluate at least:
    • Whether you will manage to make your video to accurately express what you want to say.
    • Whether your video fits in the time that you have been assigned (for this purpose, I recommend that you rehearse out loud in front of a chronometer). The time limit of the video is a hard constraint. Make sure that it does not go over time!

In the link below you will find a lot of simple but valuable advice on how to give a good talk, with many things that also apply to your theory video:
http://www.cs.dartmouth.edu/farid/downloads/tutorials/howtogiveagoodtalk.pdf

Resources

Bibliography

The slides of each topic end with references for that topic. However, in many cases the main bibliographic source is the following book, available online for the UPC community:

De Berg, Mark; Cheong, Otfried; Van Kreveld, Marc; Overmars, Mark. Computational geometry: algorithms and applications, 3rd ed. revised, Springer, 2008. Access to online version (UPC only)

Mathematical text editor

Mathematical edition is almost always and everywhere done using LaTeX. Not only it is used in universities (LaTeX has been used to write all the documents of this course, as well as all the problems lists, exams, and other mathematical texts that you had in your hands during your studies at the FIB) but it is the most extended editor of scientific texts (LaTeX is used to write all the textbooks of scientific publishers as important as Springer, and also most of the mathematics and computer science conferences around the world).

It’s a free source software that has versions for al operating systems (Linux, Mac, Windoxs, etc.), it helps writing all sort of scientific texts, such as articles, books and presentations, while it allows to incorporate figures previously produced in PDF by any drawing program.

You can download LaTeX from http://www.tug.org/.

References:

Examples of some popular LaTeX editors are TexWorks, WinEdt , or Texmaker.

Producing high-quality figures with Ipe

Each person likes preparing his/her figures with his/her favorite drawing program. I use Ipe (an evolution of xfig designed by a computational geometer), because it allows me to draw the geometric figures that I need, because it integrates text in LaTeX, and because it allows me to also prepare my presentations in a very easy what-you-see-is-what-you-get way.

It’s a free source software that has versions for all the operating systems (Linux, Windoxs, Unix, etc.). You can download it from http://ipe.otfried.org/.

Geometric constructions

In addition to producing your own drawings, you may whish to create and experiment with geometric constructions. If so, we recommend GeoGebra.

Thesis, grants, and projects

  • Are you interested in working in a geometric project, a Bacherlor’s (TFG) or Master’s (TFM) Thesis related to geometry? Or perhaps in starting a PhD in Computational Geometry?  Have a look here!
  • Also, don’t forget to take a look at what our research group does!