Passer à la navigation principale Passer à la recherche Passer au contenu principal

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

  • CNRS
  • Institut national des sciences appliquées Lyon

Résultats de recherche: Contribution à un journal › Article publié dans une revue, révisé par les pairs › Revue par des pairs

11 Citations (Scopus)

Résumé

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(ω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.

Langue originaleAnglais
Pages (de - à)73-88
Nombre de pages16
RevueTheoretical Computer Science
Volume624
Les DOIs
ÉtatPublié - 18 avr. 2016
Modification externeOui

Classification disciplinaire ASJC Scopus

  • Informatique théorique
  • Informatique générale

Empreinte digitale

Voici les principaux termes ou expressions associés à « An output-sensitive algorithm to compute the normal vector of a digital plane ». Ces libellés thématiques sont générés à partir du titre et du résumé de la publication. Ensemble, ils forment une empreinte digitale unique.

Citer cette ressource