An elementary digital plane recognition algorithm Original Research Article

A naive digital plane is a subset of points image verifying image, where image. Given a finite unstructured subset of image, 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 image 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 .