A MaximumLpDistance Problem

AbstractThis paper deals with the problem of finding a point within a convex or nonconvex planar region, which is farthest from a given point. Equivalently, given a facility serving a geographical region, a point of this region is sought which receives the least amount of service, assuming that the amount of service received decreases with distance from the facility. Applications of this problem can be found in the military, transportation, telecommunications, and public safety services. In this study the generalizedLpnorm is considered as the distance metric. For this nonlinear and nonconvex problem, properties of the optimal solution are established. Based on these properties a solution algorithm is developed, consisting of (a) thesubdivision procedurethat decomposes the boundary into manageable nonlinear segments, and (b) a branch and bound basedenveloping procedurewhich determines the optimal solution on a nonlinear segment. Using Karush–Kuhn–Tucker conditions, it is proved that the optimal solution in the special cases of the rectilinear and Tchebycheff metrics is among a set of four candidate points. For the Tchebycheff metric, a converse problem, the farthest point Vornoi diagram is defined and constructed. Appropriate examples illustrate all cases