@inproceedings{d011515585a64e969d323d3e201cabd7,
title = "Computation of the normal vector to a digital plane by sampling significant points",
abstract = "Digital planes are sets of integer points located between two parallel planes. We present a new algorithm that computes the normal vector of a digital plane given only a predicate {\textquotedblleft}is a point x in the digital plane or not{\textquotedblright}. In opposition with the algorithm presented in [7], the algorithm is fully local and does not explore the plane. Furthermore its worst-case complexity bound is O(ω), where ω is the arithmetic thickness of the digital plane. Its only restriction is that the algorithm must start just below a Bezout point of the plane in order to return the exact normal vector. In practice, our algorithm performs much better than the theoretical bound, with an average behavior close to O(log ω). We show further how this algorithm can be used to analyze the geometry of arbitrary digital surfaces, by computing normals and identifying convex, concave or saddle parts of the surface.",
keywords = "Digital geometry, Digital plane, Lattice reduction, Normal vector estimation, Recognition",
author = "Lachaud, \{Jacques Olivier\} and Xavier Proven{\c c}al and Tristan Roussillon",
note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2016.; 19th IAPR International Conference on Discrete Geometry for Computer Imagery, DGCI 2016 ; Conference date: 18-04-2016 Through 20-04-2016",
year = "2016",
doi = "10.1007/978-3-319-32360-2\_15",
language = "English",
isbn = "9783319323596",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "194--205",
editor = "Nicolas Normand and Jeanpierre Gu{\'e}don and Florent Autrusseau",
booktitle = "Discrete Geometry for Computer Imagery - 19th IAPR International Conference, DGCI 2016, Proceedings",
}