David Eppstein – Publications

Publications with Valentin Polishchuk

• Applications of nearest-neighbor chains: Euclidean TSP and motorcycle graphs.
  N. Mamano, A. Efrat, D. Eppstein, D. Frishberg, M. T. Goodrich, and S. G. Kobourov, P. Matias, and V. Polishchuk.
  arXiv:1902.06875.
  Computational Geometry: Young Researchers Forum, 2019.
  Proc. 30th International Symposium on Algorithms and Computation (ISAAC 2019), Shanghai, China, 2019.
  Leibniz International Proceedings in Informatics (LIPIcs) 149, 2019, pp. 51:1–51:21.

  We apply the nearest-neighbor chain algorithm to repeatedly find pairs of mutual nearest neighbors for different distances, speeding up the times for the multi-fragment TSP heuristic, motorcycle graphs, straight skeletons, and other problems.

• Well-separated multiagent path traversal.
  G. Dilman, D. Eppstein, V. Polishchuk, and C. Schmidt.
  Proc. 36th Canadian Conference on Computational Geometry, 2024, pp. 137–144.

  We find algorithms and lower bounds for scheduling a sequence of release times for robots to follow the same path as each other, traversing the path at uniform speeds, and not colliding.