Recursive simplex stars
Guillaume Deffuant
cs.CG









Irstea - LISC, 9 avenue Blaise Pascal 63178 Aubière, France





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 the surface to approximate, for both variants the Hausdorff distance between M and its approximation decreases like 𝒪(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). 



classification marching cubes simplex star


Recursive simplex stars
    Guillaume Deffuant
    January 15, 2018
=======================





bigskip





§ INTRODUCTION.


This paper addresses the following problems: 

	
  * How to approximate a d-1-dimensional manifold M separating a d-dimensional compact set X into two parts (one labelled -1, the other +1), using as efficiently as possible an oracle which, to any point of X, provides the value stating on which part of X the point is located ? 
	
  * How to define an efficient algorithm computing the classification of a point by the approximate separation ?


The main motivation is to improve algorithms derived from Viability Theory <cit.>. This theory, which provides methods and tools for maintaining a dynamical system within a constraint set, is used in many fields such as sustainability management <cit.>, economics <cit.> or food processing <cit.>. The main algorithms derived from Viability Theory <cit.> iterate the computation of approximate classification functions using the vertices of a grid labelled into two classes. The approximate classification methods currently used are the nearest vertex of the grid <cit.> or machine learning techniques such as support vector machines <cit.> or k-d trees <cit.>. Our main purpose is to develop a more efficient method. 

Nevertheless, deriving efficient approximate classification can be useful in other contexts. For instance, when a classification requires a heavy or difficult process, it is often interesting to compute an approximate but lighter classification function, based on a limited set of well chosen classified points. This problem is a particular case of meta (or surrogate) modelling. The field of reliability in material sciences for instance develops specific techniques to build such meta-models <cit.>. 

A problem closely related to the approximation of a classification boundary is the approximation of an isosurface, defined as the set of points such that f(x)=0, f being a continuous function from the considered space into ℝ. In this problem, it is possible to define local linear approximations of f around the values f(v) of the vertices v of the grid, which is not possible in the approximation of a classification boundary because the values at the vertices are either -1 or +1.

In 3 dimensions, the problem of approximating an isosurface is very common, for instance to visualise surfaces from scanners or magnetic resonance imaging measurements, and several techniques are available. In particular, the algorithms deriving from the marching cubes <cit.> (see <cit.> for a review) build simplex-based surfaces. They firstly compute the boundary points approximating the intersections between the isosurface and the edges of a regular grid, generally using a linear interpolation. Then the marching cubes generally use a table of rules specifying the connections between boundary points to define a simplex based separating surface in each cube configuration. Once solved the problems of consistency between cubes <cit.>, these techniques represent efficiently the surface of 3D objects. Some variants include an adaptive refinement of the grid in order to guarantee that the approximation is isotopic with the surface to approximate <cit.>. 

However, extending these methods to spaces of more than 3 dimensions faces serious difficulties as the number of cube configurations is in 2^2^d, which leads to a very high number of rules specifying the simplices by cube configuration. For instance in 6 dimensions, there are 2^64 cube configurations which is beyond any current computer storage capacities. Moreover, the number of simplices grows exponentially with the dimensionality and so does the necessary memory space to store them. Currently, as far as we know, the available methods of marching cubes in arbitrary dimensionality are:

	
  * Breaking cubes into simplices <cit.>. This addresses the problem of the fast growth of the table of rules mentioned earlier, because the number of configurations in a simplex is much lower (it varies as d+1/2) than in a cube. However, a d-dimensional cube breaks into between d! or 2^d-1d! simplices, depending on the decomposition used <cit.>. The cited papers show examples in at most 4 dimensions.
	
  * Defining the simplices in a cube from the convex hull of a set of points including the boundary points and some cube vertices <cit.>. The simplices are defined with a single rule but computing the convex hull and storing the corresponding simplices is computationally demanding when d increases. Again, <cit.> shows only examples up to 4 dimensions.


A different approach builds on the principles of Delaunay triangulation and defines simplex based surfaces approximating a manifold without using a grid, from a sampling of points on this manifold. In addition to practical algorithms, the researchers studied the topological and geometric closeness between the approximation and the manifold <cit.>. Moreover, some variants are based on iterative sampling <cit.> adapting the density of the sampling to the local complexity of the shape. Recent variants of the approach <cit.> approximate smooth manifolds of any dimensionality. However, the time complexity of the algorithm is exponential in d'^2 where d' is the dimensionality of the manifold to approximate, which makes it difficult to apply practically even for moderate values of d' (say d' > 5). The memory size needed to store the set of simplices also grows significantly with the dimensionality.

Moreover, none of these approaches considers the problem of using these approximations for a classification purpose. Indeed, when the number of simplices is very large, as expected when the dimensionality increases, computing the classification is also expected to become very demanding. Solving viability problems requires classifying large numbers of points, hence the efficiency of this procedure is crucial in this context. A specificity of this paper is precisely to propose an efficient classification algorithm adapted to specific structures of simplices.

The method proposed in this paper uses a regular grid like the marching cubes and generalises the method of centroids <cit.> to an arbitrary dimensionality. Like the dual marching cubes <cit.> it adds new points in cubes and faces. A noticeable difference with the standard marching cubes is that the boundary points cannot be approximated linearly and successive dichotomies are used instead. 

In a first variant of the proposed method, the simplices are defined in cubes of the grid, from the boundary points located on their edges. All simplices share the barycentre of the cube boundary points as a common vertex (thus shaping a "simplex star") and include simplices of lower dimensionality similarly defined in cube facets. The recursion ends when the considered face is an edge of the cube containing a boundary point. 

This method can be related to the barycentric subdivision which divides an arbitrary convex polytope into simplices sharing the barycentre of the polytope's vertices and this operation can be recursively applied to the faces of the polytope. The main difference is that the simplices of the proposed method are defined in the faces of the cube in which the boundary points are located, not in the faces of the polytope that they define.

In the proposed approach, there is only one rule deriving the simplices in a cube (or a face) whatever the dimensionality. The simplices can easily be enumerated, going through all the faces of a cube. However, when there are 2D faces including 4 boundary points, this method "glues" together surfaces that should remain separated. This creates a non-manifold approximation which should be avoided in many applications. 

The second variant of the method addresses this problem. It uses the Kuhn triangulation to break the cubes into simplices like in <cit.>. The boundary points are computed on the edges of these simplices and the approximation is defined as previously from these boundary points, using the faces of a simplex instead of the faces of a cube. This variant always defines a manifold.

The paper underlines the following properties of both variants:


  * It is possible to compute the classification of a point with at most d relatively simple operations; 


  * Under some conditions on the computation of the boundary points and on the smoothness of M, the Hausdorff distance between M and its approximation decreases like 𝒪(dn_G^-2), n_G being the number of points on each axis of the grid.  



The remaining of the paper is organised as follows: Section 2 presents the variant of the approximation defined in cubes of the grid and its classification algorithm, section 3 does the same for the variant defined in the Kuhn simplices of the grid, section 4 establishes the theorem about the approximation accuracy, section 5 reports the results of a series of tests of the method when varying the space dimensionality and the size of the grid and finally section 6 discusses these results and potential extensions. 





§ MANIFOLD APPROXIMATION WITH RESISTARS IN CUBES.



Let M be a d-1-dimensional manifold separating the compact set X = [0, 1]^d into two parts (one labelled -1 the other +1) and let ℳ: X →{-1, 0, +1}, the function which outputs 0 if x belongs to M and otherwise the label of the part of X in which x is located.  

We consider a regular grid G of n_G^d points covering X and its boundary. The distance between two adjacent points of the grid is ϵ = 1/n_G-1. The cubes of the grid are d-dimensional cubes of edge size ϵ whose vertices are points of the grid. The faces of the grid are the faces of these cubes (cubic polytopes of dimensionality lower than d, of edge size ϵ and whose vertices are points of the grid).

 It is supposed that none of the grid points belongs to M. The function ℳ is slightly modified if necessary in order to ensure this, as it is done in the marching cube approach.

The following notations are frequently used:


  * The set of the i-dimensional faces of a grid cube or a face C is denoted ℱ_i(C);

  * For any polytope P, 𝒱(P) denotes the vertices of P; 

  * For a set S of points of X, S̅ denotes the barycentre of S, [S] the convex hull of S and ∂ S the boundary of S; 

  * For two sets A and B such that B ⊂ A, A - B is the complementary of B in A.


The next subsection focuses on the approximation in a single cube of the grid and the following subsection is devoted to the approximation on the whole grid.




 §.§ c-resistar in a single cube.





  §.§.§ Boundary points.



The method requires first to define the boundary points in the cube.


Let C be a d-dimensional cube of the grid and n_e ≥ 1 be an integer. A boundary point b_M([v_-,v_+]) is defined on an edge [v_-,v_+] of C such that ℳ(v_-) = -1 and ℳ(v_+)=+1, as follows:

    b_M([v_-,v_+]) = v_- + i+0.5/n_e(v_+ - v_-),

Where i ∈{0,..,n_e-1} is such that:

    ℳ(v_- + i/n_e(v_+ - v_-)) = -1, ℳ(v_- + i+1/n_e(v_+ - v_-)) = +1.



In practice, the boundary points are determined by q successive dichotomies with algorithm <ref>, and n_e = 2^q. Because ℳ(v_-) = -1 and ℳ(v_+)=+1, M cuts the edge [v_-,v_+] at least once, therefore b_M([v_-,v_+]) exists and there exists b ∈ M ∩ [v_-,v_+] such that:

    b - b_M([v_-,v_+])≤v_+ - v_-/2 n_e = 2^-q -1ϵ.


If the manifold M cuts the edge an odd number of times, this algorithm returns a boundary point which is close to one of the intersection points. Of course, if there is an even number of intersections, no boundary point is computed because the classification of the vertices by ℳ is the same. As shown in section 4, under some conditions, it is possible to guarantee the accuracy of the approximation, despite the possibility of these situations.




For any face or cube F, we denote B_M(F) the set of boundary points defined on the edges of F. 
For a boundary point b ∈ [v_-, v_+], such that ℳ(v_+) = +1 and ℳ(v_-) = -1, v_+ is denoted v_+(b) (resp. v_- is denoted v_-(b)) and called the positive (resp. negative) vertex of b.




  §.§.§ Definition and main properties of c-resistars.





Let C be a d-dimensional cube of the grid such that B = B_M(C) ≠∅. The c-resistar approximation of M in C, denoted [B]^⋆, is the following set of simplices:
	

	
	
	
	
	
	
	


    [B]^⋆ =  ⋃_{F_1,...,F_d-1}∈ℱ^⋆(B,C)[{B̅_M(F_1),...,B̅_M(F_d-1}∪{B̅} ],

with:

    {F_1,...,F_d-1}∈ℱ^⋆(B,C) ⇔
    	F_1 ∈ℱ_1(C),	B_M(F_1) ≠∅,
    
    	F_i ∈ℱ_i(C), F_i-1⊂ F_i, 2 ≤ i ≤ d-1.
    	,

where i is an integer.



 

 

The word resistar stands for "recursive simplex star". Indeed, the barycentre B̅ of the boundary points is a vertex common to all the simplices which organises them as a star. This star is recursive because the common vertex B̅ is connected to simplices of lower dimensionality in the facets (faces of dimensionality d-1) of C that share the barycentre B̅_M(F_d-1) of the boundary points located in this facet, and so on recursively until reaching an edge F_1 of C which include a boundary point (see examples on Figures <ref> and <ref>). We use the denomination c-resistar, with the prefix "c" standing for cube, in order to distinguish these resistars from the ones which are defined in Kuhn simplices, presented in section 3. 

Propositions <ref> and <ref> establish that the c-resistar is a d-1-dimensional surface without boundary inside the cube C.


For all { F_1, ..., F_d-1}∈ℱ^⋆(B,C), the set [{B̅_M(F_1),..., B̅_M(F_d-1) }∪{B̅}] is a d-1-dimensional simplex.



Proof.
Consider  { F_1, ..., F_d-1}∈ℱ^⋆(B,C). Setting F_d = C, we will show that, for 1 ≤ i ≤ d-1:

    ∃ b_i+1∈ B_M(F_i+1), b_i+1∉ B_M(F_i).


Let F'_i ∈ℱ_i(C) be the face opposite to F_i in F_i+1. F'_i is such that 𝒱(F_i) ∪𝒱(F'_i) = 𝒱(F_i+1) (𝒱(F) being the set of vertices of face F). Two cases occur:

	
  * There are edges [v,v'] of F'_i such that ℳ(v).ℳ(v') = -1, then, for each of these edges, there is a boundary point of F_i+1 which is not in F_i;
	
  * All the vertices of F'_i have the same classification by ℳ. By hypothesis, B_M(F_i) ≠∅, thus there are vertices classified differently by ℳ in F_i, hence there are vertices v such that ℳ(v) ≠ℳ(v'), for  v' vertex of F'_i. There are such couples (v, v'), for which [v,v'] is an edge of F_i+1, thus there is a boundary point b_i+1∈ [v,v'] such that b_i+1∈ B_M(F_i+1) and b_i+1∉ F_i.  

Therefore, for 1 ≤ i ≤ d-1, B̅_M(F_i+1) ∉ F_i. Let S = {B̅_M(F_1),..., B̅_M(F_d-1) }∪{B̅}. The set S includes d affinely independent points, therefore [S] is a d-1-dimensional simplex.
□ 


The boundary of the c-resistar [B]^⋆ is included in the boundary of C.



Proof.
Let S = {B̅_M(F_1),..., B̅_M(F_d-1) }∪{B̅}, with { F_1, ..., F_d-1}∈ℱ^⋆(B,C). [S] is a simplex of [B]^⋆. Consider a facet [S_F] of this simplex, with S_F = S - { p }, p ∈ S. The following cases arise:

	
  * p = B̅. By definition of [B]^⋆, S_F is included in the facet F_d-1 of C, thus [S_F] is included in the boundary of C;
	
  * p = B̅_M(F_i), 2 ≤ i ≤ d-1. Assume that vectors {u_1,...,u_i-1} are a basis F_i-1, vectors {u_1,...,u_i-1, u_i} a basis of F_i and vectors {u_1,...,u_i-1, u_i, u_i+1} a basis of F_i+1, then let F'_i ∈ℱ(C) be such that vectors {u_1,...,u_i-1, u_i+1} are a basis of F'_i and F_i-1⊂ F'_i. We have: F'_i ≠ F_i and F'_i ⊂ F_i+1, thus the set S' = S_F ∪{B̅_M(F'_i) } is such that [S'] is a d-1-dimensional simplex of [B]^⋆ and [S_F] = [S] ∩ [S'];
	
  * p = B̅_M(F_1) = b ∈ B. There exists b' ∈ B such that b' ∈ F_2 and b' ≠ b (using the proof of proposition <ref>). Let F'_1 be the edge of C such that b' ∈ F'_1. We have {F'_1, F_2, ..., F_d-1}∈ℱ^⋆(B,C). Hence S' = {B̅_M(F'_1) }∪ S_F is such that [S'] is a d-1-dimensional simplex of [B]^⋆ and [S_F] = [S] ∩ [S'].

Finally, each simplex of [B]^⋆ has one of its facets which is included in ∂ C the boundary of C and shares all its other facets with other simplices of [B]^⋆. Therefore the boundary of [B]^⋆ is included in ∂ C.
□  


In 2 dimensions (see examples on Figure <ref>), the simplices of the c-resistar are segments [b, B̅], therefore, the number of simplices equals the number of boundary points. 

In 3 dimensions (see an example on Figure <ref>), the simplices are triangles [b, B̅_M(F_2), B̅], where F_2 is a 2D face of the cube including boundary point b. For each boundary point, there are two such faces, therefore, the number of simplices is twice the number of boundary points.

More generally, for 2 ≤ i ≤ d-1, there are d - i +1 faces of dimensionality i including a face of dimensionality i-1, therefore, the number of simplices in a d-dimensional cube is (d-1)! times its number of boundary points. The number of simplices increases thus very rapidly with the dimensionality. However, this is not a problem in our perspective because, as shown further, it is possible to compute efficiently the classification of a point by a c-resistar without considering the simplices explicitly.



  §.§.§ Classification function.



Propositions <ref> and <ref> imply that the c-resistar is a d-1-dimensional set dividing the cube C into several connected sets that we call classification sets. Definition <ref> expresses these sets as the union of polytopes sharing vertices with faces of C and with the simplices of [B]^⋆. The following propositions establish their properties. Finally these sets are used to define the resistar classification function.




Let C be a d-dimensional cube of the grid, such that B = B_M(C) ≠∅. Let ℱ(C) be the set of all the faces of cube C (including C itself) and ℋ(B, C) be the set of the faces of C without boundary points:

    ℋ(B,C) = { F ∈ℱ(C), B_M(F) = ∅}.


Let 𝒟(B,C) be the set of connected components of ℋ(B,C).

For all D ∈𝒟(B,C), the classification set [B]^𝒟⋆(D) associated to D by resistar [B]^⋆ in C, is defined as follows:
	
    [B]^𝒟⋆(D) =  ⋃_{ F_h,..,F_d-1}∈ℱ^𝒟⋆(D,C) [𝒱(F_h) ∪{B̅_M(F_h+1),...,B̅_M(F_d-1) }∪{B̅}],

	with:
	
    { F_h,..,F_d-1}∈ℱ^𝒟⋆(D,C) ⇔
    	F_h ∈ℱ_h(C), F_h ⊂ D, 0 ≤ h ≤ d-1, 
    
    	F_i ∈ℱ_i(C), F_i-1⊂ F_i, h+1 ≤ i ≤ d-1,
    
    	B_M(F_h+1) ≠∅,

where i and h are integers, 𝒱(F_h) is the set of vertices of face F_h. 



 

Figure <ref> shows examples of c-resistar classification sets in 2D. 



For all D ∈𝒟(B,C), D ⊂ [B]^𝒟⋆(D), [B]^𝒟⋆(D) is a d-dimensional connected set and [B]^𝒟⋆(D) ∩ ([B]^⋆ - ∂ [B]^⋆) is the boundary of [B]^𝒟⋆(D) in C - ∂ C.




Proof. Obviously, D ⊂ [B]^𝒟⋆(D), by definition. Indeed, for any face F_h ∈ℱ_h(C), such that F_h ⊂ D, we have [𝒱(F_h)] = F_h ⊂ [B]^𝒟⋆(D) directly from the definition of [B]^𝒟⋆(D).

Let P = 𝒱(F_h) ∪{B̅_M(F_h+1),...,B̅_M(F_d-1) }∪{B̅}, with { F_h, ...,F_d-1}∈ℱ^𝒟⋆(D, C). [P] is a polytope of dimensionality d because F_h is of dimensionality h and the set P - 𝒱(F_h) includes d-h affinely independent points (see proposition <ref>), which are not located in F_h. 

Let P_F ⊂ P such that [P_F] is a facet of [P]. There are two possibilities:


  * P_F = P - { p}, with p ∈{B̅_M(F_h+1),...,B̅_M(F_d-1) }∪{B̅}. The following cases occur:

	
  * p = B̅. Then [P_F] is included in F_d-1, therefore [P_F] ⊂∂ C;
	 
  * p =B̅_M(F_i), with h+1 ≤ i ≤ d-1, then two cases occur again: 	
	
		
  * h+1 < i. As shown in the proof of proposition <ref>, there exists F'_i ∈ℱ_i(C) such that F'_i ≠ F_i, F_i-1⊂ F'_i, and F'_i ⊂ F_i+1. Moreover, because i > h+1, F_h+1⊂ F_i-1⊂ F'_i. Hence, [P'], with P' = P_F ∪{B̅_M(F'_i) }, is a polytope of [B]^𝒟⋆(D) and [P_F] = [P] ∩ [P'].
		
  * i = h+1. Let F'_h+1∈ℱ_h+1(C) be such that F_h ⊂ F'_h+1 and F'_h+1⊂ F_h+2. There are two possibilities:
		
		
			
  * B_M(F'_h+1) = ∅, then P' = 𝒱(F'_h+1) ∪{B̅_M(F_h+2),...,B̅_M(F_d-1) }∪{B̅} is such that [P'] is a polytope of [B]^𝒟⋆(D) because F'_h+1 is connected to F_h and [P_F] = [P - B̅_M(F_h+1)] = [P] ∩ [P'].
			
  * B_M(F'_h+1) ≠∅, then P' = P_F  ∪{B̅_M(F'_h+1) } is such that [P'] is a polytope of [B]^𝒟⋆(D) and [P_F] = [P] ∩ [P'].
		
	
	
	
		
  * The d-1-dimensional face is obtained by removing vertices in 𝒱(F_h). Thus:
		
		
			
  * If h = 0, 𝒱(F_h) is a single vertex v∈ D, and the edge F_1 = [v, v'] is such that B_M(F_1) = { b } . Then P_F = P - {v} = {B̅_M(F_1), ..., B̅_M(F_d-1) }∪{B̅} and [P_F] ⊂ [B]^⋆. Moreover,  P' = { v'}∪ P_F is such that [P_F] = [P] ∩ [P'] and there exists D' ∈𝒟(B,C), D' ≠ D such that v' ∈ D' and [P'] ⊂ [B]^𝒟⋆(D').
			
  * If h > 0, 	P_F = 𝒱(F_h-1) ∪{B̅_M(F_h+1),..., B̅_M(F_d-1) }∪{B̅}, with F_h-1∈ℱ_h-1(F_h). Let F'_h∈ℱ_h(C) be such that F_h-1⊂ F'_h, F'_h ⊂ F_h+1 and F'_h ≠ F_h. There are two possibilities:

	
  * B_M(F'_h) ≠∅, then P' = P_F ∪{B̅_M(F'_h) } is such that [P'] is a polytope of [B]^𝒟⋆(D) and  [P_F] = [P] ∩ [P'];
	
  * B_M(F'_h) = ∅, then F'_h ⊂ D, because F_h and F'_h are connected by sharing face F_h-1 and P' = 𝒱(F'_h) ∪{B̅_M(F_h+1), ..., B̅_M(F_d-1) }∪{B̅} is such that [P'] is a polytope of [B]^𝒟⋆(D) and  [P_F] = [P] ∩ [P'] (because F_h-1⊂ F'_h).

		


Finally, all the polytopes [𝒱(F_h) ∪{B̅_M(F_h+1),...,B̅_M(F_d-1) }∪{B̅}] of [B]^𝒟⋆(D) such that h > 0 have all their facets shared with another polytope of [B]^𝒟⋆(D) except one facet which is included in ∂ C; the polytopes such that h = 0 have all their facets shared with another polytope of [B]^𝒟⋆(D) except one which is included in ∂ C and one which is included in [B]^⋆.
Therefore, [B]^𝒟⋆(D) is a connected set and its boundary in C - ∂ C is included in [B]^⋆.

Moreover, the set of facets included in [B]^⋆ from polytopes such that h = 0 is:

    E =  ⋃_{F_1,...,F_d-1}∈ℱ^⋆(B,C), F_1 ∩ D ≠∅[{B̅_M(F_1),...,B̅_M(F_d-1}∪{B̅} ].

We have [B]^⋆∩ [B]^𝒟⋆(D) ⊂ E. Indeed, for any set {F_h,...,F_d-1}∈ℱ^𝒟⋆(D,C), such that h > 0, there exists {F_1,...,F_d-1}∈ℱ^⋆(B,C), such that F_1 ⊂ F_h+1, F_1 ∩ D ≠∅ and {F_h+1,...,F_d-1}⊂{F_1,...,F_d-1}. Therefore, for all polytopes [P] such that h > 0 the part of the boundary of [P] which is included in [B]^⋆ is also included in E. Moreover, E ⊂ [B]^⋆∩ [B]^𝒟⋆(D) by definition. Therefore, E = [B]^⋆∩ [B]^𝒟⋆(D).

Moreover, E - (E ∩∂ C) is the boundary of  [B]^𝒟⋆(D) in C - ∂ C, hence the boundary of [B]^𝒟⋆(D) in C - ∂ C is [B]^𝒟⋆(D) ∩ ([B]^⋆ - ∂[B]^⋆).
□  


The union of the classification sets defined by the c-resistar [B]^⋆ in cube C is cube C itself:
	
    C = ⋃_D ∈𝒟(B,C) [B]^𝒟⋆(D).




Proof.
The proof of proposition <ref> shows that for all polytopes [P] ∈ [B]^𝒟⋆(D), a facet of [P] which is not in ∂ C is either shared with another polytope of [B]^𝒟⋆(D) or with another polytope of [B]^𝒟⋆(D'), with D' ≠ D.
Therefore, because the sets [B]^𝒟⋆(D) are of dimensionality d, this union is C itself.
□  



For (D,D') ∈𝒟(B,C)^2, D' ≠ D, ([B]^𝒟⋆(D) ∩ [B]^𝒟⋆(D')) ⊂ [B]^⋆.



Proof
Consider (D,D') ∈𝒟(B,C)^2, D ≠ D'. Consider polytope [P] ∈ [B]^𝒟⋆(D) with P = 𝒱(F_h) ∪{B̅_M(F_h+1),..., B̅_M(F_d-1) }∪{B̅} and polytope [P'] ∈ [B]^𝒟⋆(D') with P' = 𝒱(F'_h) ∪{B̅_M(F'_h+1),..., B̅_M(F'_d-1) }∪{B̅}. We have: [P] ∩ [P'] = [P ∩ P'] and F_h ∩ F'_h' = ∅. Therefore the intersection between [P] and [P'] is a simplex of dimensionality at most d-1, of vertices the points B̅_M(F_i) such that there exists (b, b') ∈ B_M(F_i)^2 with (v_+(b) ∈ D or v_-(b) ∈ D) and (v_+(b') ∈ D' or v_-(b') ∈ D'). Therefore ([B]^𝒟⋆(D) ∩ [B]^𝒟⋆(D')) ⊂ [B]^⋆. 
□ 


These properties of the classification sets [B]^𝒟⋆(D) guarantee that for any point x ∈ C - [B]^⋆, there exists a unique set D such that x ∈ [B]^𝒟⋆(D). This leads to the definition of the resistar classification.
 

Let C be a cube of the grid such that B = B_M(C), The resistar classification function [B]^⋆(.), from C to {-1, 0, +1}, is defined for x ∈ C as follows:

	
  * If B = ∅, then [B]^⋆(x) = ℳ(v), v ∈𝒱(C);
	
  * Otherwise, let 𝒟(B,C) be the set of connected faces of C without boundary points and, for D ∈𝒟(B,C), let [B]^𝒟⋆(D) be the classification associated to D by the c-resistar [B]^⋆.
	
	
  * If x ∈ [B]^⋆ then [B]^⋆(x) = 0, 
	
  * Otherwise there exists a single set D ∈𝒟(B,C) such that x ∈ [B]^𝒟⋆(D) and [B]^⋆(x) = ℳ(v), v ∈𝒱(D). 
	




This classification function is consistent with the classification of the vertices of C by ℳ because, for any vertex v ∈𝒱(D), D ∈𝒟(B,C), [B]^⋆(v) = ℳ(v), and any point x ∈ [B]^𝒟⋆(D) is on the same side of [B]^⋆ as v, since [B]^⋆∩ [B]^𝒟⋆(D) includes the boundary of [B]^𝒟⋆(D) in C - ∂ C.



  §.§.§ Classification algorithm.



Algorithm <ref> takes as input a point x of cube C and, if B = B_M(C) is empty, it returns the classification of a vertex of C by ℳ. Otherwise, if x is not equal to B̅, it computes x_d-1 = r⃗(B̅,x) ∩∂ C, where r⃗(B̅,x) is the ray from B̅ in the direction of x and ∂ C is the boundary of C. x_d-1 is located in a facet F_d-1 of C and algorithm <ref> repeats the same operations for x_d-1∈ F_d-1. When it reaches a face F_i without boundary points, the algorithm returns the classification of a vertex of F_i, or when  x_i = B̅_M(F_i) it returns 0 (see examples on Figure <ref>). 



Algorithm <ref> always terminates, because the dimensionality of face F_i decreases of 1 at each step, and in the worst case the algorithm reaches a face of dimensionality 0, which, by hypothesis, cannot include any boundary point. 

 



Algorithm <ref> applied to x ∈ C returns [B]^⋆(x), as specified in definition <ref>.



Proof. Consider x ∈ C.
 
	
  * If x ∈ [B]^⋆, let S = {B̅_M(F_1),...,B̅_M(F_d-1) }∪{B̅}, with {F_1,...,F_d-1}∈ℱ^⋆(B,C), such that x ∈ [S]. At each step of algorithm <ref>, either x_i = B̅_M(F_i) and then the algorithm returns 0, or x_i-1∈ [B̅_M(F_1),...,B̅_M(F_i-1) ]. Therefore, in the worst case, the algorithm reaches x_1 ∈ [B̅_M(F_1)] = b, b ∈ B, in which case the only possibility is x_1 = b, and the algorithm returns 0. Therefore if x ∈ [B]^⋆, algorithm <ref> returns 0.
	
  * If x ∈ C - [B]^⋆, let {x_d = x, .., x_h } be the values of x_i at the successive steps of algorithm <ref>, h  being the dimensionality of the face F_h such that F_h ∩ B = ∅ at the last step of the algorithm. There exists a unique set of connected faces without boundary points D such that F_h ⊂ D thus x_h ∈ D and x_h ∈ [B]^𝒟⋆(D). For h+1 ≤ i ≤ d the rays r⃗(B̅_M(F_i)  , x_i)  do not cross any simplex of [B]^⋆, thus the segments [x_i, x_i-1] for h+1 ≤ i ≤ d do not cross [B]^⋆ either. Therefore, because the boundary of [B]^𝒟⋆(D) in C- ∂ C is included in [B]^⋆, x = x_d ∈ [B]^𝒟⋆(D). Therefore, algorithm <ref> returns [B]^⋆(x).	

□ 

Actually, it can easily be shown that P = 𝒱(F_h) ∪{B̅_M(F_h+1),..., B̅_M(F_d-1)}∪{B̅}, with the faces F_i defined by algorithm <ref> is such that [P] a polytope of [B]^𝒟⋆(D) and x ∈ [P].

It appears finally that, even if the set [B]^⋆ includes a large number of simplices, the classification algorithm requires at most d relatively light computations (selecting boundary points in a face, computing their barycentre, projecting a point on the boundary of the face). Section <ref> presents a modification of this algorithm with a better management of the memory space.




 §.§ c-resistar approximation on the grid.
 

The regular grid G comprises n_G^d points covering X and its facets. The values of the coordinates of the grid points are taken in { 0, 1/n_G-1, 2/n_G-1..., 1  }. ℱ_i(G) denotes all the i-dimensional cubes or cube faces of G and ℱ(G) denotes the set of all cubes or cube faces of G.



  §.§.§ Definition.



The definition of the c-resistar approximation of M on grid G comes directly from the definition of the c-resistars in the cubes. 


The c-resistar approximation of M on grid G, denoted [B_M(G)]^⋆, B_M(G) being the set the boundary points from of all the edges of the cubes of the grid, is the union of the c-resistars approximating M in the cubes of G:


    [B_M(G)]^⋆ = ⋃_C ∈ℱ_d(G), B_M(C) ≠∅ [B_M(C)]^⋆.






The c-resistar approximation of M on grid G is a set of d-1-dimensional simplices and its boundary is included in the boundary of X.



Proof.
[B_M(G)]^⋆ is a set of d-1-dimensional simplices as the union of sets of d-1-dimensional simplices (see proposition <ref>). 

Let C be a cube of G, with B = B_M(C) ≠∅, let S = {B̅_M(F_1),...,B̅_M(F_d-1) }∪{B̅}, such that [S] is a d-1-dimensional simplex in [B]^⋆. The facet [S_F] = [S - {B̅_M(C) }] of S is located in facet F_d-1 of C. Two cases occur:

	
  * There exists a cube C', with B_M(C') = B', sharing facet F_d-1 with C. Then the simplex [S'] = [S_F ∪{B̅'̅}] is such that [S'] ∈ [B_M(C')]^⋆ and [S_F] = [S] ∩ [S'];
	
  * Otherwise, [S_F] is included in the boundary of X.

Therefore,  taking proposition <ref> into account, all the simplices of [B_M(G)]^⋆ share all their facets with other simplices of [B_M(G)]^⋆, except the facets which are in the boundary of X.
□ 



  §.§.§ Classification by the c-resistar approximation on the grid.


The classification sets defined by the c-resistar approximation on the grid are derived from the classification sets in the grid cubes.


Let B_G = B_M(G), ℋ(B_G,G) = { F ∈ℱ(G), B_M(F) = ∅} and 𝒟(B_G,G) be the connected components of ℋ(B_G,G).
 
For D ∈𝒟(B_G,G) the classification set [B_G]^𝒟⋆(D) defined by [B_G]^⋆, the c-resistar approximation of M on grid G, is the set:

    [B_G]^𝒟⋆(D) = ⋃_C ∈ℱ_d(G) [B_M(C)]^𝒟⋆(D ∩ C),

where:

    [B_M(C)]^𝒟⋆(D ∩ C) = 
    	∅,  D ∩ C = ∅,
    
    	C,  D ∩ C = C,

and follows definition <ref> otherwise.




 For all D ∈𝒟(B_G,G), D ⊂ [B_G]^𝒟⋆(D), [B_G]^𝒟⋆(D) is connected and its boundary in X - ∂ X is [B_G]^𝒟⋆(D) ∩ ([B_G]^⋆ - ∂ [B_G]^⋆).



Proof.

	
  * D ⊂ [B_G]^𝒟⋆(D) by definition.

 
  * All the polytopes of [B_G]^𝒟⋆(D) defined from face F_h ∈ D are connected to each other because they share face F_h. Because D is a connected set by definition, the polytopes defined from all faces F_h ∈ D are connected to each other through the connections between faces F_h. Therefore [B_G]^𝒟⋆(D) is a connected set. 


  * All the polytopes of [B_G]^𝒟⋆(D) are of dimensionality d, because they are either cubes without boundary points, or polytopes of a classification set in a cube, which are all of dimensionality d.


  * Consider D ∈𝒟(B_G,G) and a cube C such that D ∩ C ≠∅. 


  * If C ⊂ D, [B_M(C)]^𝒟⋆(C ∩ D) = C and for any d-1-dimensional face F_d-1 of C which is shared with another cube C' ∈ℱ_d(G), there exists a polytope [P'] ⊂ [B_M(C')]^𝒟⋆(D ∩ C') such that F_d-1⊂ [P']. Indeed, if C' ⊂ D, then [B_M(C')]^𝒟⋆(D ∩ C') = C' and F_d-1⊂ C ∩ C' by hypothesis. Otherwise, we have { F_d-1}∈ℱ^𝒟⋆(D ∩ C', C') because B_M(F_d-1) = ∅;

  * If D ∩ C ≠ C, let P = 𝒱(F_h) ∪{B̅_M(F_h+1),..., B̅_M(F_d-1)  }∪{B̅_M(C) },  with { F_h,..., F_d-1}∈ℱ^𝒟⋆(D ∩ C, C). [P] is a polytope included in [B_G]^𝒟⋆(D). Let P_F = P - {B̅_M(C) }. [P_F] is a face of [P] which is included in facet F_d-1 of C. If there exists a cube C' ∈ℱ_d(G), C' ≠ C, such that F_d-1⊂ C', then:


  * if C' ⊂ D, [P_F] = F_d-1 and F_d-1 is shared by [P] and C';

  * if C' ∩ D ≠ C', then B_M(C') ≠∅. The set P' = P_F ∪{B̅_M(C') } is such that [P'] ⊂ [B_M(C')]^𝒟⋆(D ∩ C') and [P_F] = [P] ∩ [P']. 

As shown in the proof of proposition <ref>, the other facets [P_F] of [P] which are on the boundary of [B_M(C)]^𝒟⋆(C ∩ D) are such that [P_F] ⊂ [B_M(C)]^⋆⊂ [B_G]^⋆.

Therefore, the boundary of [B_G]^𝒟⋆(D) is either in faces of cubes which are in ∂ X or included in [B_G]^⋆. 

Moreover, in each cube C such that D ∩ C ≠∅ and B_M(C) ≠∅, the boundary of [B_M(C)]^𝒟⋆(D) in C - ∂ C is [B_M(C)]^𝒟⋆(D) ∩ ([B_M(C)]^⋆ - ∂ [B_M(C)]^⋆) (proposition <ref>). Taking the union of these sets for all cubes of G, it can easily be seen that the boundary of [B_G]^𝒟⋆(D) in X - ∂ X is [B_G]^𝒟⋆(D) ∩ ([B_G]^⋆ - ∂ [B_G]^⋆).
□  


For all points x ∈ X - [B_G]^⋆, there exists a unique set D ∈𝒟(B_G, G) such that x ∈ [B_G]^𝒟⋆(D).



Proof.
Let C ∈ℱ_d(G) be such that x ∈ C. 

If B_M(C) = ∅, then there exist a unique set D ∈𝒟(B_G, G) such that C ⊂ D.

Otherwise, there exists a unique set D_C ∈𝒟(B_M(C), C) such that x ∈ [B_M(C)]^𝒟⋆(D_C) (because of propositions <ref> and <ref>) and there exists a unique set D ∈𝒟(B_G, G) such that D_C ⊂ D.
□ 


The classification function by the resistar approximation is defined directly from proposition <ref>.


The classification [B_G]^⋆(.) by the resistar approximation on the grid is a function from X to {-1,0,+1} defined for x ∈ X as follows: 

	
  * If x ∈ [B_G]^⋆, [B_G]^⋆(x) = 0
	
  * Otherwise, proposition <ref> ensures that there exists a unique classification set D ∈𝒟(B_G, G) such that x ∈  [B_G]^𝒟⋆(D), and [B_G]^⋆(x) = ℳ(v), v ∈𝒱(D).



This definition is consistent with the classification of the points of the grid by ℳ. Indeed, for all grid points v ∈𝒱(D), D ∈𝒟(B_G, G), [B_G]^⋆(v) = ℳ(v) and any point x ∈ [B_G]^𝒟⋆(D) is on the same side of [B_G]^⋆ as v, because the boundary of [B_G]^𝒟⋆(D) in X - ∂ X is [B_G]^𝒟⋆(D) ∩ ([B_G]^⋆ - ∂ [B_G]^⋆).


For all x ∈ X, let C_x be a cube of ℱ_d(G) such that x ∈ C_x. We have:
	
    [B_G]^⋆(x) = 	[B_M(C_x)]^⋆(x).




Proof.
Consider x ∈ X and C_x ∈ℱ_d(G) such that x ∈ C_x. 
There exists D ∈𝒟(B_G, G) such that x ∈  [B_G]^𝒟⋆(D) (proposition <ref>). By definition, [B_G]^𝒟⋆(D) ∩ C_x = [B_M(C_x)]^𝒟⋆(D ∩ C_x) thus x ∈ [B_M(C_x)]^𝒟⋆(D ∩ C_x).
Therefore [B_G]^⋆(x) =	[B_M(C_x)]^⋆(x).
□ 


Computing [B_M(C)]^⋆(x) can thus be performed by first computing a cube C_x such that x ∈ C_x, and then applying algorithm <ref> to x in C_x. However, this approach would require to store the classification of all the vertices of the grid. The next subsection proposes a method requiring less memory space.




 §.§ Algorithm of classification avoiding to store the classification of all grid vertices
 


This subsection describes the algorithm of classification of c-resistar approximation when storing the boundary points and only the classification by ℳ of the vertices of the edge on which the boundary point is located, instead of the classification by ℳ of all the vertices of the grid. 



  §.§.§ Classification algorithm in the cube



The modified classification algorithm is based on proposition <ref>. 

 
Let C be a cube of G. For all x ∈ C - [B]^⋆ and let F_h be the face of C such that B_M(F_h) = ∅ at the last step of algorithm <ref> applied to x. The face F_h+1 from the previous step is such that B_M(F_h+1) ≠∅ and there exists b ∈ B_M(F_h+1) such that v_+(b) ∈ F_h or v_-(b) ∈ F_h.



Proof
The proof comes directly from the argument used in the proof of proposition <ref>.
□  


Algorithm <ref> modifies algorithm <ref> using proposition <ref>: it tests the vertices of the boundary points in B_h+1 and the classification by ℳ of the first of these vertices found in F_h gives the final classification to return. Note that this algorithm supposes that B_M(C) ≠∅ (which is not the case of algorithm <ref>).

Moreover, computing the ray r⃗(B̅_M(F_i),x) requires to perform a division by B̅_M(F_i)  - x which may lead to very large numbers and strong losses of precision when B̅_M(F_i)  - x is very close to 0. Therefore, in practice, the classification returns 0 when B̅_M(F_i)  - x is smaller than a given threshold (we take 0.00001). With this modification, some points at small distance of [B]^⋆ are classified 0. Algorithm <ref> also includes this modification.


 




  §.§.§ Classification algorithm on the whole grid.



Algorithm <ref> performs the classification of a point x ∈ X by the c-resistar approximation on the grid keeping in memory only the set C_G of cubes containing boundary points. It requires defining point m ∈ X which the centre of an arbitrarily chosen cube C_m in C_G. It computes the cube C'_x ∈ C_G which is the closest to x and such that C'_x ∩ [m,x] ≠∅ and the point x' ∈ C'_x ∩ [m,x] which is the nearest to x in cube C'_x. Then, it computes the classification of x' in the identified cube C'_x (see illustration on Figure <ref>).

In practice, a hash table stores the set of couples (C, B_M(C)), for the cubes C such that B_M(C) ≠∅. Computing x' and C'_x can be done by computing the intersections of [x, m] with the facets of cubes of the grid. The procedure then requires checking which cubes intersecting [x, m] are in the hash table. The number of cubes crossing [x, m] varies linearly with n_G hence the number of requests to the hash table is also linear with n_G.  




 


When given a point x ∈ X as input, algorithm <ref> yields [B_M(G)]^⋆(x) as output.



Proof.
Let x' = x'(C'_x) as defined in algorithm <ref>. It always exists because m is the centre of a cube C_m containing boundary points, and C'_x = C_m if no other cube containing boundary points cuts the segment [x,m]. By construction, the segment [x, x'] does not cross [B_M(G)]^⋆, therefore [B_M(G)]^⋆(x) = [B_M(G)]^⋆(x') = [B_M(C'_x)]^⋆(x').
□  






§ MANIFOLD APPROXIMATION WITH RESISTARS IN SIMPLICES FROM KUHN TRIANGULATION.



Figure <ref>, panel (b) and Figure <ref>, give examples of c-resistars that are not manifolds. Indeed, in both of these cases, it is impossible to find a continuous and invertible mapping from the neighbourhood of point B̅ in the resistar into a hyperplane. However, for numerous applications, including viability kernel approximation, it is highly recommended to build manifold approximations.
In order to address this problem, we now break the cubes into simplices, using the Kuhn triangulation and we define resistars in these simplices.
 The next subsection focuses on the resistar in a single simplex and the following subsection on the approximation on the whole grid.




 §.§ K-resistar in a single simplex from Kuhn triangulation.






  §.§.§ Definition and main properties.


The Kuhn triangulation of a cube C is defined by the set of 𝒫(d) permutations of set {1, 2, .., d}. Let P be one of such permutations, the corresponding simplex S_P is defined in cube C as:

    S_P = { x ∈ C, min_P(1)≤ x_P(1)≤ x_P(2)≤ .. ≤ x_(P(d)≤max_P(d)}.


Where x_P(i) is the P(i)^th coordinate of point x,  min_P(1) and max_P(d) are respectively the minimum value of the P(1)^th coordinate and the maximum value of the P(d)^th coordinate for points in cube C. 

We denote these simplices with the prefix "K", in order to distinguish them from the simplices used to approximate M.  Examples of K-simplices in cubes are represented (by their edges) on Figures <ref> and <ref>. The set of i-dimensional faces of a K-simplex S_P is denoted 𝒦_i(S_P). The set of K-simplices of cube C is denoted 𝒦_d(C). The union of all the K-simplices defined by all the permutations is the cube itself:

    C = ⋃_S_P ∈𝒦_d(C) S_P.


On each edge  [v_-,v_+] of a K-simplex such that ℳ(v_-) = -1 and ℳ(v_+) = +1, we compute a boundary point b_M([v_-,v_+]), approximating the intersection between the edge and M, by q successive dichotomies, as previously. The value of q may be adjusted in order to ensure a given precision of the approximation even on the longest edge of the K-simplex. 

We denote B_M(S) the set of boundary points of a K-simplex or of a K-simplex face S. 

The resistars in K-simplices are defined similarly to the c-resistars, except that faces of the K-simplices are considered instead of faces of cubes (see examples on Figures <ref> and <ref>). We denote K-resistars the resistars defined in K-simplices.


Let S_P be a K-simplex such that B = B_M(S_P) ≠∅. The K-resistar [B]^⋆ is the following set:
	
    [B]^⋆ = ⋃_{ F_1,...,F_d-1}∈𝒦^⋆(B,S_P) [{B̅_M(F_1),...,B̅_M(F_d-1) }∪{B̅}]

	with:
	
    { F_1,...,F_d-1}∈𝒦^⋆(B,S_P) ⇔
    		F_1 ∈𝒦_1(S_P), B_M(F_1) ≠∅
    
    		F_i ∈𝒦_i(S_P), F_i-1⊂ F_i, 2 ≤ i ≤ d-1.

where i is an integer.


 

 

Using the same arguments as in the proofs of propositions <ref> and <ref>, it can easily be shown that K-resistar [B_M(S_P)]^⋆ is a set of d-1-dimensional simplices and that its boundary is included in the boundary of S_P. 


Let S_P be a K-simplex such that B = B_M(S_P) ≠∅. [B]^⋆ is a manifold. 



Proof.
Consider a point x ∈ [B]^⋆. There exists {F_1,...,F_d-1}∈𝒦^⋆(B, S_P) such that x ∈ [{B̅_M(F_1),..., B̅_M(F_d-1)}∪{B̅}] and there exist positive numbers (λ_i), i ∈{1,...,d} such that (setting F_d = S_P):

	
    x = ∑_i ∈{1,...,d}λ_i B̅_M(F_i) ∑_i ∈{1,...,d}λ_i = 1.

	
The Vapnik-Chervonenkis dimension of the d-1-dimensional linear separators being d+1 <cit.>, for any cut into two sets of d+1 affinely independent points, there exists a d-1-dimensional hyperplane making this cut.
Let H be a hyperplane separating the set V_+ of vertices v of S_P such that ℳ(v) = +1 from the set V_- of vertices v of S_P such that ℳ(v) = -1. To each boundary point b ∈ B, located on edge [v_-, v_+] with v_- ∈ V_- and v_+ ∈ V_+, we associate point b_H = [v_-, v_+] ∩ H. Let B_H be the set of points b_H so defined. For any face F_i of S_P, we denote B_H(F_i) = F_i ∩ B_H.
We can associate uniquely to x the point x_H ∈ H defined as follows:
	
	
    x_H = ∑_i ∈{1,...,d}λ_i B̅_H (F_i),

	
	where the faces F_i and λ_i are defined in equation <ref>. Therefore there exists a continuous and invertible function from [B]^⋆ to hyperplane H.	 
□ 




  §.§.§ Classification function and algorithm.


As stated in details in proposition <ref>, a K-simplex S_P such that B_M(S_P) ≠∅ is always separated by its K-resistar into two classification sets, each containing a single face of the K-simplex without boundary points (Figure <ref> panel (a) shows examples of these classification sets in 2 dimensions).


Let S_P be a K-simplex such that B = B_M(S_P) ≠∅. let ℋ(B,S_P) be the set of faces of S_P without boundary points :

    ℋ(B,S_P) = { F ∈𝒦(S_P), B_M(F) = ∅},

where 𝒦(S_P) is the set of all the faces of S_P. ℋ(B,S_P), includes 2 faces of S_P: [V_+] where V_+ = { v ∈𝒱(S_P), ℳ(v) = +1 } and [V_-] where V_- = { v ∈𝒱(S_P), ℳ(v) = -1 }. The resistar [B]^⋆ separates S_P into two classification sets [B]^𝒟⋆([V_+]) and [B]^𝒟⋆([V_-]), such that [V_±] ⊂ [B]^𝒟⋆([V_±]), which are :

    [B]^𝒟⋆([V_±]) = ⋃_{ F_h,..,F_d-1}∈𝒦^𝒟⋆([V_±],S_P) [𝒱(F_h) ∪{B̅(F_1),...,B̅_M(F_d-1) }∪{B̅}],

with:
	
    { F_h,..,F_d-1}∈𝒦^𝒟⋆([V_±], S_P) ⇔
    	F_h  ∈𝒦_h([V_±]), 0 ≤ h ≤ dim([V_±])
    
    	F_i ∈𝒦_i(S_P), F_i-1⊂ F_i, h+1 ≤ i ≤ d-1, 
    
    	B_M(F_h+1) ≠∅,

where dim([V_±]) is the dimensionality of [V_±]. 

Moreover, [B]^𝒟⋆([V_+]) and [B]^𝒟⋆([V_-]) are connected sets, [B]^𝒟⋆([V_-])∩ [B]^𝒟⋆([V_+]) = [B]^⋆ and [B]^𝒟⋆([V_-]) ∪ [B]^𝒟⋆([V_+]) = S_P.



Proof.
The sets V_+ and V_- are such that the sets [V_+] and [V_-] are faces of S_P, because S_P is a simplex and any set of its vertices defines one of its faces. 

The polytopes of [B]^𝒟⋆([V_±]) include at least one face F_h of [V_±], and [V_±] ⊂ [B]^𝒟⋆([V_±]) and is a connected set, therefore [B]^𝒟⋆([V_±]) is a connected set.

Using the same reasoning as in the proof of proposition <ref>, it can easily be shown that [B]^𝒟⋆([V_-]) ∩ [B]^𝒟⋆([V_+]) = [B]^⋆ and [B]^𝒟⋆([V_-]) ∪ [B]^𝒟⋆([V_+]) =S_P.
□  


The following definition of the classification function is consistent because proposition <ref> ensures that, if x ∉ [B]^⋆, either x ∈ [B]^𝒟⋆([V_+]) or x ∈ [B]^𝒟⋆([V_-]).


The classification [B]^⋆(.) by resistar [B]^⋆ in K-simplex S_P is the function from S_P to {-1, 0, +1} which, is defined as follows for x ∈ S_P (setting B = B_M(S_P)):


  * If B = ∅, then [B]^⋆(x) = ℳ(v), v ∈𝒱(S_P);

  * Otherwise:

	
  * If x ∈ [B]^⋆, [B]^⋆(x) = 0;
	
  * Otherwise, let ℋ(B,S_P) = {[V_-], [V_+] }:	
	
		
  * If  x ∈ [B]^𝒟⋆([V_+]), [B]^⋆(x) = +1;
		
  * If x ∈ [B]^𝒟⋆([V_-]), [B]^⋆(x) = -1.
	





Algorithm <ref> is easily adapted to a K-simplex instead of a cube, by replacing the faces of the cube by the faces of the K-simplex (see Figure <ref> panel (b)). It is direct to show that this algorithm returns [B]^⋆(x).


 




 §.§ K-resistar approximation on the grid.
 




  §.§.§ Definition.



The definition of the K-resistar approximation of M on the grid is similar to one of the c-resistar approximation. 
 

Let B_M^K(G) be the set of all the boundary points of all the edges of the K-simplices of the grid. We call K-resistar approximation of M on grid G, denoted [B_M^K(G)]^⋆, the following set of simplices:

	
    [B_M^K(G)]^⋆= ⋃_S_P ∈𝒦_d(G), B_M(S_P) ≠∅ [B_M(S_P)]^⋆,

where 𝒦_d(G) is the set of all the K-simplices defined in the cubes of G.



The K-resistar approximation of M on grid G is a set of d-1-dimensional simplices and its boundary is included in the boundary of X.



Proof.
The proof is the same as the one of proposition <ref>, considering faces of K-simplices instead of cube faces.
□ 


The K-resistar approximation of M on grid G is a d-1-dimensional manifold.


Proof.
K-resistars in K-simplices are d-1-dimensional manifolds as shown in proposition <ref>. We need to show that the union of K-resistars in K-simplices sharing a K-simplex face is also a manifold in the neighbourhood of their common points belonging to this face.

Let F_i be a i-dimensional face of a K-simplex, such that B_M(F_i) ≠∅. [B_M(F_i)]^⋆ = [B_M^K(G)]^⋆∩ F_i is a i-1-dimensional manifold and there exists a i-1-dimensional hyperplane H_i which separates the vertices of F_i classified positively by ℳ from the ones classified negatively. Let n_i be the normal vector of H_i, such that the vertices classified positively by ℳ are on the positive side of H_i. 

For each K-simplex S in 𝒦_d(G) containing F_i, there exists a d-1-dimensional hyperplane H_S separating the vertices of S classified positively by ℳ from the ones classified negatively. Let n_S be the normal vector of  H_S, such that the vertices classified positively by ℳ are on the positive side of ℋ_𝒮. 

We have n_i.n_S ≥ 0 because the hyperplane H_S also separates the positive and negative vertices of F_i. Therefore, we can choose each H_S such that H_S ∩ F_i = H_i.  With this choice of the hyperplanes H_S, the continuous and bijective mapping between each simplex of the K-resistar in S and H_S, defined in the proof of proposition <ref>, is the same for the points in [B_M(F_i)]^⋆ for all K-simplices S sharing face F_i. 

Let H'_i, be the d-1 dimensional hyperplane extending H_i to the set X by extending the i-dimensional normal vector n_i to the d-dimensional normal vector n'_i of d-1-dimensional hyperplane H'_i which coincides with H_i in F_i, by setting to 0  all the coordinates of n'_i which are not defined in F_i. The composition of the mappings from the K-resistar in S to the hyperplane H_S with the orthogonal projection on H'_i for all S defines a continuous and bijective mapping from the neighbourhood of [B_M(F_i)]^⋆ in the K-resistar approximation to hyperplane H'_i.
□  



  §.§.§ Classification by the K-resistar approximation on the grid.



The classification sets in X defined by the K-resistar approximation on the grid G are defined similarly to those of the c-rersistar approximation on the grid. 𝒦_i(G) denotes the set of all the faces of K-simplices defined in the cubes of the grid (𝒦_d(G) denoting the set of all the K-simplices defined in the grid cubes).


Let B_G = B_M^K(G) be the set of boundary points defined in all the K-simplices of grid G. Let ℋ^K(B_G,G) = { F ∈𝒦(G), F ∩ B_G = ∅}, where 𝒦(G) is the set of the K-simplices of the cubes of the grid G and of all their faces. Let 𝒟^K(B_G,G) be the connected components of ℋ^K(B_G,G). 

For D ∈𝒟^K(B_G,G), the classification sets [B_G]^𝒟⋆(D) defined by the K-resistar approximation are:

    [B_G]^𝒟⋆(D) = ⋃_ S_P ∈𝒦_d(G)  [B_M(S_P)]^𝒟⋆(D ∩ S_P),

with:

    [B_M(S_P)]^𝒟⋆(D ∩ S_P) =
    	∅,  D ∩ S_P = ∅,
    
    	S_P,  D ∩ S_P = S_P,

and is specified in proposition <ref> in the other cases. 




 For all D ∈𝒟^K(B_G,G), D ⊂ [B_G]^𝒟⋆(D), [B_G]^𝒟⋆(D) is connected and its boundary in X - ∂ X is a subset of [B_G]^⋆.



Proof.
The proof is similar to the one of proposition <ref>, when using faces of K-simplices instead of cube faces.
□ 


For all points x ∈ X, such that x ∉ [B_G]^⋆, there exists a unique set D ∈𝒟^K(B_G, G) such that x ∈ [B_G]^𝒟⋆(D).



Proof.
The proof is similar to the one of proposition <ref>.
□ 


Let B_G = B_M^K(G). The classification [B_G]^⋆(.) by the resistar approximation from the grid is the function from X to {-1,0,+1} defined as follows for x ∈ X: 

	
  * If x ∈ [B_G]^⋆, [B_G]^⋆(x) = 0
	
  * Otherwise, proposition <ref> ensures that there exists a unique set D ∈𝒟^K(B_G,G) such that x ∈ [B_G]^𝒟⋆(D), and [B_G]^⋆(x) = ℳ(v), v ∈𝒱(D).




For x ∈ X, let S_P(x) be the K-simplex of 𝒦_d(G) such that x ∈ S_P(x). We have:
	
    [B_M^K(G)]^⋆(x) = 	[B_M(S_P(x))]^⋆(x).



Proof.
The proof is similar to the one of proposition <ref>.
□



  §.§.§ Classification algorithm.



In practice, when classifying point x ∈ X, we also use algorithm <ref>, which provides a cube C'_x such that B_M^K(C'_x) ≠∅ and a point x' to classify in this cube, ensuring [B_M^K(G)]^⋆(x) = [B_M^K(C'_x)]^⋆(x'). Then a K-simplex of C'_x containing x' is determined by ordering the coordinates of x', this order providing the permutation P defining S_P. Then the procedure computes B_M^K(C'_x) ∩ S_P, the boundary points belonging to S_P. At this point, the classification of x' in K-simplex S_P is performed with algorithm <ref> (in its version adapted to K-simplices). 

The procedure of classification using K-resistars is thus a bit more complicated than the one of c-resistars because it requires identifying the K-simplex containing the point to classify and determining its boundary points.




§ ACCURACY OF THE APPROXIMATION WHEN THE SIZE OF THE GRID INCREASES.



Theorem <ref> bounds the Hausdorff distance between a resistar approximation and the manifold to approximate, when this manifold is smooth enough. 

The distance d(x, A) from a point x ∈ℝ^d to a set A ⊂ℝ^d is defined as (inf denoting the infimum):

    d(x, A) = inf_y ∈ Ax - y.

The Hausdorff distance d_H(A,B) between set A and set B, both subsets of ℝ^d, is defined as  (sup denoting the supremum):

    d_H(A, B) = max(sup_x ∈ A d(x, B), sup_y ∈ B d(y, A)).

The smoothness of the manifold is characterised by its reach <cit.>, which is the supremum of ρ such that for any point x of ℝ^d for which d(x, M) = ρ, there is only one point y ∈ M such that x - y  = ρ. Note that if the reach of M is strictly positive, then M is twice differentiable <cit.>.



Let M be a d-1-dimensional manifold cutting the compact X = [0,1]^d into two parts, G be a regular grid of n_G^d points covering X and its boundary, ϵ = 1/n_G-1 be the size of an edge of the grid.

If the reach r of M is such that r > √(2) d ϵ, if for all i-dimensional faces F of X, M ∩ F is a i-1-dimensional manifold of reach r_F > √(2) i ϵ, and if all the boundary points are determined with q ≥ -log_2(ϵ) dichotomies, then the Hausdorff distance between M and its resistar approximation (in cubes or in K-simplices) decreases like 𝒪(d ϵ^2).
 
 

The proof of theorem <ref> uses two lemmas presented in paragraph <ref>. Then it uses an induction on the space dimensionality (set in paragraph <ref>) with two parts: bounding the distance between the resistar approximation and M (paragraph <ref>) and bounding the distance between M and the resistar approximation (paragraph <ref>). 




 §.§ Lemmas.




Let r >0 be the reach of M and let δ > 0 be such that r > δ. For any couple of points (y_1,y_2) of M such that y_1 - y_2 ≤δ:

    y_2 - P_y_1(y_2) ≤δ^2/2r + 𝒪( δ^3),

where P_y_1(y_2) is the orthogonal projection of y_2 on the hyperplane tangent to M at y_1.  



Proof.
Let (y_1,y_2) ∈  M^2 be such that y_1 - y_2 ≤δ < r, and n be the normal vector of the hyperplane T tangent to M at y_1. Let M_- (resp. M_+) be the set of points x ∈ X such that ℳ(x) = -1 (resp.  ℳ(x) = +1). There exists ℬ(c_+,r) (resp.  ℬ(c_-,r)) a ball tangent to M at y_1 such that M_- ∩ℬ(c_+,r) = ∅ (resp. M_+ ∩ℬ(c_-,r) = ∅). y_2 is located between the balls ℬ(c_+,r) and ℬ(c_-,r), and we can suppose that it is closer to ℬ(c_+,r) (the reasoning would of course be the same if it was closer to  ℬ(c_-,r)). Let y'_2 be the projection of y_2 on ∂ℬ(c_+,r) parallel to n. We have:

    y_2 - P_y_1(y_2) ≤y'_2 - P_y_1(y_2) ,

and:

    P_y_1(y_2) - y_1 ≤δ,

because P_y_1(y_1) = y_1 and the projection is contracting. 
Moreover (see figure <ref>, panel (a)):  

    y'_2 - P_y_1(y_2)  = r (1 - cosα),

with:

    cosα≥√(1 - (δ/r)^2),

Developing equation <ref> at the second order, we get:

    y_2 - P_y_1(y_2) ≤δ^2/2r + 𝒪(δ^3).

□  


Let 𝒞 be a set of j^d adjacent cubes of the grid, covering a cubic part of X of edge size j ϵ (ϵ = 1/n_G -1), including a non-void set of boundary points B = B_M(𝒞), computed on cube edges, or B = B_M^K(𝒞), computed on edges of K-simplices, each determined with q dichotomies. If the reach r of M is such that:

    r > j√(d)ϵ,

then for any point x ∈ [B]^⋆ and for any point y ∈ (M ∩𝒞):

    x - P_y(x) ≤  2^-qϵ + d j^2/2rϵ^2 + 𝒪(ϵ^3),

where P_y(x) is the orthogonal projection of x on the hyperplane tangent to M at y.  



Proof.
By construction, for any boundary point b of B located on edge [v_-(b), v_+(b)] there exists a point b_M ∈ M ∩ [v_-(b), v_+(b)] such that b - b_M ≤ 2^-q-1ϵ. Therefore, for each boundary point b of B, we can write:


    b  - P_y(b) ≤b - b_M  + b_M - P_y(b_M) + P_y(b_M) - P_y(b),

	
with:


  * b - b_M≤ 2^-q-1ϵ (see equation <ref>);

  * P_y(b_M) - P_y(b)≤  2^-q-1ϵ, because the orthogonal projection is contracting;

  * b_M - P_y(b_M) ≤d j^2 ϵ ^2/2r + 𝒪(ϵ^3), because b_M - y≤ j√(d)ϵ, since both b_M and y belong to 𝒞, and applying lemma <ref>. 

Overall, we get:


    b  - P_y(b) ≤ 2^-qϵ + dj^2 /2rϵ^2 + 𝒪(ϵ^3).

	
Moreover, by definition of [B]^⋆, for any point x in [B]^⋆ there exists a set of positive numbers (λ_b)_b ∈ B such that:


    x = ∑_b ∈ Bλ_b b, ∑_b ∈ Bλ_b = 1.
	
	
Therefore:

    x - P_y(x)≤∑_b ∈ Bλ_b  b - P_y(b) ≤ 2^-qϵ + d j^2 /2rϵ^2 + 𝒪(ϵ^3).
	
□  

 
 


 





 §.§ Starting induction.




Assume d = 1 and r > √(2)ϵ. M is a set of discrete points such that, for b_M and b'_M  two distinct points of M, b_M - b'_M >  √(2)ϵ. Therefore, in any edge [v,v'] of the grid, v and v' being two consecutive points such that v-v' = ϵ, there is at most one point b_M of M in [v,v'] and for each point b_M of M, there exists a single boundary point b ∈ [v,v'] with b-b'_M≤ 2^-q-1ϵ, q being the number of dichotomies performed to get b. Moreover, by construction, there is no boundary point in a segment [v,v'] such that [v,v'] ∩ M = ∅. Therefore, choosing q ≥ -log_2(ϵ), ensures that theorem <ref> is true for d = 1.

Now, we assume (induction hypothesis) that the theorem is true in a compact of any dimensionality lower or equal to d-1 and we consider a manifold M splitting a X = [0,1]^d of dimensionality d and its resistar approximation, both satisfying the conditions of theorem <ref>. In the next subsection, we bound the distance from the resistar approximation to M and in the following subsection, we bound the distance from M to the resistar approximation. In both cases, the neighbourhood of the boundary of X is a specific case requiring the induction hypothesis.




 §.§ Bounding the distance from the resistar approximation to M.
 



Let C be a cube of the grid and [B]^⋆ the resistar (c-resistar or K-resistar) approximation of M in this cube, supposed non-void. 

Since there are boundary points in C, M cuts some edges of C and C ∩ M ≠∅. Let y_0 ∈ M ∩ C and let ℬ(c_+,r) and ℬ(c_-,r) be the positive and negative balls tangent to y_0 as defined in the proof of lemma <ref>. Applying lemma <ref>, for all x in [B]^⋆, because the maximum distance between two points of C is √(d)ϵ, and r > √(2) d ϵ > √(d)ϵ we have:

    x - P_y_0(x)≤ 2^- qϵ + d /2rϵ^2 + 𝒪(ϵ^3),
	

where P_y_0(x) is the orthogonal projection of x on T, the hyperplane tangent to M at y_0.
Moreover, P_y_0(x) - y_0 ≤√(d)ϵ, because the orthogonal projection is contracting. Let z_- and z_+ be the projection of x parallel to n, the normal vector to T, on respectively ℬ(c_-,r) and ℬ(c_+,r). Because of lemma <ref>, we have (see figure <ref> panel b):

    P_y_0(x) - z_-≤d/2rϵ^2 + 𝒪(ϵ^3) P_y_0(x) - z_+≤d /2rϵ^2 + 𝒪(ϵ^3).
	

There exists y ∈ M ∩ [z_-, z_+] because M is a d-1-dimensional manifold located between ℬ(c_+,r) and ℬ(c_-,r), and we have:


    x - y≤x - P_y_0(x) + P_y_0(x) - y≤ 2^- qϵ + d/rϵ^2 + 𝒪(ϵ^3),
	
because P_y_0(x) = P_y_0(y) and P_y_0(x) - y≤ P_y_0(x) - z_+ or  P_y_0(x) - y≤ P_y_0(x) - z_-.
Two cases can take place:

	
  * y ∈ X, which is guaranteed when the cube C is not at the boundary of X (see figure <ref>, panel (a)). Then if q ≥ - log_2(ϵ), x - y  = 𝒪(d ϵ^2).

  * y ∉ X, which can happen when C is at the boundary of X (see figure <ref>, panel (b)). Let z = [x,y] ∩∂ X and let F be the facet of X such that z ∈ F. We have: [x,z] ∩ M = ∅, hence ℳ(z) ≠ [B]^⋆(z). Because of the induction hypothesis, there exists a point y' ∈ (M ∩ F) such that y' - z = 𝒪((d-1) ϵ^2).
 Since: 

    x - z≤x - y≤ 2^- qϵ + d /rϵ^2 + 𝒪(ϵ^3),
	
if q ≥ - log_2(ϵ), x - y'≤x - z + z - y' = 𝒪(d ϵ^2).



Therefore, in all cases, if q ≥ - log_2(ϵ), for all x ∈ [B]^⋆, there exists y ∈ M ∩ X such that x - y = 𝒪(d ϵ^2).

 




 §.§ Bounding the distance from M to its resistar approximation.
 



Consider a point y_0 ∈ M ∩ X. Let C be a cube of the grid such that y_0 ∈ C, let T be the hyperplane tangent to M at y_0, let n be its normal vector and ℬ(c_+,r) and ℬ(c_-,r) be the positive and negative balls tangent to y_0. Let 𝒞 be the cube of centre the centre of C, and of edge size 3 ϵ. The segment [y_0,c_+] (resp. [y_0,c_-]) cuts the boundary of 𝒞 at z_+ (resp. z_-), because r > √(2) d ϵ > 2 √(d)ϵ for d ≥ 2. 

 

We first consider the case where there exists a cube C' of the grid, adjacent to C such that z_+ ∈ C', then there exists F, facet of C' such that z_+ ∈ F (see Figure <ref>).

We first show that [B]^⋆(z_+) = +1 because the whole facet F is included in ℬ(c_+,r). Let c'_+ be the orthogonal projection of c_+ on the hyperplane H_F defined by F. The intersection of ∂ℬ(c_+,r) with H_F is a sphere ∂ℬ_F(c'_+, r') in H_F of centre c'_+. Let { w } = r⃗(c_+, z_+) ∩∂ℬ_F(c'_+,r'). w is the point of ∂ℬ(c_+,r) ∩ H_F which is the closest to z_+. We have (see Figure <ref>, panel (a)):


    z_+ - w = r sinβ/cosα.


where α is the angle defined by (c'_+, c_+, y_0) and β the angle defined by (y_0, c_+, w). The angle β is minimum when the distance from y_0 to F is ϵ. Indeed, if y_0 gets closer to H_F, keeping the same angle between H_F and c_+ - y_0, the radius r' of the sphere ∂ℬ_F(c'_+, r') decreases as well as the distance w - z_+ and so does β. Moreover, cosα is maximum at 1. With these values, we have:


    sinβ = √(1 - (r - ϵ/r)^2).


Therefore:

    z_+ - w≥√( r^2 - (r - ϵ)^2).


Then, expressing within equation <ref> that z_+ - w is larger than √(d-1)ϵ the maximum distance between two points in the facet, requires:

    r ≥dϵ/2,


Therefore, as we assumed r ≥√(2) dϵ this condition is satisfied, thus z_+ - w≥√(d-1)ϵ, implying that the whole facet F is included in ℬ(c_+,r) and [B]^⋆(z_+) = +1.

Similarly, if there exists a cube C' of the grid, adjacent to C and such that z_- ∈ C', then  [B]^⋆(z_-) = -1.

Because of propositions <ref> and <ref>, the segment [z_+,z_-] crosses the resistar (c-resistar or K-resistar) approximation [B]^⋆ defined in 𝒞 (with B = B_M(𝒞) or B = B_M^K(𝒞)). Let z ∈ [z_+,z_-] ∩ [B]^⋆. Noticing that P_y_0(z) = y_0 and applying lemma <ref>, we get: y_0 - z = 𝒪(d ϵ^2).

 


Now, we consider the case where the cube C is on the boundary of X and [y_0,c_+] crosses the boundary of X in d-1-dimensional facet F of C, before crossing the boundary of 𝒞. Let z_+ = [y_0,c_+] ∩ F. Two cases can take place:

	
  * [B]^⋆ (z_+) = +1, then the same reasoning as previously applies;
	
  * [B]^⋆ (z_+) = -1, is an error (because z_+ ∈ℬ(c_+,r)) and because of the induction hypothesis, there exists a point z in [B_M(F)]^⋆ or in [B_M^K(F)], such that z_+ - z  = 𝒪((d-1)ϵ^2). We have:
	
    P_y_0(z) - P_y_0(z_+)  = P_y_0(z) - y_0 = 𝒪((d-1) ϵ^2),
	
because the orthogonal projection is contracting, and:

    P_y_0(z) - z = 𝒪(d ϵ^2)

 because z - y_0≤√(d)ϵ and applying lemma <ref>. Therefore (see figure <ref>, panel (b)):

    y_0 - z≤y_0 - P_y_0(z)  + P_y_0(z) - z = 𝒪(d ϵ^2).



Of course, the same reasoning applies to the negative side [y,c_-].
This concludes the proof of theorem <ref>.
□ 





§ EXAMPLES AND TESTS.






 §.§ Visualisation of examples with spheres and radial based functions.



When the dimensionality d is higher than 3, the surface cannot be directly represented, but it is possible to visualise its intersection with d - 3	hyperplanes. Algorithm <ref> sketches the method. It is based on building polytopes whose vertices are the intersections of edges of another polytope with a hyperplane. Starting with a simplex of the resistar, a polytope of one dimension less is computed in this way successively with each of the hyperplanes. If the intersection of the resistar simplex with the intersection of the d-3 hyperplanes is not empty, the result is a 2D polygon in the 3D intersection of the d - 3 hyperplanes. These polygons define together a 2D surface in this 3D space.

 

Even though it is possible to focus on a small percentage of all the simplices of the resistar approximation that have chances to intersect with the intersection of all the hyperplanes, this small percentage may still correspond to a high number of simplices in some cases. This can occur easily when the dimensionality of the space is higher than 6, especially with K-resistars.   

Figure <ref> shows examples of approximations of a sphere in 5D with K-resistars (panel (b)) and in 6D with c-resistars (panel (a)), for n_G = 5 points on each axis of the grid. Note that the K-resistar includes a larger number of boundary points and even larger number of simplices, although it is in 5 dimensions while the c-resistar is in 6 dimensions. In 6 dimensions, the K-resistar approximating the same sphere for n_G = 5 involves 199,322 boundary points and 1.1 billion simplices. 
	
  


 	 
 	
 	
 		
			
 	
 	
 	
 


 	  


 
  	 
 	
 	
 		
 		 	
 	
 	
 	
 
 
In order to test more systematically our approach, we derived classifications from a radial-based function defined on two sets of randomly chosen points in the space E_p = {p_1, p_2,.., p_l} and E_n = {n_1, n_2,.., n_m}, as follows:

    ℳ(x) = (∑_i = 1^l ϕ(p_i - x/σ) - ∑_i = 1^m ϕ(n_i - x/σ)),

where σ is a positive number and function ϕ is defined by:

    ϕ(x) = 100/1 + x^2.


When varying the number of points in E_p and E_n and the value of σ, the resulting surface is more or less complicated and smooth. In our tests, we use two settings that are illustrated by Figure <ref>. 





 §.§ Testing the classification error when the grid size and the space dimensionality vary.


Generally, the accuracy of classification methods is measured by the misclassification rate of points randomly drawn in [0,1]^d. However, this measure requires drawing a very large number of test points when the dimensionality d of the space increases. In order to limit the number of tests, we generated the test points only in the cubes which include boundary points. This gives more chances to get misclassified points. Taking 100 test points in each cube containing boundary points, we used 50 million test points for the resistar approximation with the highest number of cubes in the following tests (in dimensionality 4 with n_G = 48).

 	

Figure <ref> shows that the classification error decreases like n_G^-2 for both K-resistars and c-resistars (estimated slopes in the log-log graph: -2.06, for K-resistars, -2.01 for c-resistars, with R^2 = 0.99 for both) in accordance with theorem <ref>, whereas the classification error of nearest vertex decreases like n_G^-1 (estimated slope in the log-log graph: -1.02, with R^2 = 0.99). It appears also that the error of K-resistars is significantly lower than the one of c-resistars, which is expected because K-resistars are based on a larger number of boundary points located on the edges of the Kuhn simplices. Note that the values of errors do not change significantly when the dimensionality changes.

This is confirmed by Figure <ref> which shows the classification error for nearest vertex, c-resistar and K-resistars approximating radial based classification functions with the same parameters (E_p and E_n equal to 10, σ = 0.4) and the same number of points by axis of the grid n_G = 4, in dimensionality varying from 3 to 9. For each dimensionality, the tests are repeated for 10 radial-based classification functions with points E_p and E_n drawn at random in [0,1]^d. The error percentage is computed by classifying 100 points uniformly drawn in each cube which includes boundary points. We observe that the error percentages do not vary significantly with the dimensionality whereas the bound on the Hausdorff distance should vary linearly with d. 

 

Figure <ref> shows the number of boundary points and simplices when the number of points of the grid or the dimensionality of the space vary. These graphs confirm the very rapid growth of the number of boundary points and of simplices, particularly in K-resistars. In 9 dimensions, for n_G =4, the number of boundary points of the K-resistar surface is around 10 million, and the number of simplices is around 10^14 (see panel (b)). There are about 100 times less boundary points and 10,000 times less simplices in the c-resistar surface. 
The estimation of the slope of the logarithm of the number of simplices as a function of the logarithm of n_G for the tests in dimensionality 3, 4 and 5 presented on Figure <ref> (see the case of dimensionality 4 on figure <ref> panel (a)) is reported in table <ref>. For c-resistars, the number of boundary points appears thus to grow like 𝒪(n_G^d-1). For K-resistars the slope is a bit higher than d-1 and the difference increases with the dimensionality. This is due to the number of edges in all the K-simplices in a cube which increases much more rapidly than the number of edges of the cube.



 		






§ DISCUSSION - CONCLUSION



This paper shows examples of simplex based approximation and classification in 9 dimensions, which has never been done with marching cube or Delaunay triangulation. Indeed, the resistar classification is achieved through a few projections on facets and faces of a cube while the other methods would require to test the position of the point to classify with respect to a large number of simplices. This advantage of resistars starts in low dimensionality and becomes decisive in higher dimensionality as the number of simplices increases exponentially. 

The classification methods used in the algorithms of viability kernel approximation, such as nearest vertex, SVM or k-d trees, are based only on the classification of the vertices of a regular grid, hence their error cannot decrease more than 𝒪(n_G^-1) which is the intrinsic error in the learning sample. Resistar approximation does better because it is based on the boundary points which can be at a precision of 𝒪(n_G^-2) with an adequate number of dichotomies. Some other methods, for instance decision trees <cit.> could possibly be modified to learn efficiently from boundary points, but such a modification does not seem immediate. This specificity of resistar approximations allows them to ensure, under arguably reasonable conditions, that their Hausdorff distance to the manifold to approximate decreases like 𝒪(n_G^-2). This is a very significant advantage over current methods. Indeed, the resistar classification from the a grid of n_G^d points has the same accuracy as a standard classification based on a grid of (n_G^2)^d points. 

Computing the boundary points of resistars requires first classifying by ℳ the n_G^d grid points. Then, for c-resistars which generate 𝒪(n_G^d-1) boundary points, there are in total 𝒪 (q. n_G^d-1) point classifications by ℳ, because of the q successive dichotomies necessary to compute each boundary point. If q = log_2 (n_G) as in Theorem <ref>, the number of point classifications by ℳ required by c-resistars is n_G^d + log(n_G). n_G^d-1, which is very significantly lower than the  n_G^2d grid vertex classifications required by standard methods to get the same accuracy. For K-resistars, the number of boundary points increases also approximately like 𝒪 (n_G^d-1) in low dimensionality, but this number may be closer to 𝒪(n_G^d) in dimensionality 8 or 9. Overall, the number of classifications by ℳ remains still very significantly lower than the one required by usual methods to get the same accuracy. Considering the requirements in memory space, the advantage of resistars is very strong over the nearest vertex classification which needs to store the whole grid of n_G^2d points (or with some optimisation 𝒪(n_G^2d-1) points) whereas the c-resistars need to store 𝒪(n_G^d-1) boundary points and K-resistars at worst 𝒪(n_G^d), to get the same accuracy.

The two variants of resistars have different strengths and weaknesses. The K-resistars approximations have the major advantage to be manifolds and their error rate is lower than the one of the c-resistars for a given grid size. However, the c-resistars are significantly lighter, especially when the dimensionality increases. In some cases, it is possible to use them while the K-resistars are too heavy. 

For both of them, the accuracy in 𝒪(n_G^-2) requires the manifold to approximate to be smooth, which is not always the case in viability problems. This manifold is indeed often the boundary of the intersection of several smooth manifolds, hence with a reach equal to zero. A challenging future work is to define new types of resistars approximating these intersections with an accuracy of 𝒪(n_G^-2) and with an efficient classification algorithm.






§ ACKNOWLEDGMENT
 

I am grateful to Sophie Martin and Isabelle Alvarez for their helpful comments and suggestions on earlier versions of the paper.





§ REFERENCES
 

elsarticle-num





