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

作者：Lachaud Jacques Olivier; Provencal Xavier^*; Roussillon Tristan

来源：Theoretical Computer Science, 2016, 624: 73-88.

DOI：10.1016/j.tcs.2015.11.021

• Digital geometry
• Digital plane
• Recognition
• Multidimensional continued fractions
• Delaunay triangulation

A digital plane is the set of integer points located between the 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(omega log omega) calls to the predicate, where omega is equal to the arithmetic thickness parameter of the digital plane. Furthermore, our algorithm presents a much better average behavior in practice.

• 出版日期2016-4-18