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~3 log~2 n) time and O(n~2) space. This improves the time complexity of the best known algorithm for the same problem by a factorrnof n/(log n)[4].