2-Covered paths by a set of antennas with minimum power transmission range Article

Abellanas, M, Bajuelos, AL, Matos, I. (2009). 2-Covered paths by a set of antennas with minimum power transmission range . INFORMATION PROCESSING LETTERS, 109(14), 768-773. 10.1016/j.ipl.2009.03.016

cited authors

  • Abellanas, M; Bajuelos, AL; Matos, I

authors

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 (n log n) time solution, which is based on the second order Voronoi diagram. We also show how to obtain a path with such characteristics. © 2009 Elsevier B.V. All rights reserved.

publication date

  • June 30, 2009

published in

Digital Object Identifier (DOI)

start page

  • 768

end page

  • 773

volume

  • 109

issue

  • 14