A Greedy Algorithm for Constructing Region-Fault Tolerant Geometric Spanners
In this paper, we consider the problem of constructing the region-fault tolerant geometric spanners when the problem is restricted to a subclass of convex regions. Let S be a set of n points in the plane. In particular, in this paper, a greedy algorithm for constructing the region-fault tolerant geometric spanner of S where the region faults are a set of at most k half-planes with parallel boundaries is presented. We show that the proposed algorithm has the time complexity O(kn^3 logn ), and the generated graph contains O(kn) edges. To the best of our knowledge, the best-known algorithm to construct the region-fault tolerant geometric spanner of S takes O(n log^2n) time and the generated graph has O(n logn) edges.
- حق عضویت دریافتی صرف حمایت از نشریات عضو و نگهداری، تکمیل و توسعه مگیران میشود.
- پرداخت حق اشتراک و دانلود مقالات اجازه بازنشر آن در سایر رسانههای چاپی و دیجیتال را به کاربر نمیدهد.