Technische Universität Braunschweig
  • Study & Teaching
    • Beginning your Studies
      • Prospective Students
      • Degree Programmes
      • Application
      • Fit4TU
    • During your Studies
      • Freshmen-Hub
      • Term Dates
      • Information for Freshman
      • Practical Information
      • Additional Qualifications
      • Financing and Costs
      • Special Circumstances
      • Campus life
    • At the End of your Studies
      • Discontinuation and Credentials Certification
      • After graduation
      • Alumni
    • For Teaching Staff
      • Strategy, Offers and Information
      • Learning Management System Stud.IP
      • Team Teaching and Media Education
    • Contact
      • Student Advice Centre
      • Academic Advice Service
      • Admissions Office
  • Research
    • Research Profile
      • Core Research Areas
      • Clusters of Excellence
      • Research Projects
      • Research Centres
    • Early Stage Researchers
      • Promotion of early career scientists
      • PhD-Students
      • Postdocs
      • Junior research group leaders
      • Junior Professorship and Tenure-Track
      • Habilitation
      • Service Offers for Scientists
    • Research Data & Transparency
      • Transparency in Research
      • Research Data
      • Open Access Strategy
      • Digital Research Announcement
    • Research Funding
      • Research funding
    • Contact
      • Research Services
      • Academy for Graduates
  • International
    • International Students
      • Why Braunschweig?
      • Degree seeking students
      • Exchange Studies
      • Doctorate (PhD)
      • Refugee Students
      • Welcome Programme
      • TU Braunschweig Summer School
    • Scientists
      • Mobile Researchers at the TU Braunschweig
      • Research Services and European Office
    • Language and intercultural competence training
      • Learning German
      • Intercultural Communication
    • International Profile
      • Internationalisation
      • International Cooperation
    • International House
      • Information for first semester students
      • Contact
      • News and Events
      • Advisory Services
      • Location
      • About us
  • TU Braunschweig
    • Our Profile
      • Aims & Values
      • Regulations and Guidelines
      • Alliances & Partners
      • Facts & Figures
      • Our History
    • Career
      • Working at TU Braunschweig
      • Vacancies
    • Economy & Business
      • Knowledge and Technology Transfer
      • Entrepreneurship
    • General Public
      • Access to the University Library
    • Media Services
      • Communications and Press Service
      • Communications and Press Service
      • Film and photo permits
      • Advices for scientists
      • Topics and stories
    • Contact
      • General Contact
      • Getting here
  • Organisation
    • Presidency & Administration
      • Presidency
      • Designated Offices
      • Administration
      • Committees
    • Faculties
      • Carl-Friedrich-Gauß-Fakultät
      • Faculty of Life Sciences
      • Architecture, Civil Engineering and Environmental Sciences
      • Faculty of Mechanical Engineering
      • Fakultät für Elektrotechnik, Informationstechnik, Physik
      • Faculty of Humanities and Studies in Education
    • Institutes
      • Institutes from A to Z
    • Facilities
      • University Library
      • Gauß-IT-Zentrum
      • International House
      • Sports Centre
      • Facilities from A to Z
    • Equal Opportunity Office
      • Equal Opportunity Office
      • Family
      • Diversity for Students
  • Search
  • Quicklinks
    • People Search
    • Webmail
    • Campus map
    • CloudStorage
    • Messenger
    • Cafeteria
    • Courses
    • Stud.IP
    • Library Catalogue
    • IT Self-Service
    • Information Portal (employees)
    • Link Collection
    • DE
    • EN
    • IBR Twitter
    • IBR YouTube
    • Facebook
    • Twitter
    • Instagram
    • YouTube
    • LinkedIn
Menu
  • Technische Universität Braunschweig
  • Organisation
  • Faculties
  • Carl-Friedrich-Gauß-Fakultät
  • Institutes
  • Institute of Operating Systems and Computer Networks
