論文

2017年

An Algorithm for Computing a Hamiltonian Cycle of Given Points in a Polygonal Region

INTERNATIONAL CONFERENCE ON COMPUTER SCIENCE AND APPLICATION ENGINEERING (CSAE)
  • Yiyang Jia
  • ,
  • Bo Jiang

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.

リンク情報
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000426973900029&DestApp=WOS_CPL
ID情報
  • ISSN : 2475-8841
  • Web of Science ID : WOS:000426973900029

エクスポート
BibTeX RIS