**Mentor** Nina Amenta, University of California, Davis

Surface reconstruction is the problem of producing an explicit representation of a surface *S* from an input cloud of points *P* assumed to lie on or near *S*. We use it extensively in 3D to reconstruct the boundary of an object from samples. In higher dimensions, similar ideas may be useful for function estimation. For example, if we expect that *m* hidden factors explain the variation in our *d*-dimensional training data, we would also expect to observe that the training data *P* lies on or near a *m*-dimensional, probably non-linear, surface* S* in R^d. Given enough training data, we might hope to produce an explicit representation of *S* which would model the generation of observations from the hidden factors. This might help us answer queries in which we want to return the function values of query points, for instance by projecting the query to *S* before estimating the function value or by detecting queries that lie so far from the model *S *that they should be classified as outliers. Even if it is not helpful in practice, it might be very useful in theory; for instance, it might help us answer questions such as: What kind of input sampling density is required to give approximately correct answers? What can we do when the training and query noise models are different? What are the inherent limits, either information theoretic or computational, on the kinds of function estimation problems that can be solved?

**Surface Reconstruction**

Voronoi diagrams and Delaunay triangulations have proven to be very useful in two- and three-dimensional surface reconstruction, and there is a line of research towards extending them to higher-dimensional surface reconstruction. In R^3, the idea is the following: Given point sample *P*, we compute its Voronoi diagram and its dual Delaunay triangulation. We can prove that the intersection of *S* with the Voronoi diagram is simple in the following sense: it cuts every Voronoi face nearly transversally, and in a topological ball. This implies [6] that the Delaunay triangulation contains a triangulated surface homeomorphic to *S*, the restricted Delaunay triangulation or RDT. We can also prove that the RDT is close to *S*, but, not knowing *S*, we can’t guarantee that we can find the RDT. This is because if there is a Voronoi vertex very near *S*, it corresponds to a very flat “sliver” tetrahedron in the Delaunay triangulation, providing two possible surfaces, inner and outer, that might belong to the RDT. Choosing either one might be correct. Fortunately, a surface containing either is sufficient to approximate S; so many algorithms generate the set of acceptable candidate triangles and then extract a manifold surface from the candidate set.

Analogous issues complicate the higher-dimensional problem. There, in addition to Voronoi vertices very near *S*, we can also have entire edges, two-faces and so on. If a *k*-face* f* of the Voronoi diagram is nearly tangent to *S*, then the intersection *S*∩ *f* need not be a topological ball; it can be arbitrary, even if the sampling is very dense with respect to the curvature of *S.* So there is no guarantee that the RDT is homeomorphic to *S*; when a Voronoi face appears multiple times in the restricted Voronoi diagram, the dual Delaunay face appears multiple times in the dual RDT; the RDT is “folded up” and does not form a proper manifold.

**Problem 1 - nearby restricted Delaunay triangulation**

The first problem we might consider is whether there is always some nearby surface* S'*, possibly passing through the training points *P*, such that the RDT of* S' *is manifold homeomorphic to *S*. I think I can show that, for the co-dimension one case (m = d −1), we can construct an *S'* such that its (d −1)-simplices are all unique, although its lower-dimensional simplifies might not be. But I conjecture (as did Khoury and Shewchuk in the last ACM SoCG conference - see below) that we can get much further with this approach.

**Problem 2 - manifold extraction**

Assuming there is some simplicial surface approximating *S* in the high-dimensional Delaunay triangulation, is it possible to extract such a surface from the collection of candidate triangles we can find? The methods we use for this problem in 3D do not generalize obviously to higher dimensions.

Here is an idea that might work in higher dimensions. If the *m*-dimensional Delaunay simplifies bound a closed object, the boundary is an *m*-cycle. The set of candidate *m*-simplices forms a matroid, in which the independent sets are those which form no *m*-cycle. The greedy matroid algorithm (generalizing Kruskal’s MST algorithm) adds *m*-simplices one by one unless adding the current simplex would close off an *m*-cycle; it can be implemented pretty easily using matrices over *GF*(2). We can use any weighting function we want to on the simplices, and we are guaranteed that the resulting surface will be minimal weight. We also get a sequence of rejected simplifces, each of which closes off a cycle. We can choose the rejected simplex forming the largest cycle, which we retain, removing any simplicies that do not end us as part of the big *m*-cycle.

The reason this does not obviously work is that it only considers *m*-cycles; as in Problem 1, there is not a priori reason why the boundary of the big *m*-cycle might not fold up onto itself to form (m − 1)- or lower-dimensional cycles.

So the question is, is there a weighting function on the m-simplices which will make the greedy matroid algorithm produce a proper manifold when given a sufficiently dense input sample *P*?

