We consider an obnoxious facility location problem in which the facility is a trajectory consisting of a bounded length polygonal chain of two edges having extremes anchored at two given points. In other words, given a set S of points in the plane and a positive value l"0, we want to compute an anchored 1-corner polygonal chain having length at most l"0 such that the minimum distance to the points in S is maximized. We present non-trivial algorithms based on geometric properties of each possible configuration providing a solution. More specifically, we give an O(nlogn)-time algorithm for finding a 1-corner obnoxious polygonal chain whose length is exactly l"0, and an O(n^2)-time algorithm when the length of the optimal chain is at most the given bound l"0.
['José Miguel Díaz-Báñez', 'Ferran Hurtado']
Computing obnoxious 1-corner polygonal chains