On finding a widest empty 1-corner corridor
A 1-corner corridor through a set S of points is an open subset of CH(S) containing no points from S and bounded by a pair of parallel polygonal lines each of which contains two segments. Given a set of n points in the plane, we consider the problem of computing a widest empty 1-corner corridor. We describe an algorithm that solves the problem in O(n(4) log n) time and O(n) space. We also present an approximation algorithm that computes in O(n log n/epsilon(1/2) + n(2)/epsilon) time a solution with width at least a fraction (1 - epsilon) of the optimal, for any small enough epsilon > 0. (c) 2006 Elsevier B.V. All rights reserved.
algorithms computational geometry widest empty corridors