A fast and elementary algorithm for digital plane recognition

Rapport interne.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