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

详细信息    查看全文

• 作者：Jacques-Olivier Lachaud^a ; ^{jacques-olivier.lachaud@univ-savoie.fr" class="auth_mail" title="E-mail the corresponding author} ; Xavier Provenç ; al^a ; ^{xavier.provencal@univ-savoie.fr" class="auth_mail" title="E-mail the corresponding author} ; Tristan Roussillon^b ; ^{tristan.roussillon@insa-lyon.fr" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Digital geometry ; Digital plane ; Recognition ; Multidimensional continued fractions ; Delaunay triangulation
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：18 April 2016
• 年：2016
• 卷：624
• 期：Complete
• 页码：73-88
• 全文大小：1788 K

文摘

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 class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397515010828&_mathId=si1.gif&_user=111111111&_pii=S0304397515010828&_rdoc=1&_issn=03043975&md5=7be952c2290c6632e14e14be6fc1c225" title="Click to view the MathML source">O(ωlog⁡ω)class="mathContainer hidden">class="mathCode">$\mathcal{O}(\omega \log \omega )$ 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.