کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10327625 | 681260 | 2005 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Extremal point queries with lines and line segments and related problems
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We address a number of extremal point query problems when P is a set of n points in Rd, d⩾3 a constant, including the computation of the farthest point from a query line and the computation of the farthest point from each of the lines spanned by the points in P. In R3, we give a data structure of size O(n1+É), that can be constructed in O(n1+É) time and can report the farthest point of P from a query line segment in O(n2/3+É) time, where É>0 is an arbitrarily small constant. Applications of our results also include: (1) Sub-cubic time algorithms for fitting a polygonal chain through an indexed set of points in Rd, d⩾3 a constant, and (2) A sub-quadratic time and space algorithm that, given P and an anchor point q, computes the minimum (maximum) area triangle defined by q with Pâ{q}.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 32, Issue 3, November 2005, Pages 223-237
Journal: Computational Geometry - Volume 32, Issue 3, November 2005, Pages 223-237
نویسندگان
Ovidiu Daescu, Robert Serfling,