کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
414224 | 680850 | 2014 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Computing a visibility polygon using few variables
ترجمه فارسی عنوان
محاسبه چند ضلعی قابل مشاهده با استفاده از چند متغیر
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
هندسه محاسباتی، الگوریتم های محدوده حافظه، دید در زمان و فضا، چند ضلعی ساده
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We present several algorithms for computing the visibility polygon of a simple polygon PP of n vertices (out of which r are reflex) from a viewpoint inside PP, when PP resides in read-only memory and only few working variables can be used. The first algorithm uses a constant number of variables, and outputs the vertices of the visibility polygon in O(nr¯) time, where r¯ denotes the number of reflex vertices of PP that are part of the output. Whenever we are allowed to use O(s)O(s) variables, the running time decreases to O(nr2s+nlog2r) (or O(nr2s+nlogr) randomized expected time), where s∈O(logr). This is the first algorithm in which an exponential space-time trade-off for a geometric problem is obtained.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 47, Issue 9, October 2014, Pages 918–926
Journal: Computational Geometry - Volume 47, Issue 9, October 2014, Pages 918–926
نویسندگان
Luis Barba, Matias Korman, Stefan Langerman, Rodrigo I. Silveira,