The ASCI course on computational geometry is a `capita selecta' course. This means that a number of different, independent topics within the area of computational geometry will be presented. You may find some topics more interesting than others. It should be useful to know something about all topics, though, which is why this course is given this way. The topics and lecturers are given below.
April 16 - April 20 (Monday - Friday), 2007.
The course will be held at the Utrecht University
campus (De Uithof), just East of Utrecht city. For information on the campus
and how to reach it, click here.
All rooms are in BBL, the Buys Ballot Laboratorium.
Monday, April 16:
Shape Matching (Remco Veltkamp), room BBL 430 Classes start each day at 10.00 and will continue
until roughly 17.00. Classes will consist of both lecturing time and problem
solving
time. There will be a lunch break. Attendance at all five days is obligatory.
All participating students are asked to read a
paper and make an assignment. This will be done a few weeks
after the end of the course.
Please select one of the topics below for your presentation or
survey. Then send an e-mail to Remco, Marc or Leo (depending on the choice)
to confirm your choice (and avoid duplicate choice), and specify if you
want to do a survey or a presentation. In any case, send a cc of the e-mail
to Marc (so that he knows who want to do a survey and who a presentation).
In any case, the survey or presentation needs to have high quality,
in the sense of well-thought out content, a good structure, and a high
level of care with respect to layout, grammar and spelling. This holds
for presentation and survey. The length of a presentation should be
30 minutes. The length of a survey should be 8-12 pages. Quality is more
important than length!
The course material for the shape matching lecture on Monday is:
If you take shape matching ming as your topic, some suggestions for the
survey or presentation are:
Schedule:
Tuesday, April 17:
Spatial Data Mining and Computational Geometry (Marc van Kreveld), room BBL
505
Wednesday, April 18:
Approximation Algorithms for Geometric Problems (Marc van Kreveld), room BBL
361
Thursday, April 19: Geometric Algebra (Leo Dorst), room BBL 505
Friday, April 20: Geometric Algebra (Leo Dorst), room BBL 420
Examination:
Course material
Slides1, slides2, slides3.
Background survey papers on shape matching are for
example:
The following slides were used for the presentation
on spatial data mining and computational geometry on Tuesday:
Slides 1,
Slides 2.
If you take spatial data mining as your topic, some suggestions for the survey or presentation are:
The following texts were used for the presentation
on approximation algorithms on Wednesday:
Bern and Eppstein: Approximation algorithms for geometric
problems.
Arora: Approximation schemes for NP-hard geometric
optimization problems: a survey.
Agarwal,
van Kreveld and Suri: Label placement by maximum independent set in rectangles.
Chan: Approximating the diameter, width, smallest enclosing
cylinder, and minimum-width annulus.
If you choose approximation algorithms as your topic, suggestions for a presentation are:
More information and material for the geometric algebra part of this course here.
If you choose to take the Geometric Algebra part of the course as your subject, any option on doing a presentation or report can be discussed. It is of course most interesting if you can select something related to your own work. General suggestions are: