کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
433733 | 689618 | 2016 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Two dimensional range minimum queries and Fibonacci lattices
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Given a matrix of size N , two dimensional range minimum queries (2D-RMQs) ask for the position of the minimum element in a rectangular range within the matrix. We study trade-offs between the query time and the additional space used by indexing data structures that support 2D-RMQs. Using a novel technique—the discrepancy properties of Fibonacci lattices—we give an indexing data structure for 2D-RMQs that uses O(N/c)O(N/c) bits additional space with O(clogc(loglogc)2)O(clogc(loglogc)2) query time, for any parameter c , 4≤c≤N4≤c≤N. Also, when the entries of the input matrix are from {0,1}{0,1}, we show that the query time can be improved to O(clogc)O(clogc) with the same space usage.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 638, 25 July 2016, Pages 33–43
Journal: Theoretical Computer Science - Volume 638, 25 July 2016, Pages 33–43
نویسندگان
Gerth Stølting Brodal, Pooya Davoodi, Moshe Lewenstein, Rajeev Raman, Srinivasa Rao Satti,