A comment on a minmax location problem

In a recent paper Hamacher and Schöbel (Oper. Res. Lett. 20 (1997) 165–169) study a minmax location problem in the Euclidean plane that draws its main difficulty from the restriction that the new facility must not be placed within a so-called forbidden region. Hamacher and Schöbel derive a polynomial time algorithm for this problem that runs in O(I3) time for inputs of size I. In this short note we argue that this location problem can be solved in O(I log I) time by applying standard techniques from computational geometry. Moreover, by providing a matching lower bound in the algebraic computation tree model of computation, we show that the time complexity O(I log I) is in fact the best possible