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.
Document type :
Reports
Complete list of metadatas

https://hal.inria.fr/inria-00099772
Contributor : Publications Loria <>
Submitted on : Tuesday, September 26, 2006 - 9:41:06 AM
Last modification on : Wednesday, April 3, 2019 - 3:38:03 PM

Identifiers

  • 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⟩

Share

Metrics

Record views

248