کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6868562 | 681182 | 2016 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Optimal randomized incremental construction for guaranteed logarithmic planar point location
ترجمه فارسی عنوان
ساختار افزایشی به طور تصادفی بهینه برای مکان نقطه تخت لگاریتمی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
مکان نقطه، ساختار افزایشی تصادفی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Given a planar map of n segments in which we wish to efficiently locate points, we present the first randomized incremental construction of the well-known trapezoidal-map search-structure that only requires expected O(nlogâ¡n) preprocessing time while deterministically guaranteeing worst-case linear storage space and worst-case logarithmic query time. The best previously known randomized construction time of the search structure, which is based on a directed acyclic graph, so-called the history DAG, and with the above worst-case space and query-time guarantees, was expected O(nlog2â¡n). The result is based on a deeper understanding of the structure of the history DAG, its depth in relation to the length of its longest search path, as well as its correspondence to the trapezoidal search tree. Our results immediately extend to planar maps induced by finite collections of pairwise interior disjoint well-behaved curves.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 58, October 2016, Pages 110-123
Journal: Computational Geometry - Volume 58, October 2016, Pages 110-123
نویسندگان
Michael Hemmer, Michal Kleinbort, Dan Halperin,