ABSTRACT:

The mesh generation problem in its simplest form is to construct a superset of an input set of points, such that the superset has good geometry, in particular so the vertices are well-spaced. Existing algorithms can achieve an $O(1)$-minimal size superset with efficient runtime.

One can extend the notion of conforming beyond simply taking a superset; additionally conforming to input edges and facets that form a piecewise linear complex. Such a construction does not exist unless we relax the well-spacing condition around acute angles between inputs.

This relaxation destroys known lower-bounds, so that $O(1)$-minimality can no longer be guaranteed, but some weak analyses on size exist.

I will present the first runtime-efficient algorithm for this problem in 3d, with worst-case runtime O(N log D + M), where N is the input size, D is the aspect ratio of the input (diameter to closest pair ratio), and M is the output size.