کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
414682 | 681004 | 2014 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Reprint of: Memory-constrained algorithms for simple polygons
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
A constant-work-space algorithm has read-only access to an input array and may use only O(1)O(1) additional words of O(logn) bits, where n is the input size. We show how to triangulate a plane straight-line graph with n vertices in O(n2)O(n2) time and constant work-space. We also consider the problem of preprocessing a simple polygon P for shortest path queries, where P is given by the ordered sequence of its n vertices. For this, we relax the space constraint to allow s words of work-space. After quadratic preprocessing, the shortest path between any two points inside P can be found in O(n2/s)O(n2/s) time.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 47, Issue 3, Part B, April 2014, Pages 469–479
Journal: Computational Geometry - Volume 47, Issue 3, Part B, April 2014, Pages 469–479
نویسندگان
Tetsuo Asano, Kevin Buchin, Maike Buchin, Matias Korman, Wolfgang Mulzer, Günter Rote, André Schulz,