کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
433817 | 689633 | 2016 | 16 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An output-sensitive algorithm to compute the normal vector of a digital plane
ترجمه فارسی عنوان
یک الگوریتم حساس خروجی برای محاسبه بردار عادی یک صفحه دیجیتال؟
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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ω)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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 624, 18 April 2016, Pages 73–88
Journal: Theoretical Computer Science - Volume 624, 18 April 2016, Pages 73–88
نویسندگان
Jacques-Olivier Lachaud, Xavier Provençal, Tristan Roussillon,