# Geometric Data Structures

(in German: Geometric Data Structures - )

<table bgcolor="#7FB3D9" border="1" id="bkmrk-%5Btitle%5D" style="width: 100%; border-collapse: collapse; border-width: 1px; border-style: none;"><colgroup><col style="width: 100%;"></col></colgroup><tbody><tr style="background-color: rgb(235, 243, 249);"><td>##### <span style="color: rgb(0, 104, 180);">**Module-ID:** </span><span style="color: rgb(0, 104, 180);">**FIN-INF-102206**</span>

</td></tr></tbody></table>

<table border="1" id="bkmrk-verantwortung%3A-verwe" style="border-collapse: collapse; width: 100%; height: 124.8px; border-width: 1px; border-style: none;"><colgroup><col style="width: 24.7879%;"></col><col style="width: 75.2121%;"></col></colgroup><tbody><tr style="height: 35.4px;"><td style="height: 35.4px;">**Link:**</td><td style="height: 35.4px;">[LSF](https://lsf.ovgu.de/qislsf/rds?state=wsearchv&search=1&subdir=veranstaltung&veranstaltung.semester=20251&veranstaltung.dtxt=Geometric+Data+Structures&P_start=0&P_anzahl=30&P.sort=veranstaltung.dtxt&_form=display "Geometric Data Structures")</td></tr><tr style="height: 29.8px;"><td style="height: 29.8px;">**Responsibility:**</td><td style="height: 29.8px;">Prof. Dr. Stefan Schirra</td></tr><tr style="height: 29.8px;"><td style="height: 29.8px;">**Lecturer:**</td><td style="height: 29.8px;">Prof. Dr. Stefan Schirra</td></tr><tr><td>**Classes:**</td><td>- Lecture *Geometric Data Structures*
- Exercises *Geometric Data Structures*

 </td></tr><tr style="height: 29.8px;"><td style="height: 29.8px;">**Applicability in curriculum:**</td><td style="height: 29.8px;">  
</td></tr></tbody></table>

<table bgcolor="#7FB3D9" border="1" id="bkmrk-" style="border-collapse: collapse; width: 100%;"><colgroup><col style="width: 14.2515%;"></col><col style="width: 14.2515%;"></col><col style="width: 13.061%;"></col><col style="width: 15.442%;"></col><col style="width: 14.2515%;"></col><col style="width: 14.2515%;"></col><col style="width: 14.2515%;"></col></colgroup><tbody><tr><td class="align-center" style="border: 5px solid rgb(255, 255, 255);"><span style="color: rgb(61, 61, 61);">**Abbreviation**</span>

<span style="color: rgb(61, 61, 61);">GeomDS</span>

</td><td class="align-center" style="border: 5px solid rgb(255, 255, 255);"><span style="color: rgb(61, 61, 61);">**Credit Points**</span>

<span style="color: rgb(61, 61, 61);">6</span>

</td><td class="align-center" style="border: 5px solid rgb(255, 255, 255);"><span style="color: rgb(61, 61, 61);">**Semester**</span>

<span style="color: rgb(61, 61, 61);">Summer</span>

</td><td class="align-center" style="border: 5px solid rgb(255, 255, 255);"><span style="color: rgb(61, 61, 61);">**Term**</span>

<span style="color: #3d3d3d;">ab 1.</span>

</td><td class="align-center" style="border: 5px solid rgb(255, 255, 255);">**<span style="color: rgb(61, 61, 61);">Duration</span>**

<span style="color: rgb(61, 61, 61);">1 Semester</span>

</td><td class="align-center" style="border: 5px solid rgb(255, 255, 255);"><span style="color: rgb(61, 61, 61);">**Language**</span>

<span style="color: rgb(61, 61, 61);">english</span>

</td><td class="align-center" style="border: 5px solid rgb(255, 255, 255);"><span style="color: rgb(61, 61, 61);">**Level**</span>

<span style="color: rgb(61, 61, 61);">Master</span>

</td></tr></tbody></table>

**Intended learning outcomes:** Students learn how to design, analyze and apply data structures for geometric problems.

**Content:**

- heap data structures,
- balanced binary search trees,
- self-organizing data structures,
- amortized analysis,
- interval, range and segment trees,
- augmented data structures,
- quad-trees,
- fractional cascading,
- point location data structures,
- persistent data structures,
- making data structures dynamic.

**Workload:** 56h in presence + 124h self-study

<table border="1" id="bkmrk-studien-%2Fpr%C3%BCfungslei" style="border-collapse: collapse; width: 100%;"><colgroup><col style="width: 50%;"></col><col style="width: 50%;"></col></colgroup><tbody><tr><td>**Type of examination:**</td><td>**Teaching method / lecture hours per week (SWS):**</td></tr><tr><td>oral exam

</td><td>- Lecture (3SWS)
- Exercises (1SWS)

</td></tr></tbody></table>

<table border="1" id="bkmrk-voraussetzungen-nach" style="font-family: var(--font-body); font-size: 14px; width: 100%;"><colgroup><col style="width: 50%;"></col><col style="width: 50%;"></col></colgroup><tbody><tr><td>**Prerequisites according to examination regulations:**</td><td>**Recommended prerequisites:**</td></tr><tr><td>keine

</td><td>Basics in algorithmics

</td></tr></tbody></table>

<table border="1" id="bkmrk-medienformen%3A-litera" style="border-collapse: collapse; width: 100%;"><colgroup><col style="width: 50%;"></col><col style="width: 50%;"></col></colgroup><tbody><tr><td>**Media:**</td><td>**Literature:**</td></tr><tr><td></td><td>- Samet: Foundations of Multidimensional and Metric Data Structures.
- Zachmann, Langetepe: Geometric Data Structures for Computer Graphics.
- Mehta, Sahmi: Handbook of Data Structures and Applications
- Morin: Open Data Structures: An Introduction

  
</td></tr></tbody></table>

**Comments:**