کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
414425 680933 2008 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Visibility maps of segments and triangles in 3D
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Visibility maps of segments and triangles in 3D
چکیده انگلیسی

Let T be a set of n triangles in three-dimensional space, let s be a line segment, and let t be a triangle, both disjoint from T. We consider the subdivision of T based on (in)visibility from s; this is the visibility map of the segment s with respect to T. The visibility map of the triangle t is defined analogously. We look at two different notions of visibility: strong (complete) visibility, and weak (partial) visibility. The trivial Ω(n2) lower bound for the combinatorial complexity of the strong visibility map of both s and t is almost tight: we prove an O(n2α(n)) upper bound for both structures, where α(n) is the extremely slowly increasing inverse Ackermann function. Furthermore, we prove that the weak visibility map of s has complexity Θ(n5), and the weak visibility map of t has complexity Θ(n7). If T is a polyhedral terrain, the complexity of the weak visibility map is Ω(n4) and O(n5), both for a segment and a triangle. We also present efficient algorithms to compute all discussed structures.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 39, Issue 3, April 2008, Pages 163-177