**Prior work**

Cheng, Dey and Ramos [4] solved the high-dimensional surface reconstruction problem in theory by com- puting the Voronoi diagram of *P* and actually computing the *k*-dimensional restricted Voronoi diagram. For very dense samples, *S* is nearly planar in the neighborhood of any sample *p*. They use “sliver exudation” - a method in which we add a small perturbation to the triangulation by weighting the input samples [3] - to ensure that any face of dimension *d* − *k* or greater of the Voronoi diagram of *P* in the neighborhood of *S *intersects *S* transversally. As a result, *S* slices each of these faces in a topological ball, and the RDT is a triangulated manifold homeomorphic to *S*. In fact, they show that for dense enough sampling, once slivers are eliminated, these are the only *k*-simplicies with normal close enough to that of *S*, so they can (in theory) output this manifold. This algorithm is not practical, because the sampling has to be very dense, because it computes a high-dimensional Voronoi diagram (which has complexity possibly as great as n^[d/2]) and because the weights assigned to the samples have to be delicately balanced to eliminate all slivers.

Oudot and Boissonnat [2] addressed the issue of Voronoi diagram computation using the witness complex [5], a sampled version of the RDT in which a dense set of *W* samples on *S* is used as a representation of the surface, and an *m*-simplex *f* of the Delaunay triangulation of the sparser sampling *P* is included as a candidate if there is at least one sample in *W* whose *m*+1 nearest neighbors are the vertices of *f*. Again, silver exudation is used to ensure that the witness complex contains a triangulation of *S*, by improving the quality of the RDT. This paper is admirable for its negative results; it gives a concrete example, in Section 3, of a three-dimensional RDT in R^4 that gets folded up, building on an example from [4], and examples in which the witness complex of a finite point sample from* S* is neither contained in, nor contains, the RDT (although it is contained in the Delaunay triangulation).

Boissonnat and Ghosh [1] developed another theoretical method, with running time exponential in the dimension *k* rather than *d*/2, avoiding computation of the Voronoi diagram in a more practical way. They construct a local triangulation for each sample *p* in a projection of the nearby points of *P* to a *k*-dimensional estimated tangent plane at *p*. The main insight is that when a simplex appears in a local triangulation at one of its vertices but not another, this corresponds to a silver in the full-dimensional Delaunay triangulation. Again, they remove the offending silvers through silver exudation, producing a consistent triangulation.

Khoury and Shewchuk [7] recently gave an algorithm for computing a triangulation which is its own restricted Delaunay triangulation, by starting with a close-enough triangulation, constructing its restricted Delaunay triangulation, and iterating. For k = 2, they show that the fixed-point of this operation is a set of triangles that includes a piecewise-linear manifold homeomorphic to *S*. In R^3 this manifold can be extracted, while they conjecture that manifold extraction is difficult, perhaps NP-complete, in higher dimensions.

**Possible experimental work**

We can experiment with possible weighting functions for Problem 2, using two-dimensional point sets in R^3 and then moving up in dimension. We can compute Voronoi diagrams reliably, so that part is fairly easy. I can work on making a point-cloud generator for some synthetic cases in, say, dimensions four or five.

**References**

[1] Jean-Daniel Boissonnat and Arijit Ghosh. Manifold reconstruction using tangential delaunay com- plexes. Discrete & Computational Geometry, 51(1):221–267, 2014.

[2] Jean-Daniel Boissonnat, Leonidas J Guibas, and Steve Y Oudot. Manifold reconstruction in arbitrary dimensions using witness complexes. Discrete & Computational Geometry, 42(1):37–70, 2009.

[3] Siu-Wing Cheng, Tamal K Dey, Herbert Edelsbrunner, Michael A Facello, and Shang-Hua Teng. Silver exudation. Journal of the ACM (JACM), 47(5):883–904, 2000.

[4] Siu-Wing Cheng, Tamal K Dey, and Edgar A Ramos. Manifold reconstruction from point samples. In SODA, volume 5, pages 1018–1027, 2005.

[5] Vin De Silva and Gunnar Carlsson. Topological estimation using witness complexes. Proc. Sympos. Point-Based Graphics, pages 157–166, 2004.

[6] Herbert Edelsbrunner and Nimish R Shah. Triangulating topological spaces. In Proceedings of the tenth annual symposium on Computational geometry, pages 285–292. ACM, 1994.

[7] Marc Khoury and Jonathan Richard Shewchuk. Fixed points of the restricted Delaunay triangulation operator. In Symposium on Computational Geometry, 2016. SoCG 2016., pages 1–15. ACM, June 2016.