Location of an Obnoxious Route

Abstract

This problem deals with the location of a route or path through a set of given points in order to maximize the smallest weighted distance from the given points to the route. Applications may include the planning of pipelines carrying noxious material, and also certain problems in robotics. The first algorithm finds a non-linear path by iteratively solving network minimal-cut problems. A second algorithm solves the case where the route is restricted to be linear.