论文标题
Sona绘图的新结果：硬度和TSP分离
New Results in Sona Drawing: Hardness and TSP Separation
论文作者
论文摘要
给定一组点位点，SONA图是一个单个封闭曲线，与位点不相交，并且仅在简单的交叉点中与自身相交，因此其补体的每个有界区域都完全包含其中一个站点。我们证明，找到以$ n $给定点找到最小长度的Sona图是NP-Hard，并且这样的曲线可以比同一点的TSP巡回赛更长，$> 1.5487875 $。当仅限于正方形网格边缘的游览（网格电池中的点）时，我们证明即使决定是否存在此类旅行也是不安的。这些结果回答了CCCG 2006上提出的问题。
Given a set of point sites, a sona drawing is a single closed curve, disjoint from the sites and intersecting itself only in simple crossings, so that each bounded region of its complement contains exactly one of the sites. We prove that it is NP-hard to find a minimum-length sona drawing for $n$ given points, and that such a curve can be longer than the TSP tour of the same points by a factor $> 1.5487875$. When restricted to tours that lie on the edges of a square grid, with points in the grid cells, we prove that it is NP-hard even to decide whether such a tour exists. These results answer questions posed at CCCG 2006.
