Department of Information and Computing Sciences

Departement Informatica Onderwijs
Bachelor Informatica Informatiekunde Kunstmatige intelligentie Master Computing Science Game&Media Technology Artifical Intelligence Business Informatics

Onderwijs Informatica en Informatiekunde

Vak-informatie Informatica en Informatiekunde

Geometric algorithms

Website:website containing additional information
Course code:WIGA
Credits:5.72 ECTS (=4 old credit points)
Period:period 1 (week 36 through 43, i.e., 3-9-2001 through 26-10-2001; retake week 1)
Participants:up till now 7 subscriptions
Schedule:Dit is een oud rooster!
formgrouptimeweekroomteacher
college   Mon 11-1336-42 MIN-207
Thu 13-1536-42 BBL-160
lecture          Marc van Kreveld
 
Contents:Veel berekeningstaken voor computers zijn meetkundig van aard. De taken vinden hun oorsprong bijvoorbeeld in de robotica (om routes en bewegingen te berekenen), de computer graphics (om plaatjes te berekenen) en de geografische informatiesystemen (om thematische kaarten te combineren). Dit meetkundig rekenen moet bij voorkeur efficiënt gedaan worden. Het vak geometrische algoritmen gaat over het oplossen van uit de praktijk gemotiveerde problemen, waarvoor algoritmische oplossingen gegeven en geanalyseerd worden.
Literature:De Berg et al., Computational Geometry - algorithms and applications, Springer-Verlag, second edition, 2000.
Course form:hoorcollege.
Exam form:Tentamen (70) en twee huiswerkopgaven (elk 15%). Elk van de drie onderdelen moet minstens een 5 hebben.
Minimum effort to qualify for 2nd chance exam:Om aan de aanvullende toets te mogen meedoen is ontbreken van ten hoogte 1 toetsactiviteit toegestaan.
Description:Bij het college geometrische algoritmen worden drie hoofdtechnieken behandeld. Dit zijn de plane sweep techniek, de gerandomiseerde incrementele techniek en de datastructureringstechniek. Daarnaast komen de technieken divide-and-conquer en gewone incrementele constructie ook aan bod. Tenslotte is er nog gespecialiseerde techniek fractional cascading. Met behulp van deze aanpakken wordt een aantal geometrisch-algoritmische problemen opgelost. Dit zijn subdivisie opslag, convex hull berekening, lijn segment intersectie, polygoon triangulatie, lineair programmeren, orthogonaal range zoeken, point location, Voronoi diagram berekening, arrangement constructie en Delaunay triangulatie. De concepten punt-lijn dualiteit, discrepancy, levels en zones spelen ook een rol in deze oplossingen.

Elk geometrisch-algoritmisch probleem wordt eerst gemotiveerd vanuit een practische toepassing. Vanuit de toepassing wordt dan het geometrische probleem afgeleid, zodat de operationalisering ook aandacht krijgt. De gegeven oplossing wordt op de bekende algoritmische manier geanalyseerd op efficientie en geheugengebruik, met behulp van grote-O notatie.

wijzigen?