This work generalizes the ideas in the Nearest-Neighbor-Crust algorithm by Dey and Kumar. It allows to reconstruct smooth, closed curves from ε-samples with ε ≤ 0.48. This is a big improvement compared to the original bound. Further generalization leads to a new algorithm which reconstructs closed curves with self-intersections. The algorithm is very simple and short and works well in practice. A special ε-sampling condition is given which guarantees correct results. The described method works for curves in any dimension d in O(n^(2−1/d)) time. \--- In this part the well-known problem of finding the median of an ordered set is studied under a very restrictive streaming model with sequential readonly access to the data. Only a constant number of reference objects from the stream can be stored for comparison with subsequent stream elements. A first non-trivial bound of Omega(√n) distance to the extrema of the set is presented for a single pass over streams which do not reveal their total size n. This result is extended to an algorithm which guarantees a distance of Omega(n^(1−ε)) to the extrema. Additional results about upper bounds, multi-pass algorithms, and arbitrary quantiles are presented.
In diesem Kapitel wird die Idee des Nearest-Neighbor-Crust-Algorithmus von Dey und Kumar verallgemeinert. Das Ergebnis ist ein Algorithmus, der die Rekonstruktion von glatten, geschlossenen Kurven aus einem ε-Sample mit ε ≤ 0, 48 erlaubt. Dies ist eine gravierende Verbesserung gegenüber der Schranke für den unveränderten Algorithmus. Weitere Verallgemeinerung führt zu einem neuen Algorithmus, der geschlossene Kurven mit Selbstschnitten rekonstruieren kann. Der vorgestellte Algorithmus ist sehr einfach und kurz und in der Praxis einsetzbar. Es wird eine spezielle Bedingung für das ε-Sample angegeben, unter der der Algorithmus beweisbar korrekte Ergebnisse liefert. Das Verfahren funktioniert für Kurven in beliebiger Dimension d in O(n^(2−1/d)) Zeit. \--- In diesem Abschnitt wird das bekannte Problem der Mediansuche in einer geordneten Menge untersucht. Dies erfolgt in dem sehr strengen Streaming- Modell, welches nur Lesezugriff auf die Daten erlaubt. Gleichzeitig darf nur eine konstante Anzahl von Referenzobjekten aus dem Datenstrom für Vergleiche gespeichert werden. Die erste nicht-triviale untere Schranke von Omega(√n) für den Abstand zwischen dem gefundenen Wert und den Extremwerten des Datenstroms wird mit einem Single-Pass-Algorithmus erreicht. Dabei ist es nicht erforderlich die Länge n des Datenstroms zu kennen. Dieser Algorithmus bildet den Grundbaustein für ein Approximationsverfahren, welches einen Abstand von Omega(n^(1−ε)) zu den Extremwerten garantiert. Des Weiteren werden obere Schranken, Multi-Pass-Algorithmen und Ansätze für andere Elemente als den Median präsentiert.
