Improved algorithm for the widest empty 1-corner corridor

摘要

Given a set P of n points on a 2D plane, an empty corridor is an open region bounded by two parallel polygonal chains that does not contain any point of P. and partitions the point-set P into two non-empty parts. An empty corridor is said to be a 1-corner empty corridor if each of the two bounding polygonal chains has exactly one corner point. We present an improved algorithm for computing the widest empty 1-corner corridor. It runs in O(n~3 log~2n) time and O(n~2) space. This improves the time complexity of the best known algorithm for the same problem by a factor of n/logn [J.M. Diaz-Banez, M.A. Lopez, J.A. Sellares, On finding a widest empty 1-corner corridor. Information Processing Letters 98 (2006) 199-205].