Abstract. Algorithms for reconstructing a 2-manifold from a point sample
in R3 based on Voronoi-filtering like CRUST or CoCone still require
– after identifying a set of candidate triangles – a so-called
manifold extraction step which identifies a subset of the candidate triangles to form
the final reconstruction surface. Non-locality of the latter step is caused by
so-called slivers – configurations of four almost cocircular points having
an empty circumsphere with center close to the manifold surface.
We prove that under a certain mild condition – local uniformity –
which typically holds in practice but can also be enforced theoretically,
one can compute a reconstruction using an algorithm whose decisions
about the adjacencies of a point only depend on nearby points.
While the theoretical proof requires an extremely high sampling density,
our prototype implementation, described in a companion paper,
performs well on typical sample sets. Due to its local mode of computation,
it might be particularly suited for parallel computing or
external memory scenarios.