A compact data structure for high dimensional Coxeter-Freudenthal-Kuhn triangulations

Jean-Daniel Boissonnat (1) , Siargey Kachanovich (1) , Mathijs Wintraecken (2)

1 DATASHAPE - Understanding the Shape of Data
2 IST Austria - Institute of Science and Technology [Klosterneuburg, Austria]

We consider a family of highly regular triangulations of Rd that can be stored and queried efficiently in high dimensions. This family consists of Freudenthal-Kuhn triangulations and their images through affine mappings, among which are the celebrated Coxeter triangulations of type Ãd. Those triangulations have major advantages over grids in applications in high dimensions like interpolation of functions and manifold sampling and meshing. We introduce an elegant and very compact data structure to implicitly store the full facial structure of such triangulations. This data structure allows to locate a point and to retrieve the faces or the cofaces of a simplex of any dimension in an output sensitive way. The data structure has been implemented and experimental 9 results are presented.

Mots clés: Spatial subdivisions; High dimensional computational geometry; Coxeter triangulation; Kuhn triangulation; Permutahedrons

Domaines: Géométrie algorithmique [cs.CG]; Algorithme et structure de données [cs.DS]; Topologie algébrique [math.AT]; Topologie géométrique [math.GT]

Jean-Daniel Boissonnat, Siargey Kachanovich, Mathijs Wintraecken. A compact data structure for high dimensional Coxeter-Freudenthal-Kuhn triangulations. 2020. ⟨hal-03006608⟩