dc.contributor.author
Lenz, Tobias
dc.date.accessioned
2018-06-07T19:14:51Z
dc.date.available
2008-11-24T07:46:11.935Z
dc.identifier.uri
https://refubium.fu-berlin.de/handle/fub188/5905
dc.identifier.uri
http://dx.doi.org/10.17169/refubium-10104
dc.description.abstract
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.
de
dc.description.abstract
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.
de
dc.rights.uri
http://www.fu-berlin.de/sites/refubium/rechtliches/Nutzungsbedingungen
dc.subject
reconstruction
dc.subject.ddc
000 Informatik, Informationswissenschaft, allgemeine Werke
dc.title
Simple reconstruction of non-simple curves and approximating the median in
streams with constant storage
dc.contributor.contact
tlenz@mi.fu-berlin.de
dc.contributor.firstReferee
Rote, Günter
dc.contributor.furtherReferee
Funke, Stefan
dc.date.accepted
2008-10-28
dc.identifier.urn
urn:nbn:de:kobv:188-fudissthesis000000006179-1
dc.title.translated
Einfache Rekonstruktion nicht-einfacher Kurven und Approximation des Medians
in Datenströmen mit konstantem Speicher
de
refubium.affiliation
Mathematik und Informatik
de
refubium.mycore.fudocsId
FUDISS_thesis_000000006179
refubium.mycore.derivateId
FUDISS_derivate_000000004689
dcterms.accessRights.dnb
free
dcterms.accessRights.openaire
open access