Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/44

Widest empty corridor with multiple links and right-angle turns

Authors Cheng, Siu-Wing
Issue Date 1994
Summary We formulate the problem of computing the widest empty corridor with at most l links and right-angle turns for a set of n points. It is a generalization of the widest empty corridor problem studied in [2,3] and it relates to the problem of computing corridors of other shapes posed in [1,3]. We propose two alternative definitions of a corridor with at most l links and right-angle turns and one is more restrictive than the other. When l=2, it becomes the widest empty L-shaped corridor problem posed in [3], for which we develop an O(n^3)-time algorithm. For general l, we present a dynamic programming algorithm and prove a bound of O(ln^8) on its running time for the more restrictive definition. The running time increases by a factor of n for the other one. We also develop a faster approximation algorithm that computes a solution with width at least (1-e) times the optimal for any e > 0. The approximation algorithm runs in O((1/e)ln^3 log^5 n) time for the more restrictive definition and the running time increases by a factor of n for the other one.
Language English
Format Technical report
Access
Files in this item:
File Description Size Format
tr94-9.pdf 315713 B Adobe PDF