| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427756 | Information Processing Letters | 2009 | 6 Pages |
Abstract
In this paper we describe and solve the following geometric optimisation problem: given a set S of n points on the plane (antennas) and two points A and B, find the smallest radial range r∈ℜ+ (power transmission range of the antennas) so that a path with endpoints A and B exists in which all points are within the range of at least two antennas. The solution to the problem has several applications (e.g., in the planning of safe routes). We present an O(nlogn) time solution, which is based on the second order Voronoi diagram. We also show how to obtain a path with such characteristics.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
