Computing a planar widest empty -siphon in o(n 3 ) time
Boaz Ben Moshe, Binay Kumar Bhattacharya, Sandip Das, Daya Ram Gaur, Qiaosheng Shi · Canadian Conference on Computational Geometry · 2007
Given a set of n points P in the Euclidean plane, we consider the problem of locating a 1-corner polygonal chain X such that minp2P d(p;X) is maximized. The polygonal chain has the added property that its interior angle is fi and it partitions P. In this note we present an algorithm that solves the problem in o(n 3 ) time and space. The previous best running time for this problem was O(n 3 log 2 n) time [2].