Logo IBR
IBR Login
  • Institute of Operating Systems and Computer Networks
    • News
    • About us
      • Whole Team
      • Directions
      • Floor Plan
      • Projects
      • Publications
      • Software
      • News Archive
    • Connected and Mobile Systems
      • Team
      • Courses
      • Theses
      • Projects
      • Publications
      • Software
      • Datasets
    • Distributed Systems
      • Team
      • Courses
      • Theses
      • Projects
      • Publications
      • Software
    • Algorithms
      • Team
      • Courses
      • Theses
      • Projects
      • Publications
    • Microprocessor Lab
    • Education
      • Summer 2023
      • Winter 2022/2023
      • Summer 2022
      • Theses
    • Services
      • Library
      • Mailinglists
      • Webmail
      • Knowledge Base
      • Wiki
      • Account Management
    • Spin-Offs
      • Docoloc
      • AIPARK
      • Confidential Technologies
    • Research Cooperations
      • IST.hub

Computational Geometry (Algorithmische Geometrie)

Semester
Winter 2021/2022
Winter 2022/2023Winter 2020/2021Winter 2019/2020Winter 2018/2019Winter 2017/2018Winter 2016/2017Winter 2011/2012Winter 2010/2011Winter 2009/2010Winter 2007/2008
ProgrammesComputer Science Master, Business Information Systems Master
IBR GroupALG (Prof. Fekete)
TypeLecture & Exercise
Lecturer
Photo
Prof. Dr. Sándor P. Fekete
Abteilungsleiter
s.fekete[[at]]tu-bs.de
+49 531 3913111
Room 335
Assistant
Photo
Christian Rieck
Wissenschaftlicher Mitarbeiter
rieck[[at]]ibr.cs.tu-bs.de
+49 531 3913114
Room 314
Hiwi
Photo
Peter Kramer
kramer[[at]]ibr.cs.tu-bs.de
Credits5
Hours2+1+1
Time & Place Lectures: Tuesdays, 3PM, weekly
Plenary tutorial : Wednesdays, 3PM (not regular, see email announcement!)
Start Lecture: November 02, 2021
Plenary Tutorial: November 18, 2021
Prerequisitesnone
LanguageEnglish
Certificates Studienleistung ("Study requirement"): participating in live quizzes and question sheets
Exam: Oral exam
Content

Geometric algorithms are of fundamental interest for a large spectrum of topics, both from theory and practice. In this class, we will start from the basic foundations, and work our way towards advanced topics.
In this semester, we will try a special online format, with participant from different countries, giving us the opportunity to do international exchange in the same classroom. We will discuss how to make the best of this opportunity - so feel free to bring in new ideas and suggestions.

Topics are:

  • Geometric problems and data structures
  • Convex hulls
  • Closest pairs
  • Voronoi diagrams
  • Polygon triangulation
  • Point triangulation
  • Location problems
  • Tours and polygons
References
  • Mark de Berg, Marc van Kreveld, Mark Overmars and Otfried Schwarzkopf: Computational Geometry: Algorithms and Applications, Second. Edition, pages 367, Springer-Verlag, 2000 (deBerg2000, BibTeX)
  • Rolf Klein: Algorithmische Geometrie, pages 1-355, examen.press, 1997 (Klein1997, BibTeX)
  • Franco P. Preparata and Michael Ian Shamos: Computational Geometry: An Introduction, Springer, 1985 (Preparata1985, BibTeX)

General announcements

  • The next lecture will be streamed on February 15 on YouTube.
  • The next exercise / discussion meeting will be on February 16.

