Wireless sensor networks provide an alternative way of improving our environments, such as environment surveillance, hazard monitoring, and other customized environmental applications. Good coverage of service in a sensor network is an essential issue to ensure the service of quality. This paper studies the deployment of new sensor nodes so that the improvement of coverage is optimized. We propose an optimal polynomial time algorithm for this problem. Based on computational geometry and graph theory, we show the properties of such a deployment and the correctness of its optimality.