HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Technical Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/44
Title: Widest empty corridor with multiple links and right-angle turns
Authors: Cheng, Siu-Wing
Issue Date: 1994
Series/Report no.: Computer Science Technical Report ; HKUST TR94-9
Abstract: 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.
URI: http://hdl.handle.net/1783.1/44
Appears in Collections:CSE Technical Reports

Files in This Item:

File Description SizeFormat
tr94-9.pdf308KbAdobe PDFView/Open

All items in this Repository are protected by copyright, with all rights reserved.