An output-sensitive algorithm to compute the normal vector of a digital plane

Abstract

A digital plane is the set of integer points located between to parallel planes. We solve the following problem: how to compute the exact normal vector of a digital plane given only a predicate that answers the question “is a point x in the digital plane or not”. Our approach is iterative and “as local as possible”. We provide a worst-case complexity bound in O(ω log ω) calls to the predicate, where ω is equal to the arithmetic thickness parameter of the digital plane. Furthermore, our algorithm presents a much better average behavior in practice.

Jacques-Olivier Lachaud

Professor of Computer Science

My research interests include digital geometry, geometry processing, image analysis, variational models and discrete calculus.