Approximation algorithms with guaranteed performance for the intersection of edge sets of some metric graphs with equal disks

Abstract

Polynomial-time approximation algorithms with constant approximation ratio are proposed for the problem of intersection of a given set of n planar straight line segments with the least number of equal disks. In the case where the segments have at most k different orientations, a simple 4k-approximate algorithm with time complexity O(n log n) is known. In addition, a 100-approximate algorithm with time complexity O(n4 log n) is known for the case of the problem on the edge sets of plane graphs. In this paper, for instances of the problem on the edge sets of Gabriel graphs, relative neighbourhood graphs, and Euclidean minimum spanning trees, in which the number of different edge orientations is, in general, unbounded, we construct simple O(n2)-time approximation algorithms with approximation ratios 14, 12, and 10, respectively. These algorithms outperform the aforementioned approximation algorithm for the general setting of the problem for edge sets of plane graphs. © 2019 Krasovskii Institute of Mathematics and Mechanics. All rights reserved.