کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6868422 | 1439974 | 2018 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Time-space trade-offs for triangulations and Voronoi diagrams
ترجمه فارسی عنوان
ترکیب فضای زمان و فضا برای سه گانه و نمودارهای ورنونی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Let S be a planar n-point set. A triangulation for S is a maximal plane straight-line graph with vertex set S. The Voronoi diagram for S is the subdivision of the plane into cells such that all points in a cell have the same nearest neighbor in S. Classically, both structures can be computed in O(nlogâ¡n) time and O(n) space. We study the situation when the available workspace is limited: given a parameter sâ{1,â¦,n}, an s-workspace algorithm has read-only access to an input array with the points from S in arbitrary order, and it may use only O(s) additional words of Î(logâ¡n) bits for reading and writing intermediate data. The output should then be written to a write-only structure. We describe a deterministic s-workspace algorithm for computing an arbitrary triangulation of S in time O(n2/s+nlogâ¡nlogâ¡s) and a randomized s-workspace algorithm for finding the Voronoi diagram of S in expected time O((n2/s)logâ¡s+nlogâ¡slogââ¡s).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 73, August 2018, Pages 35-45
Journal: Computational Geometry - Volume 73, August 2018, Pages 35-45
نویسندگان
Matias Korman, Wolfgang Mulzer, André van Renssen, Marcel Roeloffzen, Paul Seiferth, Yannik Stein,