کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949560 | 1440195 | 2017 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Rectilinear path problems in restricted memory setup
ترجمه فارسی عنوان
مشکلات مسیر خطی در تنظیم مجدد حافظه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
مشکل مسیر خط مستقیم، مدل محاسبات در محل و فقط خواندنی، فضای کار ثابت،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
The objective of the Path-Query (p,q) in the in-place setup is to preprocess the input rectangles in a data structure in the input array itself such that for any pair of query points p and q, a rectilinear path can be reported efficiently. Here we propose an algorithm with O(nlogn) preprocessing time and O(n3/4+Ï) query time, where Ï is the number of links (bends) in the path. Both the preprocessing and query answering need O(1) extra space.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 228, 10 September 2017, Pages 80-87
Journal: Discrete Applied Mathematics - Volume 228, 10 September 2017, Pages 80-87
نویسندگان
Binay K. Bhattacharya, Minati De, Anil Maheshwari, Subhas C. Nandy, Sasanka Roy,