Base station placement on boundary of a convex polygon ?
Let P be a polygonal region which is forbidden for placing a base station in the context of mobile communication. Our objective is to place one base station at any point on the boundary of P and assign a range such that every point in the region is covered by that base station and the range assigned to that base station for covering the region is minimum among all such possible choices of base stations. Here we consider the forbidden region P as convex and base station can be placed on the boundary of the region. We present optimum linear time algorithm for that problem. In addition, we propose a linear time algorithm for placing a pair of base stations on a specified side of the boundary such that the range assigned to those base stations in order to cover the region is minimum among all such possible choices of a pair of base stations on that side.
algorithm wireless network farthest point voronoi diagram computational geometry