An elementary digital plane recognition algorithm

Yan Gérard 1 Isabelle Debled-Rennesson 2 Paul Zimmermann 3
2 ADAGE - Applying discrete algorithms to genomics
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
3 SPACES - Solving problems through algebraic computation and efficient software
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : A naive digital plane is a subset of points $(x,y,z) \in \mathbb{Z} ^3$ verifying $h\leq ax+by+cz < h+\rm{ max }\{ | a|,|b|,|c| \}$ where $(a,b,c,h)\in \mathbb{Z} ^4 $. Given a finite unstructured subset of $\mathbb{Z} ^3$, the problem of the digital plane recognition is to determine whether there exists a naive digital plane containing it. This question is rather classical in the field of digital geometry (also called discrete geometry). We suggest in this paper a new algorithm to solve it. Its asymptotic complexity is bounded by $O( n^7)$ but its behavior seems to be linear in practice. It uses an original strategy of optimization in a set of triangular facets (triangles). The code is short and elementary (less than 300 lines) and available on \url{http://www.loria.fr/~debled/plane}.
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2004, 17 p
Liste complète des métadonnées

https://hal.inria.fr/inria-00100057
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 10:13:44
Dernière modification le : jeudi 11 janvier 2018 - 06:20:00

Identifiants

  • HAL Id : inria-00100057, version 1

Citation

Yan Gérard, Isabelle Debled-Rennesson, Paul Zimmermann. An elementary digital plane recognition algorithm. Discrete Applied Mathematics, Elsevier, 2004, 17 p. 〈inria-00100057〉

Partager

Métriques

Consultations de la notice

218