Samenvatting
In this thesis we develop and analyze algorithms for computing spacelling
curve orders, Delaunay tessellations and
ow complexes of point sets. For
spacelling curve orders and Delaunay tessellations the emphasis lies on an
averagecase analysis of the algorithms. For
ow complexes the emphasis lies
on their computation in higher dimensions.
In a spacelling curve order of a point set, points which are close in the order
are also close in space. We discuss algorithms for computing spacelling curve
orders based on radix sort. We give an averagecase analysis which shows that
these orders can be computed in linear expected time for many point distributions.
As discrete counterparts of spacelling curves we consider grid traversals
and discuss nding optimal grid traversals for dierent 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 spacelling curve orders. First we give a generalized
and rened analysis of incremental constructions con BRIO, i.e., where points
are inserted in random rounds. Based on this we analyze incremental constructions
along spacelling 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 dcube in higher dimensions. In the
rst case we analyze the expected structure of the Delaunay tessellation and
in the other cases the structure of the spacelling curve order. We show for
these point distributions that incremental constructions con BRIO of Delaunay
tessellations run in linear expected time using spacelling curve orders.
The
ow complex of a point set is the collection of stable manifolds of the
ow induced by the distance function of the point set. We give an algorithm
for computing the
ow 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
ow. Based on this algorithm we give a topological
analysis of
ow shapes, i.e., the underlying spaces of subcomplexes of the
ow
complex. In particular we show that
ow shapes are homotopy equivalent to
the corresponding unions of balls.
Originele taal2  Engels 

Kwalificatie  Doctor in de Filosofie 
Toekennende instantie 

Begeleider(s)/adviseur 

Datum van toekenning  19 dec 2007 
Plaats van publicatie  Berlin 
Uitgever  
Status  Gepubliceerd  2007 
Vingerafdruk Duik in de onderzoeksthema's van 'Organizing point sets : spacefilling curves, Delaunay tessellations of random point sets, and flow complexes'. Samen vormen ze een unieke vingerafdruk.
Citeer dit
Buchin, K. (2007). Organizing point sets : spacefilling curves, Delaunay tessellations of random point sets, and flow complexes. Freie Universität Berlin.