Abstract
Original language  English 

Qualification  Doctor of Philosophy 
Awarding Institution 

Supervisors/Advisors 

Award date  19 Dec 2007 
Place of Publication  Berlin 
Publisher  
Publication status  Published  2007 
Fingerprint
Cite this
}
Organizing point sets : spacefilling curves, Delaunay tessellations of random point sets, and flow complexes. / Buchin, K.
Berlin : Freie Universität Berlin, 2007. 127 p.Research output: Thesis › Phd Thesis 4 Research NOT TU/e / Graduation NOT TU/e)
TY  THES
T1  Organizing point sets : spacefilling curves, Delaunay tessellations of random point sets, and flow complexes
AU  Buchin, K.
PY  2007
Y1  2007
N2  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.
AB  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.
UR  http://www.diss.fuberlin.de/diss/receive/FUDISS_thesis_000000003494
M3  Phd Thesis 4 Research NOT TU/e / Graduation NOT TU/e)
PB  Freie Universität Berlin
CY  Berlin
ER 