Klausurergebnisse / -Einsicht:

Termin für die Einsicht ist der 10.09.2014, 14 Uhr. Raum: 0.124.

Punkte Noten
110 1.0
104 1.3
98 1.7
92 2.0
86 2.3
80 2.7
74 3.0
68 3.3
62 3.7
55 4.0


Termine (Übungen/Vorlesungen):

Zeit Raum Beginn
Di 14:00-15:30 0.108 15.04.14
Mi 09:45-11:15 0.108 09.04.14


Gruppe Zeit Raum Tutor Beginn
1 Mi 09:45-11:15 (14-tg.) 0.108 Daniel Bahrdt


Nummer Anmerkungen
Blatt 0
Blatt 1 Daten
Blatt 2 paper, code, Lösung code
Blatt 3
Blatt 4 code
Blatt 5 CGAL Blatt4. VirtualBox Appliance mit allen nötigen tools hier zum download.
Username: compgeo Passwort: compgeo. Root-Passwort: compgeo

Skript zur Vorlesung

Scribe Notes stehen hier (Änderungen werden im Laufe des Semesters eingepflegt).


Zusammenfassung inkl. Ausschlüsse für die Prüfungen


  • 09.04.: Einleitung
  • 15.04.: Range-Trees
  • 16.04.: Segment/Intervallbäume
  • 22.04.: Priority Search Trees; CH (D&C, Giftwrapping)
  • 23.04.: CH (Graham Scan, Chan, RIC)
  • 29.04.: CH (d>2); Line Segment Intersection (Sweep)
  • 30.04.: Übung
  • 06.05.: Line Segment Intersection (RIC)
  • 07.05.: Kirkpatrick-Hierarchy
  • 13.05.: Delaunay Triangulierung; lokal Delaunay, Lifting Map
  • 20.05.: Delaunay Flipping; Winkeleigenschaften, Terminierung
  • 21.05.: Dualität Voronoidiagramm <-> Delaunay Triangulierung,
  • 26.05.: Delaunay RIC


Computational GeometryAlgorithms and Applications
de Berg, Cheong, van Kreveld, Overmars

Originalarbeit von Raimund Seidel zur Polygontriangulation in O(n log*n) findet sich hier.

Originalarbeit von Matousek/Sharir/Welzel zum subexponentiellen Simplex findet sich hier.

Originalarbeit zu Floating-Point-Fehlerschranken findet sich hier.


[Jun’19] Our paper on trajectory storage and retrieval has been accepted at SSTD 2019!

[Nov’18] Our paper on regret minimization has been accepted at AAAI 2019 (acceptance rate 16.2%)!

[Oct’18] Our paper on alternative route planning for bicycles has been accepted at ALENEX 2019!

[Apr’18] Martin has successfully defended his Ph.D. thesis. Congratulations!

[Jan’18] The journal version of our paper on k-hop path covers will receive a publication award from our university!

[Nov’17] Our paper on a theoretical explanation for several speed-up techniques for route computation has been accepted at AAAI 2018!

[Oct’17] Thomas’ paper on area preserving map simplification has been accepted at ALENEX 2018!

[May’17] Daniel’s and Martin’s paper on rational points on the unit sphere has been accepted at ISSAC 2017!

[Apr’17] Our paper on personalized route planning with dynamic approximation guarantees has been accepted at SEA 2017!

[Jan’17] Martin’s paper on map matching has been accepted at SIAM SDM 2017!

[Nov’16] Our paper on simultaneous maze solving has been accepted at AAAI 2017.

[Okt’16] Two papers, one on growing balls (!), the other on map simplification will be presented at ALENEX 2017.

[Sep’16] Our paper on Deducing Individual Driving Preferences has been accepted at the 24th ACM SIGSPATIAL GIS 2016.

[Feb’16] Our paper on placing loading stations for EVs has been accepted at ICAPS 2016.

[Jul’15] Paper about our GeoSearch Engine OSCAR at the 16th Int. Conf on Web Information Systems Engineering (WISE)!

[Jun’15] We feel very honored to have our VLDB’14 paper almost verbatimly reproduced in the ‘prestigous’ journal IJSETR, see here. Yeah! 😉

[Feb’15] We were lucky to receive a Google Research Award for research on personalized route planning!

[Sep’14] Our paper “On k-Path Covers and their Applications” has received a Best Paper Award at the 40th Int. Conference on Very Large Databases (VLDB) in Hangzhou (5 out of 139 accepted out of 695 submitted papers).

[Sep’14] Our paper on “Energy-efficient Routing: Taking Speed into Account” has received a Best Paper Award at the 37th German Conference on Artificial Intelligence (KI).

[Jul’14] Our paper “Placement of Loading Stations for Electric Vehicles: No Detours Necessary!” has received a Honorable Mention at the 28th AAAI Conference on Artificial Intelligence (AAAI) in Quebec City (5 nominated out of 398 accepted out of 1406 submitted papers).

[Mar’14] Our StuPro-Team has completed their great “SchulScheduler” project.

[Nov’13] Jochen has defended his PhD thesis and moved on to TomTom.

[Feb’13] Sabine has defended her PhD thesis (already in Dec’12) and received the INFOS award for best CS PhD thesis in 2012!

[Mar’12] Our paper Path Shapes - An Alternative Method for Map Matching and Fully Autonomous Self-Localization presented at GIS 2011 has received the Best Paper Award, also see the ACM SIGSPATIAL newsletter.