کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4949560 1440195 2017 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Rectilinear path problems in restricted memory setup
ترجمه فارسی عنوان
مشکلات مسیر خطی در تنظیم مجدد حافظه
کلمات کلیدی
مشکل مسیر خط مستقیم، مدل محاسبات در محل و فقط خواندنی، فضای کار ثابت،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
نویسندگان
, , , , ,