کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
414261 | 680868 | 2015 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Weak visibility queries of line segments in simple polygons
ترجمه فارسی عنوان
نمایش مشخصات ضعف در قسمتهای خط در چند ضلعی ساده
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
چند ضلعی قابل مشاهده دیدگاه ضعیف از بخش های خط، نمایش مشخصات قضیه منطقه
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Given a simple polygon P in the plane, we present new data structures for computing the weak visibility polygon from any query line segment in P . We build a data structure in O(n)O(n) time and space that can compute the visibility polygon for any query line segment s in O(klogn)O(klogn) time, where k is the size of the visibility polygon of s and n is the number of vertices of P . Alternatively, we build a data structure in O(n3)O(n3) time and space that can compute the visibility polygon for any query line segment in O(k+logn)O(k+logn) time. In order to develop these data structures, we obtain many other results that may be interesting in their own right.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 48, Issue 6, August 2015, Pages 443–452
Journal: Computational Geometry - Volume 48, Issue 6, August 2015, Pages 443–452
نویسندگان
Danny Z. Chen, Haitao Wang,