Paper by Erik D. Demaine

Reference:

Man-Kwun Chiu, Erik D. Demaine, Jenny Diomidova, David Eppstein, Robert A. Hearn, Adam Hesterberg, Matias Korman, Irene Parada, and Mikhail Rudoy, “New Results in Sona Drawing: Hardness and TSP Separation”, in Proceedings of the 32nd Canadian Conference in Computational Geometry (CCCG 2020), Saskatchewan, Saskatoon, Canada, August 5–7, 2020.

BibTeX

@InProceedings{Sona_CCCG2020,
  AUTHOR        = {Man-Kwun Chiu and Erik D. Demaine and Jenny Diomidova and David Eppstein and Robert A. Hearn and Adam Hesterberg and Matias Korman and Irene Parada and Mikhail Rudoy},
  authororig    = {Man-Kwun Chiu and Erik D. Demaine and Yevhenii Diomidov and David Eppstein and Robert A. Hearn and Adam Hesterberg and Matias Korman and Irene Parada and Mikhail Rudoy},
  TITLE         = {New Results in Sona Drawing: Hardness and TSP Separation},
  BOOKTITLE     = {Proceedings of the 32nd Canadian Conference in Computational Geometry (CCCG 2020)},
  bookurl       = {http://vga.usask.ca/cccg2020/},
  ADDRESS       = {Saskatchewan, Saskatoon, Canada},
  MONTH         = {August 5--7},
  YEAR          = 2020,

  withstudent   = 1,
  unrefereed    = 1,
  dblp          = {https://dblp.org/rec/conf/cccg/ChiuDDEHHKPR20},
  comments      = {This paper is also available as <A HREF="https://arXiv.org/abs/2007.15784">arXiv:2007.15784</A>. David Eppstein's presentation is available on <A HREF="https://youtu.be/TGxTTb1NRSo">YouTube</A>.},
}

Abstract:

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.

Comments:

This paper is also available as arXiv:2007.15784. David Eppstein's presentation is available on YouTube.

Availability:

The paper is available in PDF (471k).

See information on file formats.

[Google Scholar search]