Skip to main navigation Skip to search Skip to main content

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

  • CNRS
  • Institut national des sciences appliquées Lyon

Research output: Contribution to journal › Journal Article › peer-review

11 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)73-88
Number of pages16
JournalTheoretical Computer Science
Volume624
DOIs
Publication statusPublished - 18 Apr 2016
Externally publishedYes

Keywords

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'An output-sensitive algorithm to compute the normal vector of a digital plane'. These topics are generated from the title and abstract of the publication. Together, they form a unique fingerprint.

Cite this