Title: Recursive simplex stars,
Abstract: This paper proposes a new method which builds a simplex based approximation
of a $d-1$-dimensional manifold $M$ separating a $d$-dimensional compact set
into two parts, and an efficient algorithm classifying points according to this
approximation. In a first variant, the approximation is made of simplices that
are defined in the cubes of a regular grid covering the compact set, from
boundary points that approximate the intersection between $M$ and the edges of
the cubes. All the simplices defined in a cube share the barycentre of the
boundary points located in the cube and include simplices similarly defined in
cube facets, and so on recursively. In a second variant, the Kuhn triangulation
is used to break the cubes into simplices and the approximation is defined in
these simplices from the boundary points computed on their edges, with the same
principle. Both the approximation in cubes and in simplices define a separating
surface on the whole grid and classifying a point on one side or the other of
this surface requires only a small number (at most $d$) of simple tests. Under
some conditions on the definition of the boundary points and on the reach of
$M$, for both variants the Hausdorff distance between $M$ and its approximation
decreases like $\mathcal{O}(d n_G^{-2})$, where $n_G$ is the number of points
on each axis of the grid. The approximation in cubes requires computing less
boundary points than the approximation in simplices but the latter is always a
manifold and is more accurate for a given value of $n_G$. The paper reports
tests of the method when varying $n_G$ and the dimensionality of the space (up
to 9).