David Eppstein - Publications

Int. Colloq. Automata, Languages, and Programming (ICALP)

• Reset sequences for monotonic automata.
  D. Eppstein.
  15th Int. Coll. Automata, Languages and Programming, Tampere, Finland, 1988.
  Springer, Lecture Notes in Comp. Sci. 317, 1988, pp. 230–238.
  SIAM J. Computing 19 (3): 500–510, 1990.

  Automata theory. A reset sequence for a DFA is an input such that, no matter which state the DFA starts in, it ends up after the input in a known state. These have been used by Natarajan and Goldberg for certain robot motion planning problems (in fact the conference version of this paper used the title "Reset sequences for finite automata with application to design of parts orienters"), and also in coding theory where they arise in the design of self-synchronizing codes. This paper considers DFAs in which the transition functions respect a given cyclic ordering of the states, and shows that their shortest reset sequences can be found quickly. It also considers parallel algorithms for the problem. There remains open a gap between n² and n³ in the maximum length of reset sequences for general automata.

• Parallel algorithmic techniques for combinatorial computation.
  D. Eppstein and Z. Galil.
  Ann. Rev. Comput. Sci. 3: 233–283, 1988.
  Invited talk by Z. Galil, 16th Int. Coll. Automata, Languages and Programming, Stresa, Italy, 1989.
  Springer, Lecture Notes in Comp. Sci. 372, 1989, pp. 304–318.

  This survey on parallel algorithms emphasized the use of basic subroutines such as prefix sums, Euler tours, ear decomposition, and matrix multiplication for solving more complicated graph problems.

• The expected extremes in a Delaunay triangulation.
  M. Bern, D. Eppstein, and F. Yao.
  18th Int. Coll. Automata, Languages and Programming, Madrid, Spain, 1991.
  Springer, Lecture Notes in Comp. Sci. 510, 1991, 674–685.
  Int. J. Comp. Geom. & Appl. 1 (1): 79–92, 1991.

  Discusses the expected behavior of Delaunay triangulations for points chosen uniformly at random (without edge effects). The main result is that within a region containing \(n\) points, the expected maximum degree is \(O(\log n / \log\log n)\).

• Stable-matching Voronoi diagrams: combinatorial complexity and algorithms.
  G. Barequet, D. Eppstein, M. T. Goodrich, and N. Mamano.
  arXiv:1804.09411
  Proc. 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Prague.
  Leibniz International Proceedings in Informatics (LIPIcs) 107, pp. 89:1–89:14.
  J. Computational Geometry 11 (1): 26–59, 2020.

  The stable-matching Voronoi diagram of a collection of point sites in the plane, each with a specified area, is a collection of disjoint regions of the plane, one for each site and having the specified area, so that no pair of a point and a site are closer to each other than to the farthest other site and point that they may be matched to. We prove nearly-matching upper and lower bounds on the combinatorial complexity of these diagrams and provide algorithms that can compute them in a polynomial number of primitive steps.

• Optimally sorting evolving data.
  J. Besa, W. E. Devanny, D. Eppstein, M. T. Goodrich, and T. Johnson.
  arXiv:1805.03350
  Proc. 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Prague.
  Leibniz International Proceedings in Informatics (LIPIcs) 107, pp. 81:1–81:13.
  

  Suppose that a collection of objects has a linear order that is evolving by swaps of randomly chosen consecutive elements. We would like to maintain an approximation to this order using an algorithm that performs one comparison per swap. We show that repeated insertion sort can maintain linear inversion distance from the underlying order, the best possible.

• Improved mixing for the convex polygon triangulation flip walk.
  D. Eppstein and D. Frishberg.
  arXiv:2207.09972.
  Proc. 50th EATCS International Colloquium on Automata, Languages, and Programming (ICALP 2023).
  Leibniz International Proceedings in Informatics (LIPIcs) 261, 2023, pp. 56:1–56:17.
  

  The associahedron is a polytope whose vertices represent the triangulations of a convex polygon, and whose edges represent flips connecting one triangulation to another. We show that a random walk on the edges of this polytope rapidly converges to the uniform distribution on triangulations. However, we also show that the associahedron does not have constant expansion.