Academic year 2013-14
Computational Geometry
| Degree: | Code: | Type: |
| Bachelor's Degree in Computer Science | 21447 | Optional subject |
| Bachelor's Degree in Telematics Engineering | 22621 | Optional subject |
| Bachelor's Degree in Audiovisual Systems Engineering | 21650 | Optional subject |
| ECTS credits: | 4 | Workload: | 100 hours | Trimester: | 2nd |
| Department: | Dept. of Information and Communication Technologies |
| Coordinator: | Josep Blat |
| Teaching staff: | Veronika Zimmer, Arash Bahrehmand, Josep Blat |
| Language: | English |
| Timetable: | |
| Building: | Communication campus - Poblenou |
Geometry is a discipline molt frequently used in some areas of Computer Science and Media Systems, especially in Computer Graphics (and 3D games), Robotics, CAD/CAM, and GIS (Geographical Information Systems). Computational Geometry is a relatively recent subdiscipline, which is geared towards the solution of problems in those areas, on a geometrical basis, and providing efficient algorithms, with suitable data structures.
This course on Computational Geometry has to main objectives:
- to consolidate the more basic geometric concepts, so that their better understanding and manipulation could support their use in applications.
- to introduce the most characteristic aspects of the modern approximation to Computational Geometry, both in terms of algorithms and data structures.
The course intends to provide better grounding to advanced Computer Graphics, for students interested in this area.
The course adopts a very practical approach: solving problems, implementing some graphical applications is the key point to enable the students in the aspects of understanding and manipulation mentioned above.
The students will benefit from a background in maths and programming, but the content is quite self-contained.
|
Competències transversals |
Competències específiques |
InstrumentalsG1. Capacitat d'anàlisi i síntesiG2. Capacitat d'organització i planificacióG7. Capacitat de comunicar-se en contextos acadèmics i professionals de forma oral i escrita en anglès, tant davant audiències expertes com inexpertes
SistèmiquesG12. Capacitat per a progressar en els processos de formació i aprenentatge de manera autònoma i contínua G14. Capacitat de motivació per la qualitat i per l'assoliment |
Competències Específiques ProfessionalsH2. Disposar dels fonaments matemàtics, físics, econòmics i sociològics necessaris per interpretar, seleccionar, valorar, i crear nous conceptes, teories, usos i desenvolupaments tecnològics relacionats amb la informàtica, i la seva aplicació.
H4. Aprendre de manera autònoma nous coneixements i tècniques adequats per a la concepció, el desenvolupament o l'explotació de sistemes informàtics.
B16. Conèixer els fonaments teòrics de la programació i utilitzar de forma pràctica els mètodes i llenguatges de programació per al desenvolupament de sistemes software.
Competències Específiques
AU20. Assolir els coneixements bàsics de les tècniques de traçat de rajos, del modelatge geomètric i de la generació d’imatges sintètiques
|
The evaluation will be made on the material delivered, as requested in the sessions of theory (problems, algorithms pseudo-code on paper, 50% of the overall mark), seminars, and labs (reports, source code fully commented, 50% of the overall mark) – see the Aula Global for further information.
If some part of the work is failed, it can be re-submitted before the marks delivery in April, with a personal interview - or in the established 'resubmission' period in July, again with a personal interview.
Theory contents
1- Basic geometric background
1.1 Affine and metric geometry
1.2 Geometric transformations in 2D and 3D; perspective representation
1.3 Curves and surfaces
2- Introduction to Computational Geometry
2.1 Elementary geometric algorithms (intersections, convexity, ...)
2.2 Segments intersection; elementary triangulation
2.3 Voronoi diagrams
3- Selected advanced topics
Lab contents
The lab contents, developed during seminars and labs will provide practical projects where data structures and key al gorithms are implemented, and a research topic is undertaken.
There will be 3 major labs:
1. Creation of an octree from a mesh and application to ray-picking;
2. Delaunay triangulation;
3. Research project.
The course has got a practical approach, and the work of the students solving exercises, providing example pseudo-code, and implementing programs in labs is a key ingredient. The overall schedule of the subject is:
|
|
Tuesday |
Thursday |
Friday |
|
W1
|
Theory |
S101/ S102 (1h each) |
Lab |
|
W2
|
Lab |
Theory |
Lab |
|
W3
|
S101/ S102 (1h each) |
Theory |
|
|
W4
|
Lab |
Theory Lab1 delivery |
|
|
W5
|
Lab |
Theory |
|
|
W6
|
S101
|
S102 |
Theory |
|
W7 |
Lab |
Theory Lab2 delivery |
|
|
W8 |
Lab |
Theory |
|
|
W9 |
Theory |
S101
|
S102 |
|
W10 |
|
|
|
Lab3 will be presented orally the day scheduled for the exam or the last session of the course, and submitted previously.
The main reference for the course is the book:
Mark de Berg, Otfried Schwarzkopf, Marc van Kreveld , Mark Overmars: Computational Geometry: Algorithms and Applications (Second Edition), Springer-Verlag, 2000. (There is a third edition, with minor changes with respect to the second, which should be available soon in the UPF CRAI; parts of the book and complementary information can be found at http://www.cs.uu.nl/geo book/).
Some other references are: Joan Trias Pairó: Geometria per a la informàtica gràfica i el CAD, Edicions UPC, Barcelona, 1999. (There is an accompanying lab book: Joan Trias Pairó: Laboratori de Geometria Computacional, Edicions UPC, Barcelona, 1996.)
We might be using some material (exercises) from Computational Geometry courses taught at the UPC, the links to the courses are:
http://www-ma2.upc.es/~geoc/indexCAT.html
http://www-ma2.upc.es/~geoc/vella_GEOC/
Another book on CG is:
Franco P. Preparata, Michael Ian Shamos: Computational Geometry: an Introduction , Springer Verlag, New York [etc.], 1985.
Some chapters of the following books are relevant as well:
Michael F. Worboys: Geographic Information Systems: a Computing Perspective, Taylor & Francis, London, 1995.
Marc van Kreveld et al. (eds.): Algorithmic Foundations of Geographic Information Systems, Springer Lecture Notes in Computer Science 1340, Berlin & New York, 1997.
Theodosios Pavlidis: Algorithms for Graphics and Image Processing, Springer Verlag, 1982