A fast and elementary algorithm for digital plane recognition

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 with integer coefficients is a subset of points (x,y,z) in Z^3 verifying a double inequality h <= ax+by+cz < h + max{ | a|,|b|, |c| } where a,b,c and h are integer numbers. Given a finite subset of Z^3, a problem is to determine whether or not 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 for solving it. It uses an original strategy of optimization in a set of triangular facets (called triangles). The code is short and elementary (less than 300 lines) and available on http://www.loria.fr/~debled/plane. Its theoretical complexity is bounded by $O( n^7)$ but its behavior is quasi-linear in practice.
Type de document :
Rapport
[Intern report] A03-R-332 || gerard03a, 2003, 16 p
Liste complète des métadonnées

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

Identifiants

  • HAL Id : inria-00099772, version 1

Citation

Yan Gérard, Isabelle Debled-Rennesson, Paul Zimmermann. A fast and elementary algorithm for digital plane recognition. [Intern report] A03-R-332 || gerard03a, 2003, 16 p. 〈inria-00099772〉

Partager

Métriques

Consultations de la notice

180