In terms of the present coverage measure, we pose the evaluation and the deployment problems for give a network; the former is to evaluate the new coverage measure of a given sensor network, and the latter is to find an optimal placement of k additional sensor nodes to improve the coverage for a given positive integer k. We present several algorithms that are either centralized or localized that solve the problems with theoretical proofs and simulation results, thus showing that our algorithms are efficient and easy to implement in practice while the quality of their outputs is guaranteed by formal proofs. For the purpose, we show an interesting relation between the present coverage measure and a certain quantity of a point set, called the bottleneck, which has been relatively well studied in other disciplines such as computational geometry and operations research.