In this paper we establish a topological similarity between two apparently different shape constructors from a set of points. Shape constructors are geometric structures that transform finite point sets into continuous shapes. Due to their immense practical importance in geometric modeling various shape constructors have been proposed recently. Understanding the relations among them often leads to new insights that are potentially helpful in applications. Here we discover a topological equivalence among two such geometric structures, namely α shapes and flow shapes. Both shapes found applications in surface reconstruction and molecular modelin.

We present an efficient algorithm that computes a manifold triangular mesh from a set of unorganized sample points in . The algorithm builds on the observation made by several researchers that the Gabriel graph of the sample points provides a good surface description. However, this surface description is only one-dimensional. We associate the edges of the Gabriel graph with index 1 critical points of a dynamical system induced by the sample points. Exploiting also the information contained in the critical points of index 2 provides a two-dimensional surface description which can be easily turned into a manifold.

We present a novel approach to surface reconstruction based on the Delaunay complex. First we give a simple and fast algorithm that picks locally a surface at each vertex. For that, we introduce the concept of /spl lambda/-intervals. It turns out that for smooth regions of the surface this method works very well and at difficult parts of the surface yields an output well-suited for postprocessing. As a postprocessing step we propose a topological clean up and a new technique based on linear programming in order to establish a topologically correct surface. These techniques should be useful also for many other reconstruction schemes.