Lectures

  • Lecture #1, Nov 02, 2021 (Introduction)
    • Video: [Youtube], [IBR]
    • Slides: [pdf]
    • Quiz: [pdf]
    • Scientific video: Coordinated Motion Planning
  • Lecture #2, Nov 09, 2021 (Convex hull)
    • Video: [Youtube], [IBR]
    • Slides: [pdf]
    • Quiz: [pdf]
    • Original publications: Jarvis' March, Quickhull
  • Lecture #3, Nov 16, 2021 (Convex hull)
    • Video: [Youtube], [IBR]
    • Slides: [pdf]
    • Quiz: [pdf]
    • Original publications: Preparata/Hong, Graham's Scan, Kirkpatrick/Seidel, Chan's algorithm
  • Lecture #4, Nov 23, 2021 (Closest pair of points)
    • Video: [Youtube], [IBR]
    • Slides: [pdf]
    • Quiz: [pdf]
    • Original publications: Shamos / Bentley, Ben-Or, Compute Median
  • Lecture #5, Nov 30, 2021 (Closest pair of points)
    • Video: [Youtube], [IBR]
    • Slides: [pdf]
    • Quiz: [pdf]
    • Original publications: Randomized Incremental Construction
  • Lecture #6, Dec 07, 2021 (Voronoi diagram)
    • Video: [Youtube], [IBR]
    • Slides: [pdf]
    • Quiz: [pdf]
  • Lecture #7, Dec 14, 2021 (Voronoi diagram)
    • Video: [Youtube], [IBR]
    • Slides: [pdf]
  • Lecture #8, Dec 21, 2021 (Voronoi diagram)
    • Video: [Youtube], [IBR]
    • Slides: [pdf]
    • Quiz: [pdf]
    • Original publications: Fortune
  • Lecture #9, Jan 11, 2022 (Voronoi games)
    • Video: [Youtube], [IBR]
    • Slides: [pdf]
    • Original publications: Ahn 2001, Ahn 2004, One-Round Voronoi Game, Cheong 2007, Muller / Preparata, Teramoto 2011, Voronoi Game on Graphs, One-Round Manhattan Voronoi Game
  • Lecture #10, Jan 18, 2022 (Polygon triangulation)
    • Video: [Youtube], [IBR]
    • Slides: [pdf]
    • Original publications: Robot Triangulation, Chazelle 1991, Clarkson 1989, Garey 1978, Kirkpatrick 1992, Tarjan 1988
  • Lecture #11, Jan 25, 2022 (Point triangulation)
    • Video: [Youtube], [IBR]
    • Slides: [pdf]
    • Original publications: Delaunay, Triangulations - ETH, MaxMin Angle, MinMax Angle, Mulzer-Rote MWT, Haas MWT, MaxMin Edge Length, MinMax Edge Length
  • Lecture #12, Feb 01, 2022 (Location problems)
    • Video: [Youtube], [IBR]
    • Slides: [pdf]
    • Original publications: Continuous Weber Problem, Continuous Fermat Weber Problem, Solving Hard to Approximate Easy, Median, Algebraic Degree of Geometric Optimization, Paths Among Obstacles, Impossibility of Solving Fifth Degree Equation (French)
  • Lecture #13, Feb 15, 2022
    • Video: [Youtube], [IBR]
    • Slides: [pdf]
    • Original publications: Hamiltonian Cycles in Grid Graphs, MaxTSP (Russian), MaxTSP, Lawn Mowing and Milling, Min Stars Max Matching, Solving Hard to Approximate Easy, Geometric Max TSP, Longest Geometric Tours, Non-Simple Polygons with Min Perimeter, Cycle Cover with Turn Cost

Exercise / discussion meetings

  • Meeting #1, Nov 18, 2021 // Slides, Convex layers, Euler characteristic
  • Meeting #2, Dec 08, 2021 // Slides, Wallace-Bolyai-Gerwien theorem, Visualizing scissors congruence, numberphile video on Hilbert's third problem, Rotating calipers
  • Meeting #3, Jan 19, 2022 // Slides, Smallest enclosing disk - Welzl, Closest point problems - Shamos and Hoey, k-center problem, Smallest annuli with outliers, Abstract Voronoi diagrams - Rolf Klein
  • Meeting #4, Feb 02, 2022 // Slides, Trapezoidal maps - Seidel, Triangulation hierarchy - Kirkpatrick, Order type realization, Irrational guards, AGP is exist-R complete
  • Meeting #5, Feb 16, 2022 // Slides, k-dops collision detection, Intersection of convex polygons, Geometric intersection problem, Visibility polygon demo site

Mailing list

There is a mailing list for this class. Please sign up, as we will use it for communication. This list is moderated; participants from outside of TU Braunschweig will be approved manually, which may cause a slight initial delay. If you run into any problems, please contact Christian.


last changed 2022-02-16, 16:20 by Christian Rieck

For All Visitors

Vacancies of TU Braunschweig
Career Service' Job Exchange 
Merchandising

For Students

Term Dates
Courses
Degree Programmes
Information for Freshman
TUCard

Internal Tools

Glossary (GER-EN)
Change your Personal Data

Contact

Technische Universität Braunschweig
Universitätsplatz 2
38106 Braunschweig

P. O. Box: 38092 Braunschweig
GERMANY

Phone: +49 (0) 531 391-0

Getting here

© Technische Universität Braunschweig
ImprintPrivacyAccessibility