Improved Algorithm for a Widest 1-Corner Corridor.

Given a set P of n points on a 2D plane, the 1-corner empty corridor is a region inside the convex hull of P which is bounded by a pair of links; each link is an unbounded trapezium bounded by two parallel half-lines, and it does not contain any point of P. We present an improved algorithm for computing the widest empty 1-corner corridor that runs in O(n³log²n) time and O(n²) space. This improves the time complexity of the best known algorithm for the same problem by a factor of ]> [4]. [ABSTRACT FROM AUTHOR]