Site menu:
Disc coverings
Given a set of points in the plane, we seek a set of discs that cover all the points. The discs are allowed to overlap. Usually we wish to use as few discs as possible - this is the minimal disc covering problem.
There are many variants of this problem. For example, the Euclidean p-centre problem fixes the number of discs and seeks the minimum disc radius that is needed to obtain a covering. Or we can fix both the number and radius of the discs and seek to maximize the number of points that can be covered. Ref [1] gives a good overview of the topic.
The minimal disc covering problem is hard computationally (technically, strongly NP-complete). Various polynomial-time approximation schemes have been proposed. These are algorithms that run in polynomial time and guarantee to find a covering that requires no more than q times the true minimum number of discs, irrespective of the spatial distribution of the points. However, it is hard to get q at all close to one whilst maintaining reasonable computational time. Ref [2] gives an algorithm with q=2.8334 that is 'almost linear' in the number of points, but no details of actual run times are given. Ref [3] gives a brief overview of algorithms of this type.
Heuristic randomised algorithms
I have developed some randomised algorithms that simply attempt to generate 'reasonable' coverings. By running these algorithms multiple times and selecting the best solution, one can generally come close to a true minimal solution.
The algorithms proceed sequentially by identifying points that have not yet been covered a finding a disc that covers the point identified. The greedy approach of always selecting the disc that covers as many of the remaining points as possible can give poor results. Instead, we pick points randomly. Once a point is identified, there are different ways of finding a covering disc, giving rise to different variants of the basic algorithm. These are described in Ref [3].
Unlike the polynomial time schemes, this approach gives no guarantees about the quality of the solution. However, the algorithms seem to perform quite well in practice. Two advantages are that
- the algorithms are reasonably simple to program
- the computational effort can be varied (by setting the number of repetitions) depending on how important it is to find an accurate solution.
Applications
A classical application is to facility location. Here the points represent populations and we wish to locate facilities (schools, hospitals, etc) so that the distance from each population to its nearest facility is no more than r; this is achieved if the facilities are placed at the centres of the discs. More recent applications are to wireless networks.
My own interest arose in connection with a problem in ecology. The minimal disc problem provides a solution to the following problem. Suppose we have a set of animal marks (eg footprints) where it is impossible to identify individual animals (i.e. we cannot say whether or not two marks were made by the same animal). Suppose that individual animals move within circular areas (home ranges) of specified radius. What is the minimum number of animals that could have made the marks? Ref [3] gives an application to pugmarks made by the Sumatran tiger.
References
[1] Agarwal, P.K. and Sharir, M. (1998) Efficient algorithms for geometric optimiization. ACM Computing Surveys, 30, 412-48.
[2] Fu, B., Chen, Z. and Abdelguerfi, M. (2007) An almost linear time 2.8334-approximation algorithm for the disc covering problem. In Algorithmic Aspects in Information and Management: Lecture Notes in Computer Science, Vol. 4508, pp. 317--326.
[3] Ridout, M.S. (2012) Application of minimal disc covering to the analysis of wildlife signs. Submitted for publication.
