DANIEL FREEDMAN

A new algorithm is presented for surface reconstruction from unorganized points. Unlike many existing methods, this algorithm does not select a subcomplex of the Delaunay Triangulation of the points. Instead, it uses an incremental technique, adding one triangle of the surface at a time. As a result, the algorithm does not require the surface’s embedding space to be R^3; the dimension of the embedding space may vary arbitrarily without substantially affecting the complexity of the algorithm. A wider variety of surfaces may therefore be reconstructed, including the class of non-orientable surfaces, such as the Klein Bottle. The algorithm is of an experimental character; while it is motivated from geometric and topological intuition, no proofs of homeomorphism are given. Instead, its efficacy is demonstrated from the point of view of correct experimental reconstruction of surfaces of varying genus.