  The problem of covering random points in a plane with sets of a given shape
has several practical applications in communications and operations research.
One especially prominent application is the coverage of randomly-located points
of interest by randomly-located sensors in a wireless sensor network. In this
article we consider the situation of a large area containing randomly placed
points (representing points of interest), as well a number of randomly-placed
disks of equal radius in the same region (representing individual sensors'
coverage areas). The problem of finding the smallest possible set of disks that
cover the given points is known to be NP-complete. We show that the
computational complexity may be reduced by classifying the disks into several
definite classes that can be characterized as necessary, excludable, or
indeterminate. The problem may then be reduced to considering only the
indeterminate sets and the points that they cover. In addition, indeterminate
sets and the points that they cover may be divided into disjoint ``islands''
that can be solved separately. Hence the actual complexity is determined by the
number of points and sets in the largest island. We run a number of simulations
to show how the proportion of sets and points of various types depend on two
basic scale-invariant parameters related to point and set density. We show that
enormous reductions in complexity can be achieved even in situations where
point and set density is relatively high.
