کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
414589 680983 2016 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
An almost optimal algorithm for Voronoi diagrams of non-disjoint line segments
ترجمه فارسی عنوان
یک الگوریتم تقریبا بهینه برای نمودارهای ورونوی بخش های خط غیرمتلاشی
کلمات کلیدی
نمودار Voronoi؛ بخش های خط؛ چند ضلعی ضعیف ساده؛ چند ضلعی با سوراخ؛ محور میانی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

This paper presents an almost optimal algorithm that computes the Voronoi diagram of a set S of n line segments that may intersect or cross each other. If there are k intersections among the input segments in S  , our algorithm takes O(nα(n)log⁡n+k)O(nα(n)log⁡n+k) time, where α(⋅)α(⋅) denotes the inverse of the Ackermann function. The best known running time prior to this work was O((n+k)log⁡n)O((n+k)log⁡n). Since the lower bound of the problem is shown to be Ω(nlog⁡n+k)Ω(nlog⁡n+k) in the worst case, our algorithm is worst-case optimal for k=Ω(nα(n)log⁡n)k=Ω(nα(n)log⁡n), and is only a factor of α(n)α(n) away from any optimal-time algorithm, which is still unknown. For the purpose, we also present an improved algorithm that computes the medial axis or the Voronoi diagram of a polygon with holes.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 52, February 2016, Pages 34–43
نویسندگان
,