کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
414154 | 680818 | 2016 | 20 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Optimal time-convex hull for a straight-line highway in Lp-metrics
ترجمه فارسی عنوان
بدنه محدب ـ زمانی بهینه برای یک بزرگراه خط مستقیم در معیارهای LP
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
بدنه محدب بهینه؛ فاصله زمانی؛ معیارهای LpLp
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We consider the problem of computing the time-convex hull of a point set under the general LpLp metric in the presence of a straight-line highway in the plane. The traveling speed along the highway is assumed to be faster than that off the highway, and the shortest time-path between a distant pair may involve traveling along the highway. The time-convex hull TCH(P)TCH(P) of a point set P is the smallest set containing both P and all shortest time-paths between any two points in TCH(P)TCH(P). In this paper we give an algorithm that computes the time-convex hull under the LpLp metric in optimal O(nlogn)O(nlogn) time for a given set of n points and a real number p with 1≤p≤∞1≤p≤∞.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 53, February 2016, Pages 1–20
Journal: Computational Geometry - Volume 53, February 2016, Pages 1–20
نویسندگان
Bang-Sin Dai, Mong-Jen Kao, D.T. Lee,