Facet Connectedness of Arithmetic Discrete Hyperplanes with Non-Zero Shift

Eric Domenjoud (1) , Bastien Laboureix (2) , Laurent Vuillon (3)

1 ADAGIO - Applying Discrete Algorithms to Genomics and Imagery
2 ENS Cachan - École normale supérieure - Cachan
3 LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications

We present a criterion for the arithmetic discrete hyperplane Open image in new window to be facet connected when θ is the connecting thickness Open image in new window . We encode the shift μ in a numeration system associated with the normal vector Open image in new window and we describe an incremental construction of the plane based on this encoding. We deduce a connectedness criterion and we show that when the Fully Subtractive algorithm applied to Open image in new window has a periodic behaviour, the encodings of shifts μ for which the plane is connected may be recognised by a finite state automaton.

Mots clés: Discrete hyperplane; Connectedness; Connecting thickness; Fully subtractive algorithm; Numeration system; Finite state automaton

Domaines: Mathématique discrète [cs.DM]

Eric Domenjoud, Bastien Laboureix, Laurent Vuillon. Facet Connectedness of Arithmetic Discrete Hyperplanes with Non-Zero Shift. DGCI 2019: 21st International Conference on Discrete Geometry for Computer Imagery, Mar 2019, Paris, France. pp.38-50, ⟨10.1007/978-3-030-14085-4_4⟩. ⟨hal-02316870⟩