We study minimum-cost sensor placement on a bounded 3D sensing field, R, which comprises a number of discrete points that may or may not be grid points. Suppose we have l types of sensors available with different sensing ranges and different costs. We want to find, given an integer s = 1, a selection of sensors and a subset of points to place these sensors such that every point in R is covered by at least s sensors and the total cost of the sensors is minimum. This problem is known to be NP-hard. Let ki denote the maximum number of points that can be covered by a sensor of the ith type. We present in this paper a polynomial-time approximation algorithm for this problem with a proven approximation ratio γ=∑li=1ki − σ+1. In applications where the distance of any two points has a fixed positive lower bound, each ki is a constant, and so we have a polynomial-time approximation algorithm with a constant guarantee. While γ may be large, we note that it is only a worst-case upper bound. In practice the actual approximation ratio is small, even on randomly generated points that do not have a fixed positive minimum distance between them. We provide a number of numerical results for comparing approximation solutions and optimal solutions, and show that the actual approximation ratios in these examples are all less than 3, even though γ is substantially larger.
