کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9654918 | 680905 | 2005 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Ray shooting and stone throwing with near-linear storage
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
The paper presents two algorithms involving shooting in three dimensions. We first present an algorithm for performing ray shooting amid several special classes of n triangles in three dimensions, including sets of fat triangles, and sets of triangles stabbed by a common line. In all these special cases, our technique requires near-linear preprocessing and storage, and answers a query in O(n2/3+É) time. This improves the best known result of O(n3/4+É) query time (with near-linear storage) for general triangles. The second algorithm handles stone-throwing amid arbitrary triangles in 3-space, where the curves along which we shoot are vertical parabolic arcs that are trajectories of stones thrown under gravity. We present an algorithm that answers stone-throwing queries in O(n3/4+É) time, using near linear storage and preprocessing. As far as we know, this is the first nontrivial solution of this problem. Several extensions of both algorithms are also presented.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 30, Issue 3, March 2005, Pages 239-252
Journal: Computational Geometry - Volume 30, Issue 3, March 2005, Pages 239-252
نویسندگان
Micha Sharir, Hayim Shaul,