Objekt-Metadaten

Organizing Point Sets
Buchin, Kevin

HaupttitelOrganizing Point Sets
TitelzusatzSpace-Filling Curves, Delaunay Tessellations of Random Point Sets, and Flow Complexes
TitelvarianteStrukturieren von Punktmengen
Zusatz zur TitelvarianteRaumfüllende Kurven, Delaunay-Triangulierungen von zufälligen Punktmengen und Flusskomplexe
AutorBuchin, Kevin
Geburtsort: Bochum, Deutschland
GutachterProf. Dr. Günter Rothe
weitere GutachterProf. Dr. Robert L. Scot Drysdale
Freie SchlagwörterComputational Geometry, Probabilistic Analysis, Delaunay Triangulations, Space-Filling Curves, Flow ComplexesF.2.268Q25
DDC004 Datenverarbeitung; Informatik
ZusammenfassungIn this thesis we develop and analyze algorithms for computing space-filling curve orders, Delaunay Tessellations and flow complexes of point sets. For space-filling curve orders and Delaunay Tessellations the emphasis lies on an average-case analysis of the algorithms. For flow complexes the emphasis lies on their computation in higher dimensions. In a space-filling curve order of a point set, points which are close in the order are also close in space. We discuss algorithms for computing space-filling curve orders based on radix sort. We give an average-case analysis which shows that these orders can be computed in linear expected time for many point distributions. As discrete counterparts of space-filling curves we consider grid traversals and discuss finding optimal grid traversals for different locality measures using heuristics for the quadratic assignment problem. The Delaunay Tessellation of a point set is a simplicial complex capturing proximity relations of the points. We analyze incremental constructions of Delaunay Tessellations along space-filling curve orders. First we give a generalized and refined analysis of incremental constructions con BRIO, i.e., where points are inserted in random rounds. Based on this we analyze incremental constructions along space-filling curve orders for uniformly distributed points from a bounded convex region in the plane, normally distributed points in the plane, and uniformly distributed points from a d-cube in higher dimensions. In the first case we analyze the expected structure of the Delaunay Tessellation and in the other cases the structure of the space-filling curve order. We show for these point distributions that incremental constructions con BRIO of Delaunay Tessellations run in linear expected time using space-filling curve orders. The flow complex of a point set is the collection of stable manifolds of the flow induced by the distance function of the point set. We give an algorithm for computing the flow complex in higher dimensions. The algorithm is based on the Delaunay Tessellation and Voronoi Diagram of the point set and the recursive nature of the flow. Based on this algorithm we give a topological analysis of flow shapes, i.e., the underlying spaces of subcomplexes of the flow complex. In particular we show that flow shapes are homotopy equivalent to the corresponding unions of balls.
Dokumente
FUDISS_derivate_000000003494
Falls Ihr Browser eine Datei nicht öffnen kann, die Datei zuerst herunterladen und dann öffnen.
 
Fachbereich/EinrichtungFB Mathematik und Informatik
Erscheinungsjahr2008
Dokumententyp/-SammlungenDissertation
Medientyp/FormatText
SpracheEnglisch
RechteNutzungsbedingungen
Tag der Disputation19.12.2007
Erstellt am12.02.2008 - 00:00:00
Letzte Änderung19.02.2010 - 11:17:28
 
Alte Darwin URLhttp://www.diss.fu-berlin.de/2008/118/
Statische URLhttp://www.diss.fu-berlin.de/diss/receive/FUDISS_thesis_000000003494
URNurn:nbn:de:kobv:188-fudissthesis000000003494-8
Zugriffsstatistik