請用此 Handle URI 來引用此文件: http://hdl.handle.net/11455/38311
標題: Finding an Approximate Minimum-Link Visibility Path Inside a Simple Polygon
作者: M.H.Alsuwaiyel
D.T.Lee
出版社: Elsevier North-Holland, Inc. Amsterdam, The Netherlands, The Netherlands
摘要: Introduction In [1] Alsuwaiyel and Lee showed that computing a minimum link path � inside a simple polygon with n vertices such that the interior of the polygon is weakly visible from � is NP-hard. The authors also presented an O(n 3 log n) time algorithm for producing an approximate solution that was claimed to have no more than 3 times the number of links of an optimal solution. In [2] Arkin et al. show that the problem of finding a minimum-link watchman route in polygonal domains (with holes) 2 is NP-complete and give a polynomialtime approximation algorithm with performance ratio of log n. In fact the algorithm in [1] gives a feasible solution with no bound guarantee. Here we describe in a more precise way the approximation algorithm that constructs a watchman path as well as a tour in time maxfm 2 ; mng =<F
URI: http://hdl.handle.net/11455/38311
ISSN: 0020-0190
顯示於類別:資訊科學與工程學系所

文件中的檔案:
沒有與此文件相關的檔案。


在 DSpace 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。