SluitenHelpPrint
Switch to English
Cursus: INFOGA
INFOGA
Geometrische algoritmen
Cursus informatieRooster
CursuscodeINFOGA
Studiepunten (ECTS)7,5
Categorie / NiveauM (Master)
CursustypeCursorisch onderwijs
VoertaalEngels
Aangeboden doorFaculteit Betawetenschappen; Graduate School of Natural Sciences;
Contactpersoonprof. dr. M.J. van Kreveld
Telefoon+31 30 2534119
E-mailM.J.vanKreveld@uu.nl
Docenten
Docent
prof. dr. M.J. van Kreveld
Feedback en bereikbaarheid
Overige cursussen docent
Docent
dr. W van Toll
Overige cursussen docent
Blok
4  (24-04-2017 t/m 07-07-2017)
Aanvangsblok
4
TimeslotC: MA-middag/namiddag,DI-middag, DO-ochtend
Onderwijsvorm
Voltijd
Opmerkinghttp://www.cs.uu.nl/education/vak.php?vak=INFOGA
Cursusinschrijving geopendvanaf 30-01-2017 t/m 26-02-2017
AanmeldingsprocedureOsiris
Inschrijven via OSIRISJa
Inschrijven voor bijvakkersJa
VoorinschrijvingNee
Na-inschrijvingJa
Na-inschrijving geopendvanaf 03-04-2017 t/m 04-04-2017
WachtlijstJa
Plaatsingsprocedureadministratie onderwijsinstituut
Cursusdoelen
After completing the course, the student
  • Has knowledge of the most important techniques to develop geometric algorithms.
  • Has knowledge of the most important proof methods to determine the efficiency of geometric algorithms.
  • Knows about possible applications of geometric algorithms, like in robotics, graphics and geographic information science.
  • Knows how an applied problem can be converted into an abstract problem that can be tackled with techniques from computational geometry.
  • Knows how to apply the sweep-line technique correctly, including the use of status structure, event list, event handling, and efficiency analysis.
  • Knows how to apply the technique of randomized incremental construction for linear programming and minimum enclosing circle, inclusive of the probabilistic proof techniques needed.
  • Knows what the planar point location problem is and how it can be solved with randomized incremental construction.
  • Knows about kd-trees and range trees: definition, construction algorithms, and query algorithms. Also, performance of these algorithms.
  • Knows about Voronoi diagrams of points, Voronoi diagrams of line segments, furthest site Voronoi diagrams, and properties of these structures. Also, the sweep-line algorithm to construct them.
  • Knows about line segment intersection, map overlay, and polygon triangulation by a sweepline algorithm.
  • Can independently analyze a geometric problem by discovering properties that can lead to an algorithmic solution
  • Can analyze his/her solution on correctness and efficiency.
Inhoud
In many areas of computer science (robotics, computer graphics and virtual reality, and geographic information systems are some examples) it is necessary to store, analyze, and create or manipulate spatial data. This course deals with the algorithmic aspects of these tasks: the design and analysis of geometric algorithms and data structures are studied.
Ingangseisen
Je moet een geldige toelatingsbeschikking hebben
Verplicht materiaal
-
Aanbevolen materiaal
Boek
M. de Berg, M. Overmars, M. van Kreveld, and O. Schwarzkopf. Computational Geometry: Algorithms and Applications (2nd edition). Springer-Verlag, Heidelberg, 2000. ISBN 3-540-65620-0.
Software
Geen software nodig
Werkvormen (aanwezigheidsplicht)
Hoorcollege

Toetsen
Eindresultaat
Weging100
Minimum cijfer6

SluitenHelpPrint
Switch to English