2017年
An Algorithm for Computing a Hamiltonian Cycle of Given Points in a Polygonal Region
INTERNATIONAL CONFERENCE ON COMPUTER SCIENCE AND APPLICATION ENGINEERING (CSAE)
- ,
- 巻
- 190
- 号
- 開始ページ
- 243
- 終了ページ
- 250
- 記述言語
- 英語
- 掲載種別
- 研究論文(国際会議プロシーディングス)
- 出版者・発行元
- DESTECH PUBLICATIONS, INC
In this paper, for a point set X in a simple polygon P, we present an algorithm to compute a Hamiltonian cycle which avoids the boundary of P and accesses all points of X. Computing a Hamiltonian cycle of given points in a simple polygon is a novel transformation of the general Hamiltonian problems and the problem of finding simple paths on given obstacles in a simple polygon. In our solution, we first construct the geodesic convex hull G of X inside P, and then find simple paths turn only at the points of X for two adjacent vertices in X along the boundary of G which are invisible to each other. After an original Hamiltonian cycle is found, we insert the remaining points to it. Finally, we present an O((n(2) + m)nlogm) time algorithm (n is the number of points in X and m is the number of P's vertices) to report a Hamiltonian cycle if it exists or report that no such cycle exists.
- リンク情報
- ID情報
-
- ISSN : 2475-8841
- Web of Science ID : WOS:000426973900029