Technische Universität Braunschweig
  • Study & Teaching
    • Beginning your Studies
      • Prospective Students
      • Degree Programmes
      • Application
      • Fit4TU
      • Why Braunschweig?
    • During your Studies
      • Fresher's Hub
      • Term Dates
      • Courses
      • Practical Information
      • Beratungsnavi
      • Additional Qualifications
      • Financing and Costs
      • Special Circumstances
      • Health and Well-being
      • Campus life
    • At the End of your Studies
      • Discontinuation and Credentials Certification
      • After graduation
      • Alumni*ae
    • For Teaching Staff
      • Strategy, Offers and Information
      • Learning Management System Stud.IP
    • Contact
      • Study Service Centre
      • Academic Advice Service
      • Student Office
      • Career Service
  • Research
    • Research Profile
      • Core Research Areas
      • Clusters of Excellence at TU Braunschweig
      • Research Projects
      • Research Centres
      • Professors‘ Research Profiles
    • Early Career Researchers
      • Support in the early stages of an academic career
      • 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 Network
      • Research funding
    • Contact
      • Research Services
      • Academy for Graduates
  • International
    • International Students
      • Why Braunschweig?
      • Degree seeking students
      • Exchange Studies
      • TU Braunschweig Summer School
      • Refugees
      • International Student Support
    • Going Abroad
      • Studying abroad
      • Internships abroad
      • Teaching and research abroad
      • Working abroad
    • International Researchers
      • Welcome Support
      • PhD Studies
      • Service for host institutes
    • Language and intercultural competence training
      • Learning German
      • Learning Foreign Languages
      • Intercultural Communication
    • International Profile
      • Internationalisation
      • International Cooperations
      • Strategic Partnerships
      • International networks
    • International House
      • About us
      • Contact & Office Hours
      • News and Events
      • International Days
      • 5th Student Conference: Internationalisation of Higher Education
      • Newsletter, Podcast & Videos
      • Job Advertisements
  • TU Braunschweig
    • Our Profile
      • Aims & Values
      • Regulations and Guidelines
      • Alliances & Partners
      • The University Development Initiative 2030
      • Foundation University
      • Facts & Figures
      • Our History
    • Career
      • Working at TU Braunschweig
      • Vacancies
    • Economy & Business
      • Entrepreneurship
      • Friends & Supporters
    • General Public
      • Check-in for Students
      • The Student House
      • Access to the University Library
    • Media Services
      • Communications and Press Service
      • Services for media
      • Film and photo permits
      • Advices for scientists
      • Topics and stories
    • Contact
      • General Contact
      • Getting here
  • Organisation
    • Presidency & Administration
      • Executive Board
      • Designated Offices
      • Administration
      • Committees
    • Faculties
      • Carl-Friedrich-Gauß-Fakultät
      • Faculty of Life Sciences
      • Faculty of Architecture, Civil Engineering and Environmental Sciences
      • Faculty of Mechanical Engineering
      • Faculty of Electrical Engineering, Information Technology, Physics
      • Faculty of Humanities and Education
    • Institutes
      • Institutes from A to Z
    • Facilities
      • University Library
      • Gauß-IT-Zentrum
      • Professional and Personnel Development
      • International House
      • The Project House of the TU Braunschweig
      • Transfer Service
      • University Sports Center
      • Facilities from A to Z
    • Equal Opportunity Office
      • Equal Opportunity Office
      • Family
      • Diversity for Students
  • Search
  • Quicklinks
    • People Search
    • Webmail
    • cloud.TU Braunschweig
    • Messenger
    • Cafeteria
    • Courses
    • Stud.IP
    • Library Catalogue
    • IT Services
    • Information Portal (employees)
    • Link Collection
    • DE
    • EN
    • IBR YouTube
    • Facebook
    • Instagram
    • YouTube
    • LinkedIn
    • Mastodon
Menu
  • Organisation
  • Faculties
  • Carl-Friedrich-Gauß-Fakultät
  • Institutes
  • Institute of Operating Systems and Computer Networks
  • Courses
  • Winter 2023/2024
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
    • Reliable System Software
      • Overview
      • Team
      • Teaching
      • Theses & Jobs
      • Research
      • Publications
    • Algorithms
      • Team
      • Courses
      • Theses
      • Projects
      • Publications
    • Microprocessor Lab
    • Education
      • Summer 2025
      • Winter 2024/2025
      • Theses
    • Services
      • Library
      • Mailinglists
      • Webmail
      • Knowledge Base
      • Wiki
      • Account Management
      • Services Status
    • Spin-Offs
      • Docoloc
      • bliq (formerly AIPARK)
      • Confidential Technologies
    • Research Cooperations
      • IST.hub

Computational Geometry (Algorithmische Geometrie)

Semester
Winter 2023/2024
Winter 2024/2025Winter 2022/2023Winter 2021/2022Winter 2020/2021
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
Peter Kramer
Wissenschaftlicher Mitarbeiter
kramer[[at]]ibr.cs.tu-bs.de
+49 531 3913113
Room 332
Hiwi
Photo
Tobias Wallner
Wissenschaftlicher Mitarbeiter
wallner[[at]]ibr.cs.tu-bs.de
+49 531 3913116
Room 315
Credits5
Hours2+1+1
Time & Place Rooms changed starting 21.11.
Lecture: Tuesdays, 3:00 p.m. - 4:30 p.m. (Room SN19.1)
Plenary tutorial: Thursdays, 3:00 p.m. - 4:30 p.m. (Room IZ161)
Start The first lecture will be held on 02.11.2023 in IZ161.
The first plenary tutorial will be held on 16.11.2023 in IZ161.
Prerequisitesnone
LanguageEnglish
Certificates Coursework ("Studienleistung"): Live quizzes and question sheets
Exam: Written exam on 14.03.2024, 2:00 p.m. in SN 19.1
Exam registration is handled by your corresponding examination office. No further registration with the institute is required to attend.
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.

The participants learn the basic concepts of geometric algorithms. They know how to gauge the difficulty of geometric problems and formulate appropriate objectives. They are able to master different solution techniques and are capable of developing algorithmic methods for new challenges. They understand the practical relevance of problems and solutions.

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)

Lectures

  • Lecture #1, Nov 02, 2023 (Introduction)
    • Video from previous year: [Youtube]
    • Slides: [Download]
    • Original publications: Shamos / Bentley, Ben-Or, Compute Median
  • Lecture #2, Nov 07, 2023 (Convex hull)
    • Video from previous year: [Youtube]
    • Slides: [Download]
    • Original publications: Jarvis' March, Quickhull
  • Lecture #3, Nov 14, 2023 (Convex hull)
    • Video from previous year: [Youtube]
    • Slides: [Download]
    • Original publications: Preparata/Hong, Graham's Scan, Kirkpatrick/Seidel, Chan's algorithm
  • Lecture #4, Nov 21, 2023 (Closest pairs of points)
    • Video from previous year: [Youtube]
    • Slides: [Download]
    • Original publications: Shamos / Bentley, Ben-Or, Compute Median
  • Lecture #5, Nov 28, 2023 (Closest pairs of points)
    • Video from previous year: [Youtube]
    • Slides: [Download]
    • Original publications: Randomized Incremental Construction
  • Lecture #6, Dec 5, 2023 (Voronoi diagram)
    • Video from previous year: [Youtube]
    • Slides: [Download]
  • Lecture #7, Dec 12, 2023 (Voronoi diagram)
    • Video from previous year: [Youtube]
    • Slides: [Download]
  • Lecture #8, Dec 19, 2023 (Voronoi diagram)
    • Video from previous year: [Youtube]
    • Slides: [Download]
    • Original publications: Fortune's Algorithm
  • Lecture #9, Jan 9, 2024 (Voronoi games)
    • Video from previous year: [Youtube]
    • Slides: [Download]
    • 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 16, 2024 (Polygon triangulation)
    • Video from previous year: [Youtube]
    • Slides: [pdf]
    • Original publications: Robot Triangulation, Chazelle 1991, Clarkson 1989, Garey 1978, Kirkpatrick 1992, Tarjan 1988
  • Lecture #11, Jan 23, 2024 (Point triangulation)
    • Video: [Youtube]
    • Slides: [pdf]
    • Original publications: Delaunay, Triangulations - ETH, MaxMin Angle, MinMax Angle, Mulzer-Rote MWT, Haas MWT, MaxMin Edge Length, MinMax Edge Length
  • Lecture #12, Jan 30, 2022 (Location problems)
    • Video: [Youtube]
    • 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 06, 2023
    • Video: [Youtube]
    • 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

Tutorials

  • Tutorial #1, Nov 16, 2023 (Introduction, Convex Hulls)
    • Slides: [Download]
    • Further references:
      • Point Location Problem (Shamos, 1975) [Download, Problem 4]
  • Homework Sheet #1
    • Due Dec 21, 2023
    • [Download]
  • Tutorial #2, Nov 23, 2023 (Convex Layers, Boolean Operations)
    • Slides: [Download]
    • References:
      • Convex Layers (Chazelle, 1985) [Download]
  • Tutorial #3, Dec 7, 2023 (Moved to IZ305)
    • Slides: [Download]
    • References:
      • Rotating Callipers Algorithm (Shamos, 1975) [Download, Problem 3]
  • Tutorial #4, Dec 21, 2023 (Scissors Congruence, Higher order Voronoi diagram)
    • Slides: [Download]
    • References:
      • Visualizing Scissors Congruence (Devadoss et al., 2016) [Download]
  • Homework Sheet #2
    • Due Feb 1, 2023
    • [Download]
  • Tutorial #5, Jan 11, 2024
    • Slides: [Download]
  • Tutorial #6, Jan 25, 2024 (The Art Gallery Problem)
    • Slides: [Download]
  • Tutorial #7, Feb 22, 2024
    • Exam preparation!
    • Slides: [Download]

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 Peter.


last changed 2024-02-24, 22:57 by Peter Kramer

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
Imprint Privacy Accessibility