David Eppstein - Publications

Publications with Mikhail Rudoy

• New results in sona drawing: hardness and TSP separation.
  M.-W. Chiu, E. Demaine, M. Demaine, D. Eppstein, R. Hearn, A. Hesterberg, M. Korman, I. Parada, and M. Rudoy.
  arXiv:2007.15784.
  Proc. 32nd Canadian Conference on Computational Geometry, 2020, pp. 63–72.

  A sona drawing is a self-crossing curve in the plane that separates each of a given system of points into its own region. We show that it is hard to find the shortest such curve, and we explore how much shorter than the TSP it can be.