1990
Note that a paper may appear in listings for multiple years due to multiple publication (of tech. report, conference, and journal versions).- 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.
- Sequence comparison with mixed convex and concave costs.
D. Eppstein.
Tech. Rep. CUCS-382-88, Computer Science Dept., Columbia University, 1988.
J. Algorithms 11 (1): 85–101, 1990.Gives an algorithm for finding the minimum number of mutations needed to transform one input string into another, in a general model in which substrings may be inserted or deleted at a cost depending nonlinearly on the substring length. The time bound depends on the number of times the second derivative of the cost function changes sign.
- 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 n2 and n3 in the maximum length of reset sequences for general automata.
- Simultaneous strong separations of
probabilistic and unambiguous complexity classes.
D. Eppstein, L. Hemachandra, J. Tisdall, and B. Yener.
Int. Conf. Computing and Information, Toronto, North-Holland, 1989, pp. 65–70.
Tech. Rep. 335, Dept. Comp. Sci., U. Rochester, 1990.
Mathematical Systems Theory 25 (1): 23–36, 1992.Structural complexity theory. Constructs oracles in which \(\mathsf{BPP}\) (a probabilistic complexity class) and \(\mathsf{UP}\) (the class of problems with a unique "witness") contain languages that in a very strong sense are not contained in the other class. The conference version used the title "Probabilistic and unambiguous computation are incomparable".
- Maintenance of a minimum spanning forest in a dynamic plane graph.
D. Eppstein, G.F. Italiano, R. Tamassia, R.E. Tarjan, J. Westbrook, and M. Yung.
1st ACM-SIAM Symp. Discrete Algorithms, San Francisco, 1990, pp. 1–11.
J. Algorithms 13 (1): 33–54, 1992 (special issue for 1st Symp. Discrete Algorithms).
Corrigendum, J. Algorithms 15: 173, 1993.The complement of a minimum spanning tree is a maximum spanning tree in the dual graph. By applying this fact we can use a modified form of Sleator and Tarjan's dynamic tree data structure to update the MST in logarithmic time per update.
- The farthest point Delaunay triangulation minimizes angles.
D. Eppstein.
Tech. Rep. 90-45, ICS, UCI, 1990.
Comp. Geom. Theory & Applications 1: 143–148, 1992.Given a collection of points in convex position, the sharpest angle determined by any triple can be found as a corner of a triangle in the farthest point Delaunay triangulation.
- Finding the k smallest spanning trees.
D. Eppstein.
2nd Scand. Worksh. Algorithm Theory, Bergen, Norway, 1990.
Springer, Lecture Notes in Comp. Sci. 447, 1990, pp. 38–47.
BIT 32: 237–248, 1992 (special issue for 2nd Scand. Worksh. Algorithm Theory).By removing edges not involved in some solution, and contracting edges involved in all solutions, we reduce the problem to one in a graph with O(k) edges and vertices. This simplification step transforms any time bound involving m or n to one involving min(m, k) or min(n, k) respectively. This paper also introduces the geometric version of the k smallest spanning trees problem (the graph version was long known) which it solves using order (k+1) Voronoi diagrams.
- Sparse dynamic programming.
D. Eppstein, Z. Galil, R. Giancarlo, and G.F. Italiano.
1st ACM-SIAM Symp. Discrete Algorithms, San Francisco, 1990, pp. 513–522.
"Sparse dynamic programming I: linear cost functions", J. ACM 39: 519–545, 1992.
"Sparse dynamic programming II: convex and concave cost functions", J. ACM 39: 546–567, 1992.Considers sequence alignment and RNA structure problems in which the solution is constructed by piecing together some initial set of fragments (e.g. short sequences that match exactly). The method is to consider a planar point set formed by the fragment positions in the two input sequences, and use plane sweep to construct a cellular decomposition of the plane similar to the rectilinear Voronoi diagram.
- Visibility with a moving point of view.
M. Bern, D.P. Dobkin, D. Eppstein, and R. Grossman.
1st ACM-SIAM Symp. Discrete Algorithms, San Francisco, 1990, pp. 107–118.
Algorithmica 11: 360–378, 1994.An investigation of 3d visibility problems in which the viewing position moves along a straight flight path, with various assumptions on the complexity of the viewed scene.
- Provably good mesh generation.
M. Bern, D. Eppstein, and J. Gilbert.
31st IEEE Symp. Foundations of Comp. Sci., St. Louis, Missouri, 1990, pp. 231–241.
J. Comp. Sys. Sci. 48: 384–409, 1994 (special issue for 31st FOCS).In this paper, we construct triangulations of point sets and polygons by using quadtrees to add extra vertices to the input. As a result we can guarantee that all triangles have angles bounded away from zero, using a number of triangles within a constant of optimal; this was the first paper to provide simultaneous bounds on mesh element quality and mesh complexity of this form, and therefore the first to provide finite element mesh generation algorithms that guarantee both the robustness of the algorithm against unexpected input geometries and the quality of its output.
In the same paper we also use quadtrees to triangulate planar point sets so that all angles are non-obtuse, using linearly many triangles, and to triangulate higher dimensional point sets with no small solid angles and a number of simplices within a constant of optimal. Also, we can augment any higher dimensional point set so the Delaunay triangulation has linear complexity.
In later follow-up work, I showed that the same technique can also be used to find a triangulation whose edges have total length within a constant factor of optimal. Bern, Mitchell, and Ruppert showed that alternative methods can be used to triangulate any polygon without obtuse angles; see "Faster circle packing with application to nonobtuse triangulation" for an algorithmic improvement to their technique. Additionally, with Bern, Chew, and Ruppert, we showed that any point set in higher dimensions can be triangulated with nonobtuse simplices. Bern and I surveyed these and related results in our paper "Mesh generation and optimal triangulation".