返回Google圖書搜尋

A new approach for vertex guarding of polyhedral surfaces

出版	Faculty of Electrical Engineering and Computer Science, Laboratory for geometric modelling and multimedia algorithms, 2002
URL	http://books.google.com.hk/books?id=l4DTOQAACAAJ&hl=&source=gbs_api

註釋Guarding polyhedral surfaces is an important optimisation problem with many applications. In the contribution, the problem of finding the minimum number of guards and their positions, which cover a convex terrain is considered. Known approximative algorithms (Greedy Add, Stingy Drop, and the algorithm based on 5-coloring) are revised and a new approach names Smart Greedy algorithm is given. The algorithm works in three steps: identification of the vertex that is almost sure not a part of the optimum solution, selection of the vertex that is almost sure a part of the optimum solution, and updating a corresponding data structure. The proposed algorithm is compared against optimality of solutions and spent running time. It is shown that our algorithm produces best results in the shortest time.