کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10327393 | 681023 | 2013 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
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) 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) 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) time.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 46, Issue 8, October 2013, Pages 959-969
Journal: Computational Geometry - Volume 46, Issue 8, October 2013, Pages 959-969
نویسندگان
Tetsuo Asano, Kevin Buchin, Maike Buchin, Matias Korman, Wolfgang Mulzer, Günter Rote, André Schulz,