Dissertation : Simple Reconstruction of Non-Simple Curves and Approximating the Median in Streams with Constant Storage

Tobias Lenz

Betreuer: Prof. Dr. Günter Rote

In vielen wissenschaftlichen Gebieten spielt die Visualisierung von Daten eine zunehmende Rolle. Dabei werden Werte an sehr vielen fixen Positionen gemessen, z.B. die Höhe über dem Meeresspiegel für einen bestimmten Landstrich, aus dem Körper austretende elektromagnetische Wellen in einem Kernspinresonanztomographen oder Hitze in einer Brennkammer. Die Daten liegen als Paare von Punkten in einer bestimmten Dimension und den dazugehörigen Messwerten vor und ihre Anzahl kann bei sehr detaillierten Messungen durchaus Größenordnungen von einigen Millionen annehmen.

Derartige Datenmengen können nicht in Echtzeit durchsucht werden, so dass man geeignete Datenstrukturen verwenden muss, um effizient bestimmte Teilmengen zu erhalten. Eine wichtige Teilmenge ist hierbei die Menge aller Punkte, die einen bestimmten Wert haben - so genannte Isolinien bzw. Isoflächen oder auch Konturen.

Untersucht man eine solche Kontur, so stellt sich diese sehr vielgestaltig dar, kann zusammenhängend oder in viele Teile zerlegt sein, Tunnel bilden, Hohlräume einschließen und vieles mehr. Ein Beispiel für eine dreidimensionale Kontur aus einer vierdimensionalen Datenmenge ist auf dem Bild zu sehen. Diese errechnete topologische Struktur liefert in Form der so genannten Betti-Zahlen eine sinnvolle Gruppierung der Objekte.

Bei praktischen Messungen ist immer ein gewisser Fehler enthalten - auch als ``Rauschen'' bekannt. Dieses Rauschen kann bereits empfindlichen Einfluss auf die geschilderten topologischen Eigenschaften der Konturen haben, so dass ein Verfahren benötigt wird, um relevante Eigenschaften zu erkennen und zu extrahieren. Dieses Verfahren wird entwickelt und untersucht. In Experimenten hat sich herausgestellt, dass dieses Verfahren evtl. auch für effiziente Suchanfragen in geometrischen Datenbanken anwendbar ist.