A fast and elementary algorithm for digital plane recognition

A digital naive plane is a subset of points (x, y, z) ∈ Z3 verifying a double inequality h ≤ ax + by + cz < h + max{∣a∣, ∣b∣, ∣c∣} where (a, b, c) ∈ R/{(0,0,0)} and h ∈ R. Given a finite subset of Z3, a problem is to determine whether or not there exists a digital naive 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 2-simplexes called triangles and an original strategy of optimization. The code is short and elementary (less than 300 lines). Its theoritical complexity is bounded by O(n7) but its behaviour is quasi-linear in practice.