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.
Type
Publication
Theor. Comput. Sci., 624: 73-88, 2016
Digital Geometry
Digital Planarity
Recognition
Multidimensional Continued Fractions
Delaunay Triangulation
Authors
Professor of Computer Science
My research interests include digital geometry, geometry processing, image analysis, variational models and discrete calculus.