Computing the Widest Empty Boomerang.
Boaz Ben Moshe, Binay Kumar Bhattacharya, Qiaosheng Shi · 2005
In this paper we consider the following obnoxious facility location problem: given a set S of n points in the plane, and two special points a and b, find the 1-corner polygonal chain (also known as boomerang) connecting a and b such that its minimum distance to S is maximized. In other words: find the widest empty polygonal chain of two edges having extremes anchored at a and b. We present a new O(n log n) algorithm which improves the previous O(n 2) result [3].