کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6868422 1439974 2018 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Time-space trade-offs for triangulations and Voronoi diagrams
ترجمه فارسی عنوان
ترکیب فضای زمان و فضا برای سه گانه و نمودارهای ورنونی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
نویسندگان
, , , , , ,