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 language | English |
|---|---|
| Pages (from-to) | 73-88 |
| Number of pages | 16 |
| Journal | Theoretical Computer Science |
| Volume | 624 |
| DOIs | |
| Publication status | Published - 18 Apr 2016 |
| Externally published | Yes |
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
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver