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 originale | Anglais |
|---|---|
| Pages (de - à) | 73-88 |
| Nombre de pages | 16 |
| Revue | Theoretical Computer Science |
| Volume | 624 |
| Les DOIs | |
| État | Publié - 18 avr. 2016 |
| Modification externe | Oui |
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
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver