Papers for which definitive version is a book chapter
Speeding up dynamic programming.
D. Eppstein, Z. Galil, and R. Giancarlo.
29th IEEE Symp. Foundations of Comp. Sci., White Plains, New York, 1988, pp. 488–496.
Worksh. Algorithms for Molecular Genetics, Bethesda, Maryland, 1988.
Tech. Rep. CUCS-379-88, Computer Science Dept., Columbia University, 1988.
Appeared as "Efficient algorithms with applications to molecular biology" in Int. Advanced Workshop on Sequences, Positano, Italy, 1988.
Sequences: Combinatorics, Compression, Security, Transmission, R. M. Capocelli, ed., Springer, 1990, pp. 59–74.The FOCS and Positano versions of this paper merged my results on a dynamic program used for RNA secondary structure prediction, with Raffaele's on sequence comparison. The Bethesda talk and the TR version both used the longer title "Speeding up dynamic programming with application to the computation of RNA structure", and included only the RNA result, which used a mild convexity assumption on certain costs to save two orders of magnitude in total time. This work incited a boom in computational biology within the theory community that is still going strong. But the RNA results were quickly improved by a log factor [Aggarwal et al. at the same FOCS] and never made it into a journal paper.
Horizon theorems for lines and polygons.
M. Bern, D. Eppstein, P. Plassman, and F. Yao.
Discrete and Computational Geometry: Papers from the DIMACS Special Year, J. Goodman, R. Pollack, and W. Steiger, eds.,
DIMACS Series in Discrete Mathematics and Theoretical Computer Science 6, Amer. Math. Soc., 1991, 45–66.The total complexity of the cells in a line arrangement that are cut by another line is at most \(15n/2\). The complexity of cells cut by a convex \(k\)-gon is \(O(n\alpha(n,k))\). The first bound is tight, but it remains open whether the second is, or whether only linear complexity is possible.
Efficient algorithms for sequence analysis.
D. Eppstein, Z. Galil, R. Giancarlo, and G.F. Italiano.
International Advanced Workshop on Sequences, Positano, Italy, 1991.
Sequences II: Methods in Communication, Security, and Computer Science, R.M. Capocelli, A. De Santis, and U. Vaccaro, eds., Springer, 1993, pp. 225–244.Surveys results on speeding up certain dynamic programs used for sequence comparison and RNA structure prediction.
Mesh generation and optimal triangulation.
M. Bern and D. Eppstein.
Tech. Rep. CSL-92-1, Xerox PARC, 1992.
Computing in Euclidean Geometry, D.-Z. Du and F.K. Hwang, eds., World Scientific, 1992, pp. 23–90.
Revised version in Computing in Euclidean Geometry, 2nd ed., D.-Z. Du and F.K. Hwang, eds., World Scientific, 1995, pp. 47–123.Considers both heuristics and theoretical algorithms for finding good triangulations and tetrahedralizations for surface interpolation and unstructured finite element meshes. Note that the online copy here omits the figures.
Approximation algorithms for geometric problems.
M. Bern and D. Eppstein.
Approximation Algorithms for NP-hard Problems, D. Hochbaum, ed., PWS Publishing, 1996, pp. 296–345.Considers problems for which no polynomial-time exact algorithms are known, and concentrates on bounds for worst-case approximation ratios, especially those depending intrinsically on geometry rather than on more general graph theoretic or metric space formulations. Includes sections on the traveling salesman problem, Steiner trees, minimum weight triangulation, clustering, and separation problems.
Spanning trees and spanners.
D. Eppstein.
Tech. Rep. 96-16, ICS, UCI, 1996.
Handbook of Computational Geometry, J.-R. Sack and J. Urrutia, eds., Elsevier, 1999, pp. 425–461.Surveys results in geometric network design theory, including algorithms for constructing minimum spanning trees and low-dilation graphs.
Dynamic graph algorithms.
D. Eppstein, Z. Galil, and G.F. Italiano.
Tech. Rep. CS96-11, Univ. Ca' Foscari di Venezia, Oct. 1996.
Algorithms and Theoretical Computing Handbook, M. J. Atallah, ed., CRC Press, 1999, chapter 8.
2nd. ed., CRC Press, 2010, Vol. I: General Concepts and Techniques, chapter 9, pp. 9–1 - 9-28.
Searching for spaceships.
D. Eppstein.
arXiv:cs.AI/0004003.
MSRI Combinatorial Game Theory Research Worksh., July 2000.
More Games of No Chance, R. J. Nowakowski, ed., MSRI Publications 42, pp. 433–453.We describe software that searches for spaceships in Conway's Game of Life and related two-dimensional cellular automata. Our program searches through a state space related to the de Bruijn graph of the automaton, using a method that combines features of breadth first and iterative deepening search, and includes fast bit-parallel graph reachability and path enumeration algorithms for finding the successors of each state. Successful results include a new 2c/7 spaceship in Life, found by searching a space with 2^126 states.
One-dimensional peg solitaire, and duotaire.
C. Moore and D. Eppstein.
arXiv:math.CO/0006067 and math.CO/0008172.
MSRI Combinatorial Game Theory Research Worksh., July 2000.
Santa Fe Inst. working paper 00-09-050, September 2000.
More Games of No Chance, R. J. Nowakowski, ed., MSRI Publications 42, pp. 341–350.We describe by a regular expression the one-dimensional peg-solitaire positions reducible to a single peg, and provide a linear-time algorithm (based on finding shortest paths in an associated DAG) for reducing any such position to the minimum number of pegs. We then investigate impartial games in which players alternate peg solitaire moves in an attempt to be the one to move last.
(Cris' MSRI talk on streaming video – Cris' publications page)
Phutball endgames are hard.
E. Demaine, M. Demaine, and D. Eppstein.
arXiv:cs.CC/0008025.
More Games of No Chance, R. J. Nowakowski, ed., MSRI Publications 42, pp. 351–360.We show that, in John Conway's board game Phutball (or Philosopher's Football), it is NP-complete to determine whether the current player has a move that immediately wins the game. In contrast, the similar problems of determining whether there is an immediately winning move in checkers, or a move that kings a man, are both solvable in polynomial time.
Vertex-unfoldings of simplicial manifolds.
E. Demaine, D. Eppstein, J. Erickson, G. Hart, and J. O'Rourke.
Tech. Reps. 071 and 072, Smith College, 2001.
arXiv:cs.CG/0107023 and cs.CG/0110054.
18th ACM Symp. Comp. Geom., Barcelona, 2002, pp. 237–243.
Discrete Geometry: In honor of W. Kuperberg's 60th birthday, Pure and Appl. Math. 253, Marcel Dekker, pp. 215–228, 2003.We unfold any polyhedron with triangular faces into a planar layout in which the triangles are disjoint and are connected in a sequence from vertex to vertex
Fat 4-polytopes and fatter 3-spheres.
D. Eppstein, G. Kuperberg, and G. Ziegler.
arXiv:math.CO/0204007.
Discrete Geometry: In honor of W. Kuperberg's 60th birthday, Pure and Appl. Math. 253, Marcel Dekker, pp. 239–265, 2003.We introduce the fatness parameter of a 4-dimensional polytope P, (f1+f2)/(f0+f3). It is open whether all 4-polytopes have bounded fatness. We describe a hyperbolic geometry construction that produces 4-polytopes with fatness > 5.048, as well as the first infinite family of 2-simple, 2-simplicial 4-polytopes and an improved lower bound on the average kissing number of finite sphere packings in R3. We show that fatness is not bounded for the more general class of strongly regular CW decompositions of the 3-sphere.
Separating thickness from geometric thickness.
D. Eppstein.
arXiv:math.CO/0204252.
10th Int. Symp. Graph Drawing, Irvine, 2002.
Springer, Lecture Notes in Comp. Sci. 2528, 2002, pp. 150–161.
In Towards a Theory of Geometric Graphs, AMS, 2004, Contemporary Math 342, J. Pach, ed., pp. 75–86.We show that thickness and geometric thickness are not asymptotically equivalent: for every t, there exists a graph with thickness three and geometric thickness > t. The proof uses Ramsey-theoretic arguments similar to those in "Separating book thickness from thickness".