A Geometric Theorem for Approximate Disk Covering Algorithms
Massimo Franceschetti, Matthew Cook, Jehoshua Bruck · 2001
We present a basic theorem in combinatorial geometry that leads to a family of approximation algorithms for the the geometric disk covering problem. These algorithms exhibit constant approximation factors, with a wide range of their choices. This exibility allows to achieve a running time that compares favourably with those of existing procedures. 1 Introduction and Main Results In this paper we present a basic theorem in combinatorial geometry and discuss its application to the well known problem of computing a geometric disk covering [1]. The theorem states as follows: Theorem 1 Consider a square lattice where the distance between two neighboring lattice vertices is one. Call a disk of xed radius r , centered at a lattice vertex, a grid disk. The number N of grid disks that are necessary and sucient to cover any disk of radius r placed on the plane, is given by: CASE 1. For r < p 2 2 , N does not exist. CASE 2. For p 2 2 r < p 10 4 , N = 6. CASE 3. For p 10 4...