A Maximum L Distance Problem

This 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 generalized Lp norm 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. the subdi¨ision procedure that decomposes the boundary into manageable nonlinear segments, and b. a branch and bound based en¨eloping procedure which 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.