Going around in circles

详细信息	查看全文 | 推荐本文 |

• 作者：Adrian Dumitrescu¹ ; ^{dumitres@uwm.edu}
• 关键词：Hamiltonian cycle ; Turning angle ; Robot path planning ; Geometric graph ; Integer lattice
• 刊名：Computational Geometry
• 出版年：2012
• 期刊代码：18_09257721
• 类别：cp
• 出版时间：August, 2012
• 卷：45
• 期：7
• 页码：370-381
• 文件大小：265 K

摘要

Let and let 惟 be a disk of sufficiently large radius R in the plane, i.e., . We first show that the set of lattice points inside 惟 can be connected by a (possibly self-intersecting) spanning tour (Hamiltonian cycle) consisting of straight line edges such that the turning angle at each point on the tour is at most 蔚. This statement remains true for any large and evenly distributed point set (suitably defined) in a disk. This is the first result of this kind that suggests far-reaching generalizations to arbitrary regions with a smooth boundary. Our methods are constructive and lead to an efficient algorithm for computing such a tour. On the other hand, it is shown that such a result does not hold for convex regions without a smooth boundary.