Master in Advanced Mathematics and Mathematical Engineering (MAMME)
Departament de Matemàtiques
Facultat de Matemàtiques i Estadística
Universitat Politècnica de Catalunya
General information on the course (syllabus, references, evaluation, etc.).
Particular information on the course for the current term (teaching hours, classroom, calendar, etc.)
Instructors
- Rodrigo Silveira (first half of the course – year 2023-2024)
- Clemens Huemer (second half of the course – year 2023-2024)
- Julian Pfeifle
Some material for the course
- Background
- Basic tool: orientation tests
- Brief digression: Borsuk’s number.
- Intersecting line segments: Bentley-Ottman’s algorithm
- Computing the convex hull of a finite point set
- Convex hulls in 2D
- Convex hull of a simple polygon: a curiosity
- Convex hulls in 3D
- Convex hulls in higher dimensions
- An applet about 2D convex hulls
- Intersecting half-planes and related problems: duality, computing the intersection of half-planes, solving linear programs, and computing the minimum spanning circle of a set of points.
- An applet for visualizing dualities in the plane.
- Median finding
- Triangulating polygons
- Triangulating point sets
- Proximity
- Point location in planar subdivisions
- Arrangements of lines
- Robustness in geometric computations:
- Robustness and CGAL
- Classrom Examples of Robustness Problems in Geometric Computations, by L. Kettner, K. Melhorn, S. Pion, S. Schirra and C. Yap.
Problems and assignments
There will be two problem presentations, to be done in teams of two students. The problem of each team will be chosen from a list that will be posted in Atenea.
The provisonal dates for the problem presentations are:
- Presentation of problem 1: October 5, 2023.
- Presentation of problem 2: October 26, 2023.
References about algorithmic geometry
- Berg, Mark de; Cheong, Otfried; Kreveld, Marc van; Overmars, Mark. Computational geometry: algorithms and applications. 3rd ed. revised. Berlin: Springer, 2008. ISBN 9783540779735.
- Boissonnat, J. D.; Yvinec, M. Algorithmic Geometry. Cambridge: Cambridge University Press, 1997. ISBN 0521565294.
- Edelsbrunner, Herbert. Algorithms in combinatorial geometry. Berlín: Springer, 1987. ISBN 354013722X.
Please see the official general information for this course for more information.
Further resources
- 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, and probably all the problems lists, exams, and other mathematical texts that you had in your hands during your previous studies) 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 all 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:
- Introductory text: L. Lamport, LaTeX, a Document Preparation System, Addison-Wesley, 2nd ed., 1994.
- The LaTeX project site.
- The LaTeX wikibook.
Examples of some popular LaTeX editors are TexWorks, WinEdt , or Texmaker.
- Drawings
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 IPE from http://ipe.otfried.org/
- Geometric constructions
In addition to producing your own drawings, you may wish to create and experiment with geometric constructions. If so, I recommend GeoGebra: http://www.geogebra.org/cms/
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!