Orientations of Simplices Determined by Orderings on the Coordinates of their Vertices

Emeric Gioan 1 Kevin Sol 1 Gérard Subsol 2
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 ICAR - Image & Interaction
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We address the problem of testing when orderings on coordinates of n points in an (n-1)-dimensional affine space, one ordering for each coordinate, suffice to determine if these points are the vertices of a simplex (i.e. are affinely independent), and the orientation of this simplex, independently of the real values of the coordinates. In other words, we want to know when the sign (or the non-nullity) of the determinant of a matrix whose columns correspond to affine points is determined by orderings given on the values on each row. We completely solve the problem in dimensions 2 and 3, providing a direct combinatorial characterization, together with a formal calculus method, that can be seen also as a decision algorithm, which relies on testing the existence of a suitable inductive cofactor expansion of the determinant. We conjecture that the method we use generalizes in higher dimensions. The motivation for this work is to be part of a study on how oriented matroids encode shapes of 3-dimensional objects, with applications in particular to the analysis of anatomical data for physical anthropology and clinical research.
Type de document :
Communication dans un congrès
CCCG: Canadian Conference on Computational Geometry, Aug 2011, Toronto, Canada. 23rd Canadian Conference on Computational Geometry, 2011, 〈http://2011.cccg.ca/〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00741936
Contributeur : Kevin Sol <>
Soumis le : lundi 15 octobre 2012 - 15:20:19
Dernière modification le : jeudi 11 janvier 2018 - 06:26:18

Identifiants

  • HAL Id : lirmm-00741936, version 1

Citation

Emeric Gioan, Kevin Sol, Gérard Subsol. Orientations of Simplices Determined by Orderings on the Coordinates of their Vertices. CCCG: Canadian Conference on Computational Geometry, Aug 2011, Toronto, Canada. 23rd Canadian Conference on Computational Geometry, 2011, 〈http://2011.cccg.ca/〉. 〈lirmm-00741936〉

Partager

Métriques

Consultations de la notice

152