-
\-
\!top
-
\-
\!top
-
\-
\!top
-
\-
\!top
-
\-
\!year
- \!y:1985 1985 \- \!year
- \!y:1987 1987 \- \!year
- \!y:1988 1988 \- \!year
- \!y:1989 1989 \- \!year
- \!y:1990 1990 \- \!year
- \!y:1991 1991 \- \!year
- \!y:1992 1992 \- \!year
- \!y:1993 1993 \- \!year
- \!y:1994 1994 \- \!year
- \!y:1995 1995 \- \!year
- \!y:1996 1996 \- \!year
- \!y:1997 1997 \- \!year
- \!y:1998 1998 \- \!year
- \!y:1999 1999 \- \!year
- \!y:2000 2000 \- \!year
- \!y:2001 2001 \- \!year
- \!y:2002 2002 \- \!year
- \!y:2003 2003 \- \!year
- \!y:2004 2004 \- \!year
- \!y:2005 2005 \- \!year
- \!y:2006 2006 \- \!year
- \!y:2007 2007 \- \!year
- \!y:2008 2008 \- \!year
- \!y:2009 2009 \- \!year
-
\!y:future
To appear with unknown date
\-
\!conf
- \!c:scg ACM Symp. Computational Geometry (SCG) \- \!conf
- \!c:stoc ACM Symp. Theory of Computing (STOC) \- \!conf
- \!c:soda ACM-SIAM Symp. Discrete Algorithms (SODA) \- \!conf
- \!c:esa European Symp. Algorithms (ESA) \- \!conf
- \!c:focs IEEE Symp. Foundations of Computer Science (FOCS) \- \!conf
- \!c:icalp Int. Colloq. Automata, Languages, and Programming (ICALP) \- \!conf
- \!c:imr Int. Meshing Roundtable \- \!conf
- \!c:gd Int. Symp. Graph Drawing \- \!conf
- \!c:swat Scandinavian Worksh. Algorithm Theory (SWAT) \- \!conf
- \!c:wads Worksh. Algorithms and Data Structures (WADS) \- \!conf
- \!c:wcg ARO-MSI and CGC Workshops in Computational Geometry \- \!conf
- \!c:cccg Canadian Conf. Computational Geometry (CCCG) \- \!conf
- \!c:other Other conferences and workshops \- \!conf
- \!c:sub Conference submissions \- \!conf
- \!c:no Papers not presented at a conference \- \!jour
- \!j:talg ACM Transactions on Algorithms \- \!jour
- \!j:algo Algorithmica \- \!jour
- \!j:cgta Computational Geometry : Theory & Applications \- \!jour
- \!j:dcg Discrete & Computational Geometry \- \!jour
- \!j:dm Discrete Mathematics \- \!jour
- \!j:ic Information & Computation (formerly Information & Control) \- \!jour
- \!j:ipl Information Processing Letters \- \!jour
- \!j:ijcga International Journal of Computational Geometry & Applications \- \!jour
- \!j:algs Journal of Algorithms and Transactions on Algorithms \- \!jour
- \!j:acm Journal of the Association for Computing Machinery \- \!jour
- \!j:jct Journal of Combinatorial Theory \- \!jour
- \!j:jcss Journal of Computing and Systems Sciences \- \!jour
- \!j:jga Journal of Graph Algorithms and Applications \- \!jour
- \!j:jgt Journal of Graph Theory \- \!jour
- \!j:mst Theory of Computing Systems (formerly Mathematical Systems Theory) \- \!jour
- \!j:bit Nordic Journal on Computing (formerly BIT) \- \!jour
- \!j:ojc ORSA Journal on Computing \- \!jour
- \!j:sjc SIAM Journal on Computing \- \!jour
- \!j:tcs Theoretical Computer Science \- \!jour
- \!j:other Other journals and periodicals \- \!jour
- \!j:sub Journal and book chapter submissions \- \!jour
- \!j:book Papers for which definitive version is a book chapter \- \!jour
- \!j:no Papers with no journal or book chapter version \- \!auth
- \!a:agarwal Papers with \!auth \!auth Pankaj Agarwal \!auth \- \!auth
- \!a:amenta Papers with \!auth \!auth Nina Amenta \!auth \- \!auth
- \!a:arge Papers with \!auth \!auth Lars Arge \!auth \- \!auth
- \!a:aronov Papers with \!auth \!auth Boris Aronov \!auth \- \!auth
- \!a:asuri Papers with Hari Asuri \- \!auth
- \!a:augustine Papers with \!auth \!auth John Augustine \!auth \- \!auth
-
\-
\!subj
-
\-
\!graph
-
\!graph:all
All graph algorithm papers
\-
\!geom
- \!geom:all All geometry papers \- \!graph
- \!graph:sgi Subgraph isomorphism \- \!graph
- \!graph:cube Partial cubes and media theory \- \!graph
- \!graph:match Matching \- \!graph \!geom
- \!tsp Traveling salesman and hamiltonian cycle problems \- \!graph \!geom
- \!mst Minimum spanning trees \- \!graph
- \!graph:dyn Dynamic graph algorithms \- \!graph
- \!graph:planar Planar graphs \- \!graph
- \!graph:color Graph coloring \- \!graph
- \!graph:path Paths in graphs \- \!graph
- \!graph:random Random graphs and web graph models \- \!geom
- \!geom:hyperbolic Hyperbolic geometry \- \!geom
- \!geom:path Paths and distances in geometric graphs \- \!geom
- \!geom:kset Halving lines and k-sets \- \!geom
- \!geom:deep Deep points in arrangements \- \!geom
- \!geom:dyn Dynamic computational geometry \- \!geom
- \!geom:tri Mesh generation and optimal triangulation \- \!geom
- \!geom:qt Quadtrees and related hierarchical decompositions \- \!geom
- \!geom:cluster Geometric clustering \- \!geom
- \!geom:nn Nearest neighbors \- \!geom
- \!geom:circle Circles, spheres, and sphere packing \- \!geom
- \!geom:lp Low-dimensional linear programming and LP-type problems \- \!geom
- \!geom:ss Straight skeletons \- \!geom
- \!geom:zono Zonotopes \- \!geom
- \!geom:approx Geometric approximation \- \!geom \!graph
- \!gdraw Graph drawing \- \!geom \!graph
- \!ramsey Ramsey theory \- \!subj
- \!exponential Exponential-time algorithmics \- \!subj
- \!molbio Computational molecular biology \- \!subj
- \!stat Computational statistics \!subj \- \!subj
- \!par Parallel algorithms \- \!subj \!geom \!graph
- \!kbest Generating multiple near-optimal solutions \- \!subj \!geom
- \!usesgeom Geometric methods for non-geometric problems \- \!geom
- \!geom:misc Miscellaneous geometry \- \!graph
- \!graph:misc Miscellanous graph theory \- \!subj
- \!param Parametric optimization \- \!subj
- \!pure Pure Mathematics \- \!subj
- \!rec Recreational Mathematics \- \!subj
- \!misc Miscellaneous \- \# finish header or list of subtopics \!top \!geom \!graph \!auth \!conf \!jour \!subj \!year
\- \!c:scg I was on the program committee for the 11th Symposium, 1995, and the 15th Symposium, 1999. I am the program chair for the theory track of the 17th Symposium, 2001.
\- \!c:focs I was on the program committee for the 34th Symposium, 1993.
\- \!c:stoc I was on the program committee for the 26th Symposium, 1994, the 32nd Symposium, 2000, and the 35th Symposium, 2003.
\- \!c:soda I was on the program committee for the 7th Symposium, 1996, and the 11th Symposium, 2000. I was also program chair for the 13th Symposium, 2002.
\- \!c:wads I was on the program committee for the 5th Workshop, 1997.
\- \!j:algs I have been on the editorial board since 1994.
\- \!j:sjc \!j:jga I have been on the editorial board since 1995.
\- \!top A listing of my publications in BibTeX format is also available, and is indexed from the entries in this file. Most of my recent papers can be found at arXiv. I also maintain a database of citations to my own papers by other authors.
Caveat: Most of the papers here are subject to some sort of copyright restriction.
\- \!c:stoc The Hypertext Bibliography Project at MIT also includes listings of my STOC papers.
\- \!c:soda The Hypertext Bibliography Project at MIT also includes listings of my SODA papers.
\- \!c:focs The Hypertext Bibliography Project at MIT also includes listings of my FOCS papers.
\- \!j:ic The Hypertext Bibliography Project at MIT also includes listings of my Inf.&Comput. papers.
\- \!j:acm The Hypertext Bibliography Project at MIT also includes listings of my J. ACM papers.
\- \!kbest See also my bibliography of algorithms for k shortest paths, which also includes related work on other "kth best solution" problems, especially the k smallest spanning trees. Victor Jiménez and Andrés Marzal maintain a web page on algorithms for k shortest paths.
\- \!param These papers concern problems in which some parameter or parameters is free, and one must explore the space of different solutions obtained for different values of these parameters. The k-set problem can be viewed in this framework as a form of parametric median-finding, in which the set of elements have values that are linear functions of a single time parameter; I have also looked at other similar parametric matroid problems as well as some parametric geometry problems.
\- \!pure Most of my research is in the design and analysis of algorithms, but some of my papers are completely non-algorithmic, instead consisting of theorems about graphs or combinatorial geometry. Some other papers, while primarily about algorithms, also contain non-algorithmic content of independent interest.
\- \!rec These papers are mainly for fun, although there is also some serious research content to some of them. See also my recreational mathematics web pages.
\- \!graph:sgi Subgraph isomorphism is a very general form of pattern matching in which one attempts to find a target graph as a subgraph of a larger input graph. It is NP-complete, but it has many applications and algorithms are known for many special cases. See also my bibliography of subgraph isomorphism algorithms and applications, which I collected for my SODA 95 paper.
\- \!a:cgitf The Computational Geometry Impact Task Force was organized by Bernard Chazelle, and consisted of N. Amenta, T. Asano, G. Barequet, M. Bern, J.-D. Boissonnat, J. Canny, B. Chazelle, K. Clarkson, D. Dobkin, B. Donald, R. S. Drysdale, H. Edelsbrunner, D. Eppstein, A. R. Forrest, S. Fortune, K. Goldberg, M. Goodrich, L. J. Guibas, P. Hanrahan, C. M. Hoffman, D. Huttenlocher, H. Imai, D. Kirkpatrick, D. T. Lee, K. Mehlhorn, V. Milenkovic, J. Mitchell, M. Overmars, R. Pollack, R. Seidel, M. Sharir, J. Snoeyink, G. Toussaint, S. Teller, H. Voelcker, E. Welzl, and C. Yap. (I am not listing this under my co-author publication lists for each individual member of the task force.)
\- \################################################################# \# the papers themselves \################################################################# \# start unnumbered list of papers \# roughly sorted by date of final version \+ \!top \!geom \!graph \!auth \!subj \!year \!conf \!jour
-
\-
\!all
\!gdraw
\!a:solo
\!c:no
\!j:other
\!y:1985
- Trees in TeX.
D. Eppstein.
TUGboat 6(1):31, 1985.This note in the TeX user's group newsletter described a set of macros for drawing trees, using TeX's boxes-and-glue mechanisms to line up the nodes at each level of the tree.
(BibTeX -- TeX source code -- Citations -- Nelson Beebe's TeX tree drawing bibliography)
\- \!all \!misc \!a:solo \!c:other \!j:no \!p:proginv \!y:1985
- A heuristic approach to program inversion.
D. Eppstein.
9th Int. Joint Conf. Artificial Intelligence, Los Angeles, 1985, pp. 219-221.Program transformation. Given a (lisp) program for an invertible function, how do we automatically find a program for the inverse function? Considers more general simultaneous inverses of multiple functions. The heuristic part involves type inference for finding conditionals to use in certain if statements.
(BibTeX -- MacLISP source code -- Kawabe's Common Lisp port -- Citations -- CiteSeer)
\- \!all \!rec \!a:solo \!c:no \!j:other \!p:cryptarithm \!y:1987
- On the NP-completeness of cryptarithms.
D. Eppstein.
SIGACT News 18(3):38-40, 1987.A cryptarithm (also known as an alphametic) is a puzzle in which the digits of a mathematical formula (typically addition of two large numbers) are replaced by letters; the goal is to determine which letter stands for which digits. If arithmetic is done in a polynomially large radix, the problem becomes NP-complete.
(BibTeX -- Full paper -- Citations)
\- \!all \!molbio \!a:galil \!a:giancarlo \!p:speeding \!c:focs \!c:other \!j:book \!y:1988 \!y:1990
- 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-Verlag, 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.
(Bibtex: Positano, FOCS -- Citations -- Citations of "Efficient algorithms..." -- MIT hypertext bibliography -- CiteSeer)
\- \!all \!molbio \!a:solo \!y:1989
- Efficient algorithms for sequence analysis with concave and convex gap costs.
D. Eppstein.
Ph.D. thesis, Columbia University, 1989.Includes results from "Speeding up dynamic programming", "Sequence comparison with mixed convex and concave costs", and "Sparse dynamic programming".
(BibTeX)
\- \!all \!molbio \!a:solo \!c:no \!j:algs \!p:mixed \!y:1988 \!y:1990
- 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.
(BibTeX -- Citations -- ACM DL)
\- \!all \!misc \!par \!a:solo \!c:icalp \!j:sjc \!y:1988 \!y:1990
- Reset sequences for monotonic automata.
D. Eppstein.
15th Int. Coll. Automata, Languages and Programming, Tampere, Finland, 1988.
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.
(BibTeX -- Citations -- CiteSeer -- ACM DL (ICALP) -- ACM DL (SJC))
\- \!all \!misc \!par \!a:solo \!y:1989
- On reset sequence length.
D. Eppstein.
Tech. Rep. CUCS-440-89, Computer Science Dept., Columbia University, 1989.(BibTeX)
\- \!all \!par \!graph:all \!graph:misc \!survey \!a:galil \!c:icalp \!j:other \!y:1988 \!y:1989
- 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.
Lecture Notes in Comp. Sci. 372, 1989, pp. 304-318, © Springer-Verlag.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.
(BibTeX -- Citations -- CiteSeer -- ACM DL (ARCS) -- ACM DL (ICALP))
\- \!all \!geom:all \!geom:misc \!pure \!a:bern \!a:plassman \!a:yao \!c:no \!j:book \!y:1991
- 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 α(n,k)). The first bound is tight, but it remains open whether the second is, or whether only linear complexity is possible.
\- \!all \!pure \!geom:all \!geom:tri \!a:bern \!a:yao \!c:icalp \!j:ijcga \!y:1991
- The expected extremes in a Delaunay triangulation.
M. Bern, D. Eppstein, and F. Yao.
18th Int. Coll. Automata, Languages and Programming, Madrid, Spain, 1991.
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 bounded to within a constant factor of log n / log log n.
(BibTeX -- Citations -- CiteSeer -- ACM DL -- ACM DL (2))
\- \!all \!graph:all \!graph:sgi \!graph:planar \!par \!a:chrobak \!c:no \!j:tcs \!p:outdegree \!y:1991
- Planar orientations with low out-degree and compaction of adjacency matrices.
M. Chrobak and D. Eppstein.
Theor. Comp. Sci. 86(2):243-266, 1991.Describes efficient sequential and parallel algorithms for orienting the edges of an undirected planar graph so that each vertex has few outgoing edges. From such an orientation one can test in constant time whether a given edge exists. \!par One consequence is a parallel algorithm to list all subgraphs isomorphic to K3 or K4. \!par \!graph:sgi More recently this paper has been cited for its applications to scheduling update operations in parallel finite element methods. \!graph:sgi
(BibTeX -- Citations -- CiteSeer -- ACM DL)
\- \!all \!pure \!graph:all \!graph:random \!a:feigenbaum \!a:li \!c:no \!j:dm \!y:1991
- Equipartitions of graphs.
D. Eppstein, J. Feigenbaum, and C.L. Li.
Discrete Mathematics 91(3):239-248, 1991.Considers partitions of the vertices of a graph into equal subsets, with few pairs of subsets connected by edges. (Equivalently we view the graph as a subgraph of a product in which one factor is sparse.) A random graph construction shows that such a factorization does not always exist.
(BibTeX -- Full paper -- CiteSeer -- ACM DL)
\- \!all \!par \!graph:all \!graph:match \!a:asuri \!a:dillencourt \!a:lueker \!a:molodowitch \!c:no \!j:no \!y:1992
- Fast optimal parallel algorithms for maximal matching in sparse graphs.
H. Asuri, M. Dillencourt, D. Eppstein, G. Lueker, and M. Molodowitch.
Tech. Rep. 92-01, ICS, UCI, 1992.We later discovered that the same results were published in a SPAA paper by Greg Shannon.
(BibTeX)
\- \!all \!pure \!geom:all \!geom:kset \!a:sol \!c:no \!j:no \!y:1992
- Sets of points with many halving lines.
D. Eppstein.
Tech. Rep. 92-86, ICS, UCI, 1992.I used genetic algorithms to search for small configurations of points bisected by lines in many combinatorially distinct ways.
\- \!all \!geom:all \!geom:cluster \!a:overmars \!a:rote \!a:woeginger \!c:no \!j:dcg \!y:1992
- Finding minimum area k-gons.
D. Eppstein, M. Overmars, G. Rote, and G. Woeginger.
Disc. Comp. Geom. 7(1):45-58, 1992.Uses dynamic programming to choose sets of k points optimizing various criteria on the quality of their convex hull (in particular area). The time complexity (cubic in n) was later improved to quadratic in my paper "New algorithms for minimum area k-gons", which however continues to use the same dynamic program as a subroutine.
(BibTeX -- Citations -- CiteSeer -- ACM DL)
\- \!all \!misc \!a:hemachandra \!a:tisdall \!a:yener \!c:other \!j:mst \!y:1989 \!y:1990 \!y:1992
- 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 BPP (a probabilistic complexity class) and 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".
(BibTeX: ICCI, MST -- Citations: ICCI, MST -- CiteSeer)
\- \!all \!graph:all \!mst \!graph:dyn \!graph:planar \!a:italiano \!a:tamassia \!a:tarjan \!a:westbrook \!a:yung \!c:soda \!j:algs \!p:eittwy \!y:1990 \!y:1992 \!y:1993
- 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.
(BibTeX -- Citations -- CiteSeer -- ACM DL)
\- \!all \!pure \!geom:all \!geom:tri \!a:solo \!c:no \!j:cgta \!y:1990 \!y:1992
- 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.
(BibTeX -- Citations -- CiteSeer -- ACM DL)
\- \!all \!par \!pure \!graph:all \!graph:misc \!a:solo \!c:no \!p:serpar \!j:ic \!y:1992
- Parallel recognition of series parallel graphs.
D. Eppstein.
Information & Computation 98:41-55, 1992.Characterizes two-terminal series graphs in terms of a tree-like structure in their ear decompositions. \!pure Uses this characterization to construct parallel algorithms that recognize these graphs and construct their series-parallel decompositions. \!pure
(BibTeX -- Citations -- MIT hypertext bibliography -- CiteSeer -- ACM DL)
\- \!all \!kbest \!graph:all \!mst \!geom:all \!mst \!a:solo \!c:swat \!j:bit \!p:kmst \!y:1990 \!y:1992
- Finding the k smallest spanning trees.
D. Eppstein.
2nd Scand. Worksh. Algorithm Theory, Bergen, Norway, 1990.
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.
(BibTeX -- Citations -- ACM DL (SWAT) -- ACM DL (BIT))
\- \!all \!molbio \!usesgeom \!a:galil \!a:giancarlo \!a:italiano \!c:soda \!p:sparsedp \!y:1990
- 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.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.
\- \!all \!molbio \!usesgeom \!a:galil \!a:giancarlo \!a:italiano \!j:acm \!p:sparsedp \!y:1989 \!y:1992
- Sparse dynamic programming I: linear cost functions.
D. Eppstein, Z. Galil, R. Giancarlo, and G.F. Italiano.
Tech. Rep. CUCS-471-89, Computer Science Dept., Columbia University, 1989.
J. ACM 39:519-545, 1992.First half of the journal version of Sparse dynamic programming.
(Citations -- MIT hypertext bibliography)
\- \!all \!molbio \!usesgeom \!a:galil \!a:giancarlo \!a:italiano \!j:acm \!p:sparsedp \!y:1989 \!y:1992
- Sparse dynamic programming II: convex and concave cost functions.
D. Eppstein, Z. Galil, R. Giancarlo, and G.F. Italiano.
Tech. Rep. CUCS-472-89, Computer Science Dept., Columbia University, 1989.
J. ACM 39:546-567, 1992.Second half of the journal version of Sparse dynamic programming.
(Citations -- MIT hypertext bibliography)
\- \!all \!geom:all \!geom:tri \!a:bern \!c:scg \!j:ijcga \!p:nonobtuse \!y:1991 \!y:1992
- Polynomial-size non-obtuse triangulation of polygons.
M. Bern and D. Eppstein.
7th ACM Symp. Comp. Geom., North Conway, New Hampshire, 1991, pp. 342-350.
Int. J. Comp. Geom. & Appl. 2:241-255, 1992 (special issue for 7th Symp. Comput. Geom.).Any simple polygon can be triangulated with quadratically many nonobtuse triangles. Mostly subsumed by recent results of Bern et al described in "Faster circle packing".
(BibTeX -- Citations -- CiteSeer)
\- \!all \!molbio \!a:galil \!a:giancarlo \!a:italiano \!c:other \!j:book \!y:1991 \!y:1993 \!survey
- 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-Verlag, 1993, pp. 225-244.
Surveys results on speeding up certain dynamic programs used for sequence comparison and RNA structure prediction.
(BibTeX -- Citations -- CiteSeer)
\- \!all \!pure \!geom:all \!geom:kset \!a:solo \!c:no \!j:jct \!y:1991 \!y:1993
- Improved bounds for intersecting triangles and halving planes.
D. Eppstein.
Tech. Rep. 91-60, ICS, UCI, 1991.
J. Combinatorial Theory Ser. A 62:176-182, 1993.Reduces the polylogarithmic term in an upper bound for the three-dimensional k-set problem.
A bug in the proof was corrected by Nivasch and Sharir.
(BibTeX -- Citations -- CiteSeer -- ACM DL)
\- \!all \!graph:all \!graph:sgi \!graph:planar \!ramsey \!pure \!a:solo \!c:no \!j:jgt \!p:conmin \!y:1992 \!y:1993
- Connectivity, graph minors, and subgraph multiplicity.
D. Eppstein.
Tech. Rep. 92-06, ICS, UCI, 1992.
J. Graph Th. 17:409-416, 1993.It was known that planar graphs have O(n) subgraphs isomorphic to K3 or K4. This paper characterizes the subgraphs for which such a linear bound holds: they are exactly the 3-connected planar graphs. Please note that the Tech. Rep. version had a bug (in a supposed generalization of the result to nonplanar graph families) which was corrected in the journal version.
(BibTeX -- Citations -- CiteSeer -- ACM DL)
\- \!all \!geom:all \!geom:tri \!a:bern \!a:edelsbrunner \!a:smitchell \!a:tan \!c:other \!j:dcg \!y:1992 \!y:1993
- Edge insertion for optimal triangulations.
M. Bern, H. Edelsbrunner, D. Eppstein, S. Mitchell, and T.S. Tan.
1st Latin Amer. Symp. Theoretical Informatics, Sao Paulo, 1992.
Lecture Notes in Comp. Sci. 583, 1992, pp. 46-60.
Tech. Rep. EDC UILU-ENG-92-1702, Univ. Illinois, Urbana-Champaign, 1992.
Disc. & Comp. Geom. 10:47-65, 1993.One standard way of constructing Delaunay triangulations is by iterated local improvement, in which each step flips the diagonal of some quadrilateral. For many other optimal triangulation problems, flipping is insufficient, but the problems can instead be solved by a more general local improvement step in which a new edge is added to the triangulation, cutting through several triangles, and the region it cuts through is retriangulated on both sides.
(BibTeX -- Citations -- CiteSeer -- ACM DL)
\- \!all \!geom:all \!geom:misc \!param \!a:bern \!a:dobkin \!a:grossman \!c:soda \!j:algo \!y:1990 \!y:1994
- 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.
\- \!all \!par \!graph:all \!graph:misc \!a:chrobak \!a:italiano \!a:yung \!c:soda \!j:no \!y:1991
- Efficient sequential and parallel algorithms for
computing recovery points in trees and paths.
M. Chrobak, D. Eppstein, G.F. Italiano, and M. Yung.
2nd ACM-SIAM Symp. Discrete Algorithms, San Francisco, 1991, pp. 158-167.
ALCOM Report 91-74, University of Rome, 1991.Described slightly superlinear algorithms for partitioning a tree into a given number of subtrees, making them all as short as possible. Frederickson at the same conference further improved the sequential time to linear. There may still be something worth publishing in the parallel algorithms.
\- \!all \!geom:all \!geom:tri \!geom:qt \!a:bern \!a:gilbert \!c:focs \!j:jcss \!p:pgood \!y:1990 \!y:1994
- 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).Uses quadtrees to construct triangulations with extra Steiner vertices added to the original input. Triangulates planar point sets and polygons, with all angles bounded away from zero, using a number of triangles within a constant of optimal. Triangulates planar point sets with all angles non-obtuse, using linearly many triangles. Triangulates higher dimensional point sets with no small solid angles and a number of simplices within a constant of optimal. Augments any higher dimensional point set so the Delaunay triangulation has linear complexity.
(BibTeX -- Citations -- Preliminary copy of journal version -- MIT hypertext bibliography -- CiteSeer -- ACM DL (JCSS))
\- \!all \!geom:all \!geom:dyn \!geom:cluster \!geom:lp \!a:solo \!c:focs \!j:ojc \!p:3lp \!y:1991 \!y:1992
- Dynamic three-dimensional linear programming.
D. Eppstein.
Tech. Rep. 91-53, ICS, UCI, 1991.
32nd IEEE Symp. Foundations of Comp. Sci., San Juan, Puerto Rico, 1991, pp. 488-494.
ORSA J. Computing 4:360-368, 1992 (special issue on computational geometry).Uses Dobkin-Kirkpatrick hierarchies to perform linear programming queries in the intersection of several convex polyhedra. By maintaining a collection of halfspaces as several subsets, represented by polyhedra, this leads to algorithms for a dynamic linear program in which updates change the set of constraints. The fully dynamic results have largely been subsumed by Agarwal and Matoušek, but this paper also includes polylog time results for semi-online problems, and uses them to give a fast randomized algorithm for the planar 2-center problem (later improved by various authors, most recently in "Faster Construction of Planar Two-Centers", which re-uses the data structures described here).
(BibTeX -- Citations -- CiteSeer -- ACM DL)
\- \!all \!misc \!a:solo \!c:no \!j:no \!y:1991
- Persistence, offline algorithms, and space compaction.
D. Eppstein.
Tech. Rep. 91-54, ICS, UCI, 1991.Considers persistence for a naive form of dynamic algorithm in which each update rebuilds a static solution. The space bounds for this can often be reduced by maintaining an offline solution over a sequence of updates constructed from an Euler tour of the persistent update history tree.
(BibTeX)
\- \!all \!pure \!geom:all \!geom:tri \!geom:qt \!geom:approx \!mst \!a:solo \!c:soda \!j:dcg \!p:mwst \!y:1991 \!y:1992 \!y:1994
- Approximating the minimum weight Steiner triangulation.
D. Eppstein.
Tech. Rep. 91-55, ICS, UCI, 1991.
3rd ACM-SIAM Symp. Discrete Algorithms, Orlando, 1992, pp. 48-57.
Disc. Comp. Geom. 11:163-191, 1994.Quadtree based triangulation gives a large but constant factor approximation to the minimum weight triangulation of a point set or convex polygon, allowing extra Steiner points to be added as vertices. Includes proofs of several bounds on triangulation weight relative to the minimum spanning tree or non-Steiner triangulation, and a conjecture that for convex polygons the only points that need to be added are on the polygon boundary.
(BibTeX -- Citations -- CiteSeer)
\- \!all \!geom:all \!geom:cluster \!ramsey \!a:solo \!c:soda \!p:kgon \!y:1991 \!y:1992
- New algorithms for minimum area k-gons.
D. Eppstein.
Tech. Rep. 91-59, ICS, UCI, 1991.
3rd ACM-SIAM Symp. Discrete Algorithms, Orlando, 1992, pp. 83-86.Shows that the minimum area polygon containing k of n points must be near a line determined by two points, and uses this observation to find the polygon quickly. Merged with "Iterated nearest neighbors and finding minimal polytopes" in the journal version.
\- \!all \!geom:all \!geom:cluster \!a:erickson \!c:no \!j:no \!y:1992
- New algorithms for minimum measure simplices and one-dimensional
weighted Voronoi diagrams.
D. Eppstein and J. Erickson.
Tech. Rep. 92-55, ICS, UCI, 1992.Looks at space complexity of finding minimum simplices -- solves the problem in O(n2) space and O(nd) time (matching the best known time bounds) or in linear space at the expense of an additional log in time. Also finds one-dimensional multiplicatively weighted Voronoi diagrams in linear time for sorted inputs (O(n log n) was known).
(BibTeX -- Citations -- Jeff's pub list entry)
\- \!all \!geom:all \!geom:nn \!geom:cluster \!geom:deep \!a:erickson \!c:soda \!j:dcg \!p:inn \!y:1992 \!y:1993 \!y:1994 \!kbest
- Iterated nearest neighbors and finding minimal polytopes.
D. Eppstein and J. Erickson.
Tech. Rep. 92-71, ICS, UCI, 1992.
4th ACM-SIAM Symp. Discrete Algorithms, Austin, 1993, pp. 64-73.
Disc. Comp. Geom. 11:321-350, 1994.Showed that for various optimization criteria, the optimal polygon containing k of n points must be near one of the points, hence one can transform time bounds involving several factors of n to bounds linear in n but polynomial in k. Used as a subroutine are data structures for finding several nearest neighbors in rectilinear metric spaces, and algorithms for finding the deepest point in an arrangement of cubes or spheres.
(BibTeX -- Citations -- Jeff's pub list entry -- CiteSeer)
\- \!all \!kbest \!geom:all \!mst \!a:solo \!c:no \!j:ijcga \!y:1992 \!y:1994
- Tree-weighted neighbors and geometric k smallest spanning trees.
D. Eppstein.
Tech. Rep. 92-77, ICS, UCI, 1992.
Int. J. Comp. Geom. & Appl. 4:229-238, 1994."Finding the k smallest spanning trees" used higher order Voronoi diagrams to reduce the geometric k smallest spanning tree problem to the graph problem. Here I instead use nearest neighbors for a modified distance function where the bottleneck shortest path length is subtracted from the true distance between points. The result improves the planar time bounds and extends more easily to higher dimensions.
\- \!all \!param \!pure \!geom:all \!mst \!a:aronov \!a:bern \!c:no \!j:dcg \!y:1994
- On the number of minimal 1-Steiner trees.
B. Aronov, M. Bern, and D. Eppstein.
Disc. & Comp. Geom. 12:29-34, 1994.Given a d-dimensional set of n points, the number of combinatorially different minimum spanning trees that can be formed by adding one more point is within a polylogarithmic factor of nd.
(BibTeX -- Citations -- CiteSeer)
\- \!all \!pure \!graph:all \!graph:sgi \!a:solo \!c:no \!j:ipl \!p:asgi \!y:1994
- Arboricity and bipartite subgraph listing algorithms.
D. Eppstein.
Tech. Rep. 94-11, ICS, UCI, 1994.
Inf. Proc. Lett. 51:207-211, 1994.For any sparse family of graphs, one can list in linear time all complete bipartite subgraphs of a graph in the family. There are O(n) complete bipartite subgraphs of a graph in the family, and the sum of the numbers of vertices in these subgraphs is also O(n).
Nowadays these results can also be interpreted as a form of formal concept analysis. If a set of objects and attributes is sparse (e.g., if it is generated by adding objects and attributes one at a time, where each newly-added object is given O(1) attributes and each newly-added attribute is held by O(1) objects) then the total size of all concepts in its concept lattice is linear, and this lattice may be generated in linear time.
(BibTeX -- Citations -- CiteSeer -- ACM DL)
\- \!all \!graph:all \!graph:dyn \!mst \!geom:all \!geom:dyn \!mst \!a:solo \!c:wads \!j:algs \!y:1991 \!y:1992 \!y:1994
- Offline algorithms for dynamic minimum spanning tree problems.
D. Eppstein.
2nd Worksh. Algorithms and Data Structures, Ottawa, Canada, 1991.
Lecture Notes in Comp. Sci. 519, 1991, pp. 392-399.
Tech. Rep. 92-04, ICS, UCI, 1992.
J. Algorithms 17:237-250, 1994.Given a sequence of edge insertions and deletions in a graph, finds the corresponding sequence of minimum spanning tree changes, in logarithmic time per update. Similarly solves the planar geometric version of the problem (using a novel "mixed MST" formulation in which part of the input is a graph and part is a point set) in time O(log2 n) for the Euclidean metric and O(log n log log n) for the rectilinear metric.
(BibTeX -- Citations -- CiteSeer -- ACM DL (JA))
\- \!all \!geom:all \!geom:dyn \!mst \!geom:nn \!a:solo \!j:dcg \!y:1992 \!y:1995 \!p:dynmst
- Dynamic Euclidean minimum spanning trees and extrema of binary functions.
D. Eppstein.
Tech. Rep. 92-05, ICS, UCI, 1992.
Tech. Rep. 92-88, ICS, UCI, 1992.
Disc. Comp. Geom. 13:111-122, 1995.Shows that bichromatic nearest neighbors can be maintained under point insertion and deletion essentially as quickly as known solutions to the post office problem, and that the minimum spanning tree can be maintained in the same time except for an additive O(sqrt n) needed for solving the corresponding graph problem. TR 92-88's title was actually "Fully dynamic maintenance of Euclidean minimum spanning trees and maxima of decomposable functions". TR 92-05's title left out the part about maxima; that version gave a slower algorithm superseded by the result in 92-88.
(BibTeX -- Citations -- Closest pair project page -- CiteSeer)
\- \!all \!geom:all \!geom:dyn \!mst \!geom:nn \!a:agarwal \!a:matousek \!c:focs \!p:dynhalf \!y:1992
- Dynamic algorithms for half-space reporting, proximity problems, and
geometric minimum spanning trees.
P.K. Agarwal, D. Eppstein, and J. Matoušek.
33rd IEEE Symp. Foundations of Comp. Sci., Pittsburgh, 1992, pp. 80-89.This conference paper merged my results from "Dynamic Euclidean minimum spanning trees" with results of my co-authors on nearest neighbors and halfspace range searching.
\- \!all \!graph:path \!kbest \!rec \!survey \!a:solo \!c:no \!j:other \!p:egypt \!y:1995
- Ten algorithms for Egyptian fractions.
D. Eppstein.
Mathematica in Education and Research 4(2):5-15, 1995.Number theory. I survey and implement in Mathematica several methods for representing rational numbers as sums of distinct unit fractions. One of the methods involves searching for paths in a certain graph using a k shortest paths heuristic.
(BibTeX -- Citations -- Also available in HTML and Mathematica notebook formats)
\- \!all \!geom:all \!geom:misc \!graph:dyn \!a:solo \!c:no \!j:algo \!p:csg \!y:1992 \!y:1995
- Asymptotic speed-ups in constructive solid geometry.
D. Eppstein.
Tech. Rep. 92-87, ICS, UCI, 1992.
Algorithmica 13:462-471, 1995.Finds boundary representations of CSG objects. Uses techniques from dynamic graph algorithms, including a tree partitioning technique of Frederickson and a new data structure for maintaining the value of a Boolean expression with changing variables in time O(log n / log log n) per update.
\- \!all \!geom:all \!geom:tri \!a:solo \!y:1991
- Subquadtratic nonobtuse triangulation of convex polygons.
D. Eppstein.
Tech. Rep. 91-61, ICS, UCI, 1991.This was merged into "triangulating polygons without large angles". We find a grid-like structure in the input polygon, which is then thinned out using a complicated divide-and-conquer scheme. The results are largely subsumed by the method of Bern et al. described in "Faster circle packing".
(BibTeX)
\- \!all \!geom:all \!geom:tri \!a:bern \!a:dobkin \!c:scg \!j:ijcga \!p:nolarge \!y:1992 \!y:1995
- Triangulating polygons without large angles.
M. Bern, D. Dobkin, and D. Eppstein.
8th ACM Symp. Comp. Geom., Berlin, 1992, pp. 222-231.
Int. J. Comp. Geom. & Appl. 5:171-192, 1995 (special issue for 8th Symp. Comput. Geom.)Follows up "Polynomial size non-obtuse triangulation of polygons"; improves the number of triangles by relaxing the requirements on their angles. Again mostly subsumed by results of Bern et al described in "Faster circle packing".
(BibTeX -- Citations -- CiteSeer)
\- \!all \!survey \!geom:all \!geom:tri \!a:bern \!c:no \!j:book \!p:meshgen \!y:1992 \!y:1995
- 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; also online is this paper's bibliography.
(BibTeX -- Citations -- CiteSeer)
\- \!all \!geom:all \!geom:deep \!geom:circle \!a:miller \!a:teng \!c:scg \!j:other \!y:1993 \!y:1995
- A deterministic linear time algorithm for geometric separators
and its applications.
D. Eppstein, G.L. Miller, and S.-H. Teng.
9th ACM Symp. Comp. Geom., San Diego, 1993, pp. 99-108.
Fundamenta Informaticae 22:309-330, 1995 (special issue on computational geometry).Teng and others previously showed that certain geometric graphs had small separators that could be found by lifting the graph to a sphere one dimension up and choosing a random great circle. Here we show that epsilon-cuttings and the method of conditional expectations can be used to guide a deterministic prune-and-search method for the same problem. Applications include finding the intersection graph of a collection of spheres and computing or approximating the maximum number of spheres having a common intersection.
(BibTeX -- Citations -- CiteSeer)
\- \!all \!graph:all \!graph:dyn \!mst \!kbest \!a:galil \!a:italiano \!a:nissenzweig \!c:focs \!j:acm \# submitted to Leighton for JACM, 18 Jan 1993 \# revised May 1996 \!p:sparsification \!y:1992 \!y:1993 \!y:1997
- Sparsification--A technique for speeding up dynamic graph algorithms.
D. Eppstein, Z. Galil, G.F. Italiano, and A. Nissenzweig.
33rd IEEE Symp. Foundations of Comp. Sci., Pittsburgh, 1992, pp. 60-69.
Tech. Rep. RC 19272 (83907), IBM, 1993.
Tech. Rep. CS96-11, Univ. Ca' Foscari di Venezia, Oct. 1996.
J. ACM 44(5):669-696, 1997.Uses a divide and conquer on the edge set of a graph, together with the idea of replacing subgraphs by sparser certificates, to make various dynamic algorithms as fast on dense graphs as they are on sparse graphs. Applications include random generation of spanning trees as well as finding the k minimum weight spanning trees for a given parameter k.
(BibTeX -- Citations -- MIT hypertext bibliography -- ACM DL)
\- \!all \!graph:all \!graph:dyn \!mst \!kbest \!a:galil \!a:italiano \!c:no \!y:1993
- Improved sparsification.
D. Eppstein, Z. Galil, and G.F. Italiano.
Tech. Rep. 93-20, ICS, UCI, 1993.Saves a log factor over dynamic graph algorithms in "Sparsification" and their applications, by dividing vertices instead of edges. Merged into the journal version of "Sparsification".
(BibTeX -- Citations -- CiteSeer)
\- \!all \!graph:all \!graph:dyn \!mst \!graph:planar \!kbest \!a:galil \!a:italiano \!a:spencer \!c:stoc \!p:egis \!y:1993
- Separator based sparsification for dynamic planar graph algorithms.
D. Eppstein, Z. Galil, G.F. Italiano, and T. Spencer.
25th ACM Symp. Theory of Computing, San Diego, 1993, pp. 208-217.Replaces portions of a hierarchical separator decomposition with smaller certificates to achieve fast update times for various dynamic planar graph problems. Applications include finding the k best spanning trees of a planar graph.
(BibTeX -- Citations -- MIT hypertext bibliography)
\- \!all \!graph:all \!graph:dyn \!mst \!graph:planar \!kbest \!a:galil \!a:italiano \!a:spencer \!j:jcss \!p:egis \!y:1996
- Separator based sparsification I:
planarity testing and minimum spanning trees.
D. Eppstein, Z. Galil, G.F. Italiano, and T. Spencer.
J. Comp. Sys. Sci. 52:3-27, 1996 (special issue for 25th STOC).First half of journal version of Separator based sparsification for dynamic planar graph algorithms.
\- \!all \!graph:all \!graph:dyn \!graph:planar \!a:galil \!a:italiano \!a:spencer \!j:sjc \!p:egis \!y:1996 \!y:1999
- Separator based sparsification II: edge and vertex connectivity.
D. Eppstein, Z. Galil, G.F. Italiano, and T. Spencer.
Tech. Rep. CS96-13, Univ. Ca' Foscari di Venezia, Oct. 1996.
SIAM J. Computing 28(1):341-381, 1999.Second half of journal version of Separator based sparsification for dynamic planar graph algorithms.
\- \!all \!geom:all \!geom:qt \!geom:tri \!geom:nn \!kbest \!a:dickerson \!c:no \!j:cgta \!p:k-neighbors \!y:1996
- Algorithms for proximity problems in higher dimensions.
M. T. Dickerson and D. Eppstein.
Comp. Geom. Theory & Applications 5:277-291, 1996.Combines a method from "Provably good mesh generation" for finding sparse high-dimensional Delaunay triangulations, a method of Dickerson, Drysdale, and Sack ["Simple algorithms for enumerating interpoint distances", IJCGA 1992] for using Delaunay triangulations to search for nearest neighbors, and a method of Frederickson for speeding up tree-based searches. The results are fast algorithms for several proximity problems such as finding the k nearest neighbors to each point in a given point set.
(BibTeX -- Full paper -- Citations -- CiteSeer -- ACM DL)
\- \!all \!geom:all \!geom:dyn \!mst \!a:solo \!c:soda \!j:cgta \!p:avgdynopt \!y:1993 \!y:1994 \!y:1996
- Average case analysis of dynamic geometric optimization.
D. Eppstein.
Tech. Rep. 93-18, ICS, UCI, 1993.
5th ACM-SIAM Symp. Discrete Algorithms, Arlington, 1994, pp. 77-86.
Comp. Geom. Theory & Applications 6:45-68, 1996.The Tech. Report used the more informative title "Updating widths and maximum spanning trees using the rotating caliper graph", which I also used for the journal submission, but the referees made me change it back. Dynamic geometry in a model of Mulmuley and Schwarzkopf in which insertions and deletions are chosen randomly among a worst-case pool of points. This paper introduces several fundamental techniques including the rotating caliper graph of a point set and a method for performing decomposible range queries in the average case setting. It has also since inspired the use of a similar model in dynamic graph algorithms.
(BibTeX -- SODA paper -- Full paper -- Citations -- CiteSeer -- ACM DL)
\- \!all \!geom:all \!geom:dyn \!a:solo \!c:wcg \!y:1993
- Dynamic geometric optimization.
D. Eppstein.
Invited talk, 3rd MSI Worksh. Computational Geometry, 1993, p. 14.
\- \!all \!geom:all \!geom:dyn \!geom:deep \!a:dobkin \!c:scg \!p:disc \!y:1993
- Computing the discrepancy.
D. P. Dobkin and D. Eppstein.
9th ACM Symp. Comp. Geom., San Diego, 1993, pp. 47-52.Measures how well a sample of points from a set works as a discrete approximation to the continuous measure of shapes in the set, using algorithms based on Overmars and van Leeuwen's dynamic convex hull data structure. Some versions of the problem also involve subroutines for finding the deepest point in an arrangement of quadrants or orthants.
This paper was merged with results of Mitchell to form the journal version, "Computing the discrepancy with applications to supersampling patterns".
\- \!all \!geom:all \!geom:dyn \!geom:deep \!a:dobkin \!a:dmitchell \!j:other \!p:supersample \!y:1996
- Computing the discrepancy with applications to supersampling patterns.
D. P. Dobkin, D. Eppstein, and D. P. Mitchell.
ACM Trans. on Graphics 15(4):354-376, 1996.Combines "Computing the discrepancy" with experimental results of Mitchell on the discrepancies of various point sets, emphasizing the application of low-discrepancy sets to anti-aliasing in raytraced graphics.
(BibTeX -- Citations -- CiteSeer -- ACM DL)
\- \!all \!geom:all \!geom:circle \!geom:tri \!mst \!graph:dyn \!a:solo \!c:no \!j:ijcga \!p:cpack \!y:1994 \!y:1997 \# submitted to D.T.Lee for IJCGA, 31 Oct 1994 \# accepted subject to revision by Goodrich 15 Jun 1995 \# sent final version 29 Jun 1995 \# recd & returned offprint request listing as V7 N5 (Oct 1997), 28 Jul 1997
- Faster circle packing with application to nonobtuse triangulation.
D. Eppstein.
Tech. Rep. 94-33, ICS, UCI 1994.
Int. J. Comp. Geom. & Appl. 7(5):485-491, 1997.Speeds up a triangulation algorithm of Bern et al. ["Linear-Size Nonobtuse Triangulation of Polygons"] by finding a collection of disjoint circles which connect up the holes in a non-simple polygon. The method is to use a minimum spanning tree to find a collection of overlapping circles, then shrink them one by one to reduce the number of overlaps, using Sleator and Tarjan's dynamic tree data structure to keep track of the connectivity of the shrunken circles.
\- \!all \!geom:all \!geom:approx \!geom:deep \!geom:lp \!stat \!a:clarkson \!a:miller \!a:sturtivant \!a:teng \!c:scg \!j:ijcga \!y:1993 \!y:1996
- Approximating center points with iterated Radon points.
K. Clarkson, D. Eppstein, G.L. Miller, C. Sturtivant, and S.-H. Teng.
9th ACM Symp. Comp. Geom., San Diego, 1993, pp. 91-98.
Int. J. Comp. Geom. & Appl. 6(3):357-377, 1996.Given a collection of n sites, a center point is a point (not necessarily a site) such that no hyperplane through the centerpoint partitions the collection into a very small and a very large subset. Center points have been used by Teng and others as a key step in the construction of geometric separators. One can find a point with this property by choosing a random sample of the collection and applying linear programming, but the complexity of that method grows exponentially with the dimension. This paper proposes an alternate method that produces lower quality approximations (in terms of the size of the worst hyperplane partition) but takes time polynomial in both n and d.
(BibTeX -- Citations -- Full paper and source code -- CiteSeer)
\- \!all \!geom:all \!mst \!geom:path \!graph:all \!graph:match \!tsp \!pure \!a:bern \!c:scg \!p:subadditive \!j:no \!y:1993
- Worst-case bounds for subadditive geometric graphs.
M. Bern and D. Eppstein.
9th ACM Symp. Comp. Geom., San Diego, 1993, pp. 183-188.For many geometric graph problems for points in the unit square, such as minimum spanning trees, matching, and traveling salesmen, the sum of edge lengths is O(sqrt n) and the sum of dth powers of edge lengths is O(log n). We provide a "gap theorem" showing that if these bounds do not hold for a class of graphs, both sums will instead be Omega(n). For traveling salesmen the O(log n) bound is tight but for some other graphs the sum of dth powers of edge lengths is O(1).
(BibTeX -- Citations -- Preprint of SCG version -- CiteSeer)
\- \!all \!geom:all \!geom:tri \!geom:cluster \!geom:nn \!geom:qt \!par \!a:bern \!a:teng \!c:wads \!j:ijcga \# sent to DT Lee for IJCGA, 26 Jul 1996 \# accepted subject to revisions 18 Feb 1997 \# returned final version 25 May 1999 \!p:parallel-qt \!y:1993 \!y:1994 \!y:1999
- Parallel construction of quadtrees and quality triangulations.
M. Bern, D. Eppstein, and S.-H. Teng.
3rd Worksh. Algorithms and Data Structures, Montreal, 1993.
Lecture Notes in Comp. Sci. 709, 1993, pp. 188-199, © Springer-Verlag.
Tech. Rep. 614, MIT Lab. for Comp. Sci., 1994.
Int. J. Comp. Geom. & Appl. 9(6):517-532, 1999.A parallelization of the quadtree constructions in "Provably good mesh generation", in an integer model of computation, based on a technique of sorting the input points using values formed by shuffling the binary representations of the coordinates. A side-effect is an efficient construction for the "fair split tree" hierarchical clustering method used by Callahan and Kosaraju for various nearest neighbor problems.
(BibTeX -- CiteSeer -- Citations -- ACM DL)
\- \!all \!usesgeom \!graph:all \!graph:dyn \!graph:misc \!a:solo \!c:soda \!j:other \!y:2000 \# sent to Networks 16 Nov 1994 \# recd referee reports May 1998 \# returned revision 23 Jul 1998 \# accepted 11 Oct 1999 \# returned galleys 29 Dec 1999 \!y:1993 \!y:1994
- Clustering for faster network simplex pivots.
D. Eppstein.
Tech. Rep. 93-19, ICS, UCI, 1993.
5th ACM-SIAM Symp. Discrete Algorithms, Arlington, 1994, pp. 160-166.
Networks 35(3):173-180, 2000.Speeds up the worst case time per pivot for various versions of the network simplex algorithm for minimum cost flow problems. Uses techniques from dynamic graph algorithms as well as some simple geometric data structures.
\- \!all \!kbest \!graph:all \!graph:path \!a:solo \!c:focs \!j:sjc \# sent to SICOMP 14 Aug 1995 \# attempted to return revision 31 Mar 1997 but email refused (too big). \# trying again with uuencoded compressed postscript... \# still didn't work, put it on the web page \# accepted 22 Apr 1997 \!p:kpath \!y:1994 \!y:1998
- Finding the k shortest paths.
D. Eppstein.
35th IEEE Symp. Foundations of Comp. Sci., Santa Fe, 1994, pp. 154-165.
Tech. Rep. 94-26, ICS, UCI, 1994.
SIAM J. Computing 28(2):652-673, 1998.Finds multiple short paths connecting two terminals in a graph (allowing repeated vertices and edges in the paths) in constant time per path after a preprocessing stage dominated by a single-source shortest path computation. Applications include dynamic programs for the knapsack problem, biological sequence alignment, and maximum inscribed polygons.
(BibTeX -- Full paper -- Citations -- \# http://www-scf.usc.edu/~graehl/kbest.zip no longer there? 31 Oct 1998 Graehl implementation -- Jiménez-Marzal implementations -- Shibuya implementation -- Martins implementation -- CiteSeer: TR '94, SJC '98 -- ACM DL)
\- \!all \!pure \!geom:all \!geom:tri \!a:bern \!a:chew \!a:ruppert \!c:other \!c:soda \!j:no \!p:dihedral \!y:1994 \!y:1995
- Dihedral bounds for mesh generation in high dimensions.
M. Bern, L.P. Chew, D. Eppstein, and J. Ruppert.
892nd Meeting Amer. Math. Soc., Brooklyn, 1994.
Abstract in Abs. Amer. Math. Soc. 15, 1994, p. 366.
6th ACM-SIAM Symp. Discrete Algorithms, San Francisco, 1995, pp. 189-196.Any d-dimensional point set can be triangulated with O(nceil(d/2)) simplices, none of which has an obtuse dihedral angle. No bound depending only on n is possible if we require the maximum dihedral angle to measure at most 90-epsilon degrees or the minimum dihedral to measure at least epsilon. Includes a classification of simplices in terms of their bad angles.
(BibTeX -- SODA paper -- Citations -- CiteSeer)
\- \!all \!graph:all \!graph:sgi \!graph:planar \!a:solo \!c:soda \!j:jga \# sent to Tamassia for JGAA, 19 Dec 1995 \# accepted 7 Jan 1997 \!p:psgi \!y:1994 \!y:1995 \!y:1999
- Subgraph isomorphism in planar graphs and related problems.
D. Eppstein.
Tech. Rep. 94-25, ICS, UCI, 1994.
6th ACM-SIAM Symp. Discrete Algorithms, San Francisco, 1995, pp. 632-640.
arXiv:cs.DS/9911003.
J. Graph Algorithms and Applications 3(3):1-27, 1999.Uses an idea of Baker to cover a planar graph with subgraphs of low treewidth. As a consequence, any fixed pattern can be found as a subgraph in linear time; the same methods can be used to solve other planar graph problems including vertex connectivity, diameter, girth, induced subgraph isomorphism, and shortest paths. A companion paper presents a result announced in the conference version of this paper, that exactly characterizes the minor-closed graph families for which the same techniques apply.
(BibTeX -- Citations -- Citations from MIT hypertext bibliography -- CiteSeer (SODA) -- CiteSeer (JGAA))
\- \!all \!pure \!param \!usesgeom \!geom:all \!geom:kset \!graph:all \!mst \!a:solo \!c:stoc \!p:geomlb \!j:dcg \# sent to R.Pollack for DCG 8 Nov 1996 \# accepted subject to (extremely minor) revisions 18 Feb 1997 \# returned galleys 29 Jul 1997 \!y:1995 \!y:1998
- Geometric lower bounds for parametric matroid optimization.
D. Eppstein.
Tech. Rep. 95-11, ICS, UCI, 1995.
27th ACM Symp. Theory of Computing, Las Vegas, 1995, pp. 662-671.
Disc. Comp. Geom. 20:463-476, 1998.Considers graphs in which edge weights are linear functions of time. Shows nonlinear lower bounds on the number of different minimum spanning trees appearing over time by translation from geometric problem of lower envelopes of line segments. A matroid generalization has a better lower bound coming from many faces in line arrangements, and the uniform matroid problem is equivalent to the geometric k-set problem.
(BibTeX -- Citations -- CiteSeer -- MIT hypertext bibliography)
\- \!all \!param \!pure \!geom:all \!geom:lp \!geom:zono \!a:bern \!a:guibas \!a:hershberger \!a:suri \!a:wolter \!c:esa \!j:no \!p:centroid \!y:1995
- The centroid of points with approximate weights.
M. Bern, D. Eppstein, L. J. Guibas, J. Hershberger, S. Suri, and J. Wolter.
3rd Eur. Symp. Algorithms, Corfu, 1995.
Lecture Notes in Comp. Sci. 979, 1995, pp. 460-472, © Springer-Verlag.Given a set of points with weights that are not known precisely, but are known to fall within some range, considers the possible weighted centroids arising from different choices of weights in each range. The combinatorics of this problem are closely connected with those of zonotopes.
(BibTeX -- Citations -- CiteSeer -- ACM DL)
\- \!all \!graph:all \!graph:color \!exponential \!a:beigel \!c:focs \!p:3color \!y:1995
- 3-Coloring in time O(1.3446n): a no-MIS algorithm.
R. Beigel and D. Eppstein.
Tech. Rep. 95-033, Electronic Coll. Computational Complexity, 1995.
36th IEEE Symp. Foundations of Comp. Sci., 1995, pp. 444-453.
DIMACS Worksh. Faster Exact Solutions for NP-Hard Problems, 2000.Speeds up 3-coloring by solving a harder problem: constraint satisfaction in which each variable can take on one of three values and each constraint forbids a pair of variable assignments. The detailed solution involves several long hairy case analyses. Similar methods apply also to 3-list-coloring, 3-edge-coloring, and 3-SAT. The 3-SAT algorithm is fixed-parameter tractible in that it is polynomial time when the number of 3-variable clauses is O(log n). Merged into 3-coloring in time O(1.3289^n) for the journal version.
(BibTeX -- Citations -- DIMACS abstract and slides -- CiteSeer)
\- \!all \!survey \!geom:all \!geom:tri \!geom:approx \!tsp \!a:bern \!c:no \!j:book \!y:1996
- 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.
(BibTeX -- Citations -- ACM DL)
\- \!all \!pure \!geom:all \!geom:nn \!a:solo \!c:no \!y:1992
- The diameter of nearest neighbor graphs.
D. Eppstein.
Tech. Rep. 92-76, ICS, UCI, 1992.Any connected nearest neighbor forest with diameter D has O(D6) vertices. This was later further improved to O(D5) and merged with results of Paterson and Yao into "On nearest neighbor graphs".
(BibTeX -- Citations -- CiteSeer)
\- \!all \!graph:all \!graph:misc \!misc \!a:solo \!c:no \!j:algs \!y:1995 \!y:1997 \# sent to Zvi for J. Alg. 17 Aug 1995 \# accepted subject to revision 3 Jan 1996 \# returned revision 6 Aug 1996 \# returned galleys 17 Feb 1997
- Minimum range balanced cuts via dynamic subset sums.
D. Eppstein.
Tech. Rep. 95-10, ICS, UCI, 1995.
J. Algorithms 23:375-385, 1997.Describes data structures for maintaining the solution of a dynamically changing subset sum problem, and uses them to find a cut in a graph minimizing the difference between the heaviest and lightest cut edge.
\- \!all \!misc \!param \!usesgeom \!geom:all \!geom:kset \!geom:lp \!stat \!a:hirschberg \!c:wcg \!j:algs \!p:maxwtavg \!y:1995 \!y:1997 \# sent to Zvi for J. Alg. 22 Mar 1995, sent revision 4 Mar 1996 \# accepted 7 Oct 1996; queue is 10 months long
- Choosing subsets with maximum weighted average.
D. Eppstein and D. S. Hirschberg.
Tech. Rep. 95-12, ICS, UCI, 1995.
5th MSI Worksh. on Computational Geometry, 1995, pp. 7-8.
J. Algorithms 24:177-193, 1997.Uses geometric optimization techniques to find, among n weighted values, the k to drop so as to maximize the weighted average of the remaining values. The feasibility test for the corresponding decision problem involves k-sets in a dual line arrangement.
(BibTeX -- Full paper -- CiteSeer -- ACM DL)
\- \!all \!geom:all \!mst \!geom:approx \!geom:cluster \!geom:qt \!a:solo \!c:no \!j:cgta \!p:k-point \!y:1995 \!y:1997
- Faster geometric k-point MST approximation.
D. Eppstein.
Tech. Rep. 95-13, ICS, UCI, 1995.
Comp. Geom. Theory & Applications 8:231-240, 1997.Various authors have looked at a variant of geometric clustering in which one must select k points that can be connected by a small spanning tree. The problem is NP-complete (for variable k); good approximations are known based on dynamic programming techniques but the time dependence on n is high. This paper describes a faster approximation algorithm based on dynamic programming in quadtrees, and a general technique based on that in "Iterated nearest neighbors" for reducing the dependence on n in any approximation algorithm.
(BibTeX -- Citations -- CiteSeer -- ACM DL)
\- \!all \!pure \!graph:all \!mst \!graph:path \!graph:match \!kbest \!a:solo \!c:no \!j:no \!y:1995
- Representing all Minimum Spanning Trees with Applications to
Counting and Generation.
D. Eppstein.
Tech. Rep. 95-50, ICS, UCI, 1995.Shows how to find for any edge weighted graph G an equivalent graph EG such that the minimum spanning trees of G correspond one-for-one with the spanning trees of EG. \!pure The equivalent graph can be constructed in time O(m+n log n) given a single minimum spanning tree of G. As a consequence one can find fast algorithms for counting, listing, and randomly generating MSTs. \!pure Also discusses similar equivalent graph constructions for shortest paths, minimum cost flows, and bipartite matching.
\- \!all \!pure \!geom:all \!geom:tri \!a:solo \!c:scg \!j:cgta \!p:hexmesh \!y:1995 \!y:1996 \!y:1999 \# emailed to Goodrich for CGTA special on SCG 96 appl. papers, 27 Sep 1996 \# accepted subject to revn 30 Jan 1998; returned revn 28 Aug 1998 \# returned galleys 1 Dec 1998
- Linear complexity hexahedral mesh generation.
D. Eppstein.
Tech. Rep. 95-51, ICS, UCI, 1995.
12th ACM Symp. Comp. Geom., Philadelphia, 1996, pp. 58-67.
arXiv:cs.CG/9809109.
Comp. Geom. Theory & Applications 12:3-16, 1999 (special issue for 12th SCG).Any simply connected polyhedron with an even number of quadrilateral sides can be partitioned into O(n) topological cubes, meeting face to face.
(BibTeX -- Citations -- SCG paper -- SCG talk slides -- CiteSeer -- ACM DL (CGTA))
\- \!all \!kbest \!graph:all \!graph:path \!a:solo \!c:no \!p:ancestors \!y:1995
- Finding Common Ancestors and Disjoint Paths in DAGs.
D. Eppstein.
Tech. Rep. 95-52, ICS, UCI, 1995.This paper describes algorithms for finding pairs of vertex-disjoint paths in a DAG, either connecting two given nodes to a common ancestor, or connecting two given pairs of terminals. The main results were merged into the journal version of "Finding the k shortest paths".
(BibTeX)
\- \!all \!rec \!geom:all \!geom:zono \!a:solo \!c:no \!j:other \!p:zono \!y:1995 \!y:1996
- Zonohedra and Zonotopes.
D. Eppstein.
Tech. Rep. 95-53, ICS, UCI, 1995.
Mathematica in Education and Research 5(4):15-21, 1996.I use Mathematica to construct zonotopes and display zonohedra. Many examples are shown, including one used for a lower bound in "The centroid of points with approximate weights". This paper is also available in HTML and Mathematica notebook formats.
(BibTeX -- Citations -- CiteSeer)
\- \!all \!geom:all \!geom:nn \!pure \!a:paterson \!a:yao \!j:dcg \!p:nn \!y:1997
- On nearest-neighbor graphs.
D. Eppstein, M. S. Paterson, and F. F. Yao.
Disc. Comp. Geom. 17:263-282, 1997.Paterson and Yao presented a paper at ICALP showing among other things that any connected nearest neighbor forest with diameter D has O(D9) vertices. This paper is the journal version; my contribution consists of improving that bound to O(D5), which is tight.
(BibTeX -- CiteSeer -- Citations)
\- \!all \!geom:all \!geom:tri \!a:barequet \!a:dickerson \!c:scg \!j:cgta \!p:3poly \!y:1996 \!y:1998 \# Gill submitted it to CGTA ca summer 1996 \# favorable referee reports received by Gil 30 Jul 1997 \# revision accepted 23 Oct 1997 \# Gill returned proofs 31 Mar 1998 \# scheduled for CGTA v10 n3 Jun 1998
- On triangulating three-dimensional polygons.
G. Barequet, M. Dickerson, and D. Eppstein.
12th ACM Symp. Comp. Geom., Philadelphia, 1996, pp. 38-47.
Comp. Geom. Theory & Applications 10:155-170, 1998.It is NP-complete, given a simple polygon in 3-space, to find a triangulated simply-connected surface (without extra vertices) spanning that polygon. If extra vertices are allowed, or the surface may be curved, such a surface exists if and only if the polygon is unknotted; the complexity of testing knottedness remains open. Snoeyink has shown that exponentially many extra vertices may be required for a triangulated spanning disk.
(BibTeX -- SCG paper -- Full paper -- Citations -- CiteSeer -- ACM DL)
\- \!all \!param \!usesgeom \!graph:all \!mst \!a:fernandez-baca \!a:slutzki \!c:swat \!j:bit \!p:parammst \!y:1996
- Using sparsification for parametric minimum spanning tree problems.
D. Fernández-Baca, G. Slutzki, and D. Eppstein.
5th Scand. Worksh. Algorithm Theory, Reykjavik, 1996.
Lecture Notes in Comp. Sci. 1097, 1996, pp. 149-160, © Springer-Verlag.
Nordic J. Computing 3(4):352-366, 1996 (special issue for 5th SWAT).Given a graph with edge weights that are linear functions of a parameter, finds the sequence of minimum spanning trees produced as the parameter varies, in total time O(mn log n), by combining ideas from "Sparsification" and "Geometric lower bounds". Also solves various problems of optimizing the parameter value, including one closely related to that in "Choosing subsets with maximum weighted average".
(BibTeX -- Citations -- MIT hypertext bibliography -- ACM DL (SWAT) -- ACM DL (NJC))
\- \!all \!geom:all \!geom:cluster \!geom:circle \!a:solo \!c:soda \!j:no \!p:2c \!y:1996 \!y:1997
- Faster construction of planar two-centers.
D. Eppstein.
Tech. Rep. 96-12, ICS, UCI, 1996.
8th ACM-SIAM Symp. Discrete Algorithms, New Orleans, 1997, pp. 131-138.Improving on a recent breakthrough of Sharir, we use data structures from "Dynamic three-dimensional linear programming" to find two circular disks of minimum radius covering a set of points in the Euclidean plane, in randomized expected time O(n log2 n).
(BibTeX -- SODA paper -- Citations -- DREI and SODA talk slides -- CiteSeer)
\- \!all \!graph:all \!graph:dyn \!a:solo \!c:no \!j:ipl \!y:1996 \!y:1997
- Dynamic connectivity in digital images.
D. Eppstein.
Tech. Rep. 96-13, ICS, UCI, 1996.
Inf. Proc. Lett. 62:121-126, 1997.Any algorithm that maintains the connected components of a bitmap image must take Omega(log n / log log n) time per change to the image. The problem can be solved in O(log n) time per change using dynamic planar graph techniques. We discuss applications to computer Go and other games.
(BibTeX -- Citations -- MIT hypertext bibliography -- CiteSeer -- ACM DL)
\- \!all \!graph:all \!mst \!a:solo \!c:no \!j:no \!y:1996
- On the parity of graph spanning tree numbers.
D. Eppstein.
Tech. Rep. 96-14, ICS, UCI, 1996.Any bipartite Eulerian graph, any Eulerian graph with evenly many vertices, and any bipartite graph with evenly many vertices and edges, has an even number of spanning trees. More generally, a graph has evenly many spanning trees if and only if it has an Eulerian edge cut.
(BibTeX -- Citations -- CiteSeer)
\- \!all \!geom:all \!geom:path \!graph:path \!a:solo \!c:no \!j:cgta \!p:beta \!y:1996 \!y:2002 \# web sub to CGTA 4 Dec 2000 \# acc. subj. to minor revisions 15 Mar 2001
- Beta-skeletons have unbounded dilation.
D. Eppstein.
Tech. Rep. 96-15, ICS, UCI, 1996.
arXiv:cs.CG/9907031.
Comp. Geom. Theory & Applications 23:43-52, 2002.Beta-skeletons are geometric graphs used among other purposes for empirical network analysis and minimum weight triangulation. A fractal construction shows that, for any beta>0, the beta-skeleton of a point set can have arbitrarily large dilation: Omega(nc), where c is a constant depending on beta and going to zero in the limit as beta goes to zero. In particular this applies to the Gabriel graph. We also show upper bounds on dilation of the same form.
(BibTeX -- Citations -- ACM DL)
\- \!all \!survey \!geom:all \!geom:path \!graph:path \!a:solo \!c:no \!j:book \!p:sst \!y:1996 \!y:1999
- 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.
(BibTeX -- Citations -- CiteSeer)
\- \!all \!geom:all \!geom:misc \!a:cgitf \!a:amenta \!a:barequet \!a:bern \!a:clarkson \!a:dobkin \!a:edelsbrunner \!a:guibas \!a:overmars \!a:snoeyink \!c:no \!j:no \!y:1996
- Application Challenges to Computational Geometry.
The \!a:cgitf \!a:cgitf Computational Geometry Impact Task Force \!a:cgitf \!a:cgitf Report.
Tech. Rep. TR-521-96, Princeton University, April 1996.
Advances in Discrete and Computational Geometry -- Proc. 1996 AMS-IMS-SIAM Joint Summer Research Conf. Discrete and Computational Geometry: Ten Years Later, Contemporary Mathematics 223, Amer. Math. Soc., 1999, pp. 407-423.\- \!all \!geom:all \!geom:tri \!geom:lp \!pure \!a:amenta \!a:bern \!c:soda \!j:algs \!p:meshsmooth \!y:1997 \!y:1999
- Optimal point placement for mesh smoothing.
N. Amenta, M. Bern, and D. Eppstein.
8th ACM-SIAM Symp. Discrete Algorithms, New Orleans, 1997, pp. 528-537.
Symp. Computational Geometry Approaches to Mesh Generation, SIAM 45th Anniversary Mtg., Stanford, 1997.
arXiv:cs.CG/9809081.
J. Algorithms 30:302-322, 1999 (special issue for SODA 1997).We study finite element mesh smoothing problems in which we move vertex locations to optimize the shapes of nearby triangles. Many such problems can be solved in linear time using generalized linear programming; we also give efficient algorithms for some non-LP-type mesh smoothing problems. One lemma may be of independent interest: the locus of points in Rd from which a d-1 dimensional convex set subtends a given solid angle is convex.
(BibTeX -- SODA paper -- Citations -- CiteSeer -- ACM DL)
\- \!all \!graph:all \!graph:sgi \!graph:planar \!graph:path \!pure \!a:solo \!j:algo \!p:dtwmcgf \!y:1999 \!y:2000 \# sent to Bodlaender for special issue of Algorithmica, 28 Jan 1997 \# accepted subject to revision 16 Oct 1997, fully accepted 28 Jan 1998 \# returned galleys 6 Jan 2000
- Diameter and treewidth in minor-closed graph families.
D. Eppstein.
arXiv:math.CO/9907126.
Algorithmica 27:275-291, 2000 (special issue on treewidth, graph minors, and algorithms).It was known that planar graphs have the diameter-treewidth property: there is a function f(D) such that any planar graph with diameter D has treewidth at most f(D). (Actually, f(D)=O(D).) We characterize the other minor-closed families with this property: F has the diameter-treewidth property if and only if there is a graph G, formed by adding a vertex to a planar graph, that is not in F. Families with the diameter-treewidth property include bounded-genus graphs (for which again f(D)=O(D)) and K3,a-free graphs. As a consequence, various efficient planar subgraph isomorphism and approximation algorithms can be extended to these families. Some of these results were announced in the conference version of "subgraph isomorphism for planar graphs and related problems" but not included in the journal version.
\- \!all \!survey \!graph:all \!graph:dyn \!survey \!a:galil \!a:italiano \!c:no \!j:book \!y:1996 \!y:1999
- 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.(BibTeX -- Citations -- CiteSeer)
\- \!all \!geom:all \!geom:path \!graph:path \!a:hart \!c:wads \!j:no \!y:1997
- An efficient algorithm for shortest paths in vertical and horizontal
segments.
D. Eppstein and D. Hart.
5th Worksh. Algorithms and Data Structures, Halifax, Nova Scotia, 1997.
Lecture Notes in Comp. Sci. 1272, 1997, pp. 234-247, © Springer-Verlag.We show how to find shortest paths along the segments of an arrangement of n vertical and horizontal line segments in the plane, in time O(n3/2).
(BibTeX -- Citations -- CiteSeer -- ACM DL)
\- \!all \!misc \!j:jcss \!y:1997 \# bwah hah hah, appeared in same issue as special for 32nd FOCS
- Guest editor's forward to special issue of papers from the 34th Annual Symposium on Foundations of Computer Science.
D. Eppstein.
J. Comp. Sys. Sci. 54:263, 1997.(BibTeX)
\- \!all \!geom:all \!geom:path \!a:amenta \!a:bern \!c:no \!j:other \!p:crust \!y:1998
- The crust and the beta-skeleton: combinatorial curve
reconstruction.
N. Amenta, M. Bern, and D. Eppstein.
Xerox PARC research report.
Graphical Models & Image Processing 60/2(2):125-135, 1998.We consider the problem of "connect the dots": if we have an unknown smooth curve from which sample points have been selected, we would like to find a curve through the sample points that approximates the unknown curve. We show that if the local sample density is sufficiently high, a simple algorithm suffices: form the Delaunay triangulation of the sample points together with their Voronoi vertices, and keep only those Delaunay edges connecting original sample points.
(Tech. report version -- BibTeX -- Citations -- CiteSeer -- ACM DL)
\- \!p:crust \!a:amenta
\- \!all \!param \!usesgeom \!a:solo \!c:other \!y:1997
- Computational geometry and parametric matroid optimization.
D. Eppstein.
Invited talk, 5th Int. Symp. Parametric Optimization, Chiba, Japan, 1997.This talk surveys some connections from computational geometry to parametric matroids: the results of my paper "Geometric lower bounds", new upper bounds from a paper by Tamal Dey, and a problem from constructive solid geometry with the potential to lead to stronger lower bounds.
\- \!all \!geom:all \!geom:tri \!geom:circle \!a:bern \!c:imr \!c:wcg \!j:ijcga \!p:qpack \!y:1997 \!y:1999 \!y:2000 \# sub to SHT for IJCGA special issue on IMR 17 Jun 1998 \# accepted 3 Nov 1998
- Quadrilateral meshing by circle packing.
M. Bern and D. Eppstein.
2nd CGC Worksh. Computational Geometry, Durham, North Carolina, 1997.
6th Int. Meshing Roundtable, Park City, Utah, 1997, pp. 7-19.
arXiv:cs.CG/9908016.
Int. J. Comp. Geom. & Appl. 10(4):347-360, 2000.We use circle-packing methods to generate quadrilateral meshes for polygonal domains, with guaranteed bounds both on the quality and the number of elements. We show that these methods can generate meshes of several types:
- The elements form the cells of a Voronoi diagram,
- The elements each have two opposite 90 degree angles,
- All elements are kites, or
- All angles are at most 120 degrees.
(BibTeX -- Citations -- CiteSeer)
\- \!p:qpack \!a:bern
\- \!all \!geom:all \!geom:dyn \!graph:all \!graph:match \!tsp \!stat \!a:solo \!c:soda \!j:other \!y:1998 \!y:2000 \# sub to Skiena for JEA 21 Dec 1999
- Fast hierarchical
clustering and other applications of dynamic closest pairs.
D. Eppstein.
9th ACM-SIAM Symp. Discrete Algorithms, San Francisco, 1998, pp. 619-628.
arXiv:cs.DS/9912014.
J. Experimental Algorithmics 5(1):1-23, 2000.This paper shows how to use my dynamic closest pair data structure from "Dynamic Euclidean minimum spanning trees" for some non-geometric problems including hierarchical clustering, greedy matching, and TSP heuristics. Experiments show variants of my data structures to be faster than previously used heuristics.
(Source code and experimental data -- BibTeX -- SODA paper -- Citations -- CiteSeer -- ACM DL -- JEA home page)
\- \!all \!geom:all \!geom:dyn \!geom:ss \!a:erickson \!c:scg \!j:dcg \!y:1998 \!y:1999 \# sent by JE to Ken Clarkson for some special issue, 1 Jul 1998 \# Jeff returned galleys 23 Jul 1999
- Raising roofs, crashing cycles, and playing pool: applications of
a data structure for finding pairwise interactions.
D. Eppstein and J. Erickson.
14th ACM Symp. Comp. Geom., Minneapolis, 1998, pp. 58-67.
Disc. Comp. Geom. 22(4):569-592, 1999 (special issue for SCG 1998).We use my dynamic closest pair data structure from "Dynamic Euclidean minimum spanning trees" to detect collisions among a collection of moving objects in sublinear time per collision. As one application, we can construct the straight skeleton of Aichholzer et al (and the mitered offset curves from which it is defined) in subquadratic time.
(Jeff's publications page and copy of the journal version -- BibTeX -- Citations -- CiteSeer)
\- \!all \!pure \!geom:all \!graph:all \!gdraw \!a:dillencourt \!a:hirschberg \!c:gd \!j:jga \!p:thickness \!y:1998 \!y:1999 \!y:2000 \# sub to SCG 20 Nov 1997 \# rejected 2 Feb 1998 \# sub to Graph Drawing 4 May 1998 \# sub by Dillencourt to Liotta for JGAA special issue 30 Nov 1998
- Geometric thickness of complete graphs.
M. Dillencourt, D. Eppstein, and D. S. Hirschberg.
6th Int. Symp. Graph Drawing, Montreal, August 1998.
Lecture Notes in Comp. Sci. 1547, 1998, pp. 102-110, © Springer-Verlag.
arXiv:math.CO/9910185.
J. Graph Algorithms and Applications 4(3):5-17, 2000 (special issue for GD98).We define a notion of geometric thickness, intermediate between the previously studied concepts of graph thickness and book thickness: a graph has geometric thickness T if its vertices can be embedded in the plane, and its edges partitioned into T subsets, so that each subset forms a planar straight line graph. We then give upper and lower bounds on the geometric thickness of complete graphs.
(Springer abstract -- BibTeX -- CiteSeer -- Citations -- ACM DL -- GDEA)
\- \!all \!geom:all \!geom:path \!graph:path \!a:hart \!c:soda \!j:no \!y:1999 \# sub to SCG 21 Nov 1997 \# rejected 2 Feb 1998 \# accepted to SODA 4 Sep 1998
- Shortest paths in an arrangement with k line orientations.
D. Eppstein and D. Hart.
10th ACM-SIAM Symp. Discrete Algorithms, Baltimore, 1999, pp. 310-316.We show how to find shortest paths between two points on the lines of an arrangement of n lines with k distinct orientations, in time O(n + k2).
(BibTeX -- SODA paper -- Citations -- CiteSeer)
\- \!all \!geom:all \!geom:circle \!rec \!a:bern \!a:demaine \!a:hayes \!c:other \!j:no \!y:1998 \!y:1999 \!y:2001
- A disk-packing algorithm for an origami magic trick.
M. Bern, E. Demaine, D. Eppstein, and B. Hayes.
Int. Conf. Fun with Algorithms, Elba, June 1998.
Proceedings in Informatics 4, Carleton Scientific, Waterloo, Canada, 1999, pp. 32-42.
Origami3: Proc. 3rd Int. Mtg. Origami Science, Math, and Education (Asilomar, California, 2001), A K Peters, 2002, pp. 17-28.We apply techniques from "Quadrilateral meshing by circle packing" to a magic trick of Houdini: fold a piece of paper so that with one straight cut, you can form your favorite polygon.
(preprint at Erik's web site -- BibTeX -- CiteSeer)
\- \!all \!param \!graph:all \!mst \!usesgeom \!a:agarwal \!a:guibas \!a:henzinger \!c:focs \!j:no \!y:1998
- Parametric and kinetic minimum spanning trees.
P. K. Agarwal, D. Eppstein, L. J. Guibas, and M. R. Henzinger.
39th IEEE Symp. Foundations of Comp. Sci., 1998, pp. 596-605..We describe algorithms for maintaining the minimum spanning tree in a graph in which the edge weights are piecewise linear functions of time that may change unpredictably. We solve the problem in time O(n2/3 polylog n) per combinatorial change to the tree for general graphs, and in time O(n1/4 polylog n) per combinatorial change to the tree for planar graphs.
(BibTeX -- FOCS '98 talk slides -- Citations -- CiteSeer -- ACM DL)
\- \!all \!pure \!geom:all \!geom:qt \!graph:all \!graph:color \!a:bern \!a:hutchings \!c:no \!j:algo \!y:1999 \!y:2002 \# sent Boissonat for Algorithmica 26 May 1998, revised 8 Apr 1999 and \# again 2 Sep 1999, accepted 9 Dec 1999, returned galleys 13 Jul 2001
- Algorithms for coloring quadtrees.
M. Bern, D. Eppstein, and B. Hutchings.
arXiv:cs.CG/9907030.
Algorithmica 32(1):87-94, 2002.We consider several variations of the problem of coloring the squares of a quadtree so that no two adjacent squares are colored alike. We give simple linear time algorithms for 3-coloring balanced quadtrees with edge adjacency, 4-coloring unbalanced quadtrees with edge adjacency, and 6-coloring balanced or unbalanced quadtrees with corner adjacency. The number of colors used by the first two algorithms is optimal; for the third algorithm, 5 colors may sometimes be needed.
\- \!all \!geom:all \!geom:dyn \!a:solo \!c:soda \!j:algs \!y:1998 \!y:1999 \!y:2000 \# sub to SODA 6 Jul 1998 \# accepted as short form paper 2 Sep 1998 \# sub to Zvi for J. Algorithms, 1 Oct 1999 \# acc by Shimon Even 20 Dec 1999
- Incremental and decremental maintenance of planar width.
D. Eppstein.
arXiv:cs.CG/9809038.
10th ACM-SIAM Symp. Discrete Algorithms, Baltimore, 1999, pp. S899-S900.
J. Algorithms 37(2):570-577, 2000.We show how to maintain the width of a planar point set, subject to insertions or deletions (but not both) in time O(nc) per update for any c > 0. The idea is to apply our dynamic closest pair data structure to an appropriate measure of distance between pairs of convex hull features.
(BibTeX -- Citations -- SODA talk slides -- ACM DL)
\- \!all \!geom:all \!geom:deep \!pure \!stat \!a:amenta \!a:bern \!a:teng \!c:wcg \!j:dcg \!p:regdepth \!y:1998 \!y:2000 \# sub xxx version to Ricky P. for DCG, 6 Oct 1998 \# revision ca Jul 1999 \# returned galleys 27 Oct 1999
- Regression depth and center points.
N. Amenta, M. Bern, D. Eppstein, and S.-H. Teng.
arXiv:cs.CG/9809037.
3rd CGC Worksh. Computational Geometry, Brown Univ., 1998.
Disc. Comp. Geom. 23(3):305-323, 2000.We show that, for any set of n points in d dimensions, there exists a hyperplane with regression depth at least ceiling(n/(d+1)). as had been conjectured by Rousseeuw and Hubert. Dually, for any arrangement of n hyperplanes in d dimensions there exists a point that cannot escape to infinity without crossing at least ceiling(n/(d+1)) hyperplanes. We also apply our approach to related questions on the existence of partitions of the data into subsets such that a common plane has nonzero regression depth in each subset, and to the computational complexity of regression depth problems.
(BibTeX -- Citations -- CiteSeer)
\- \!all \!graph:all \!graph:dyn \!j:algo \!y:1998
- Guest editor's forward to special issue on dynamic graph algorithms.
D. Eppstein.
Algorithmica 22(3):233-234, 1998.\- \!all \!param \!graph:all \!mst \!graph:path \!geom:all \!geom:lp \!usesgeom \!a:solo \!c:focs \!j:sjc \!y:1999 \!y:2003 \# esub to SICOMP 31 Mar 2000, revised 1 Aug 2002, accepted 16 Oct 2002
- Setting parameters by example.
D. Eppstein.
arXiv:cs.DS/9907001.
40th IEEE Symp. Foundations of Comp. Sci., 1999, pp. 309-318.
SIAM J. Computing 32(3):643-653, 2003.We introduce a class of "inverse parametric optimization" problems, in which one is given both a parametric optimization problem and a desired optimal solution; the task is to determine parameter values that lead to the given solution. We use low-dimensional linear programming and geometric sampling techniques to solve such problems for minimum spanning trees, shortest paths, and other optimal subgraph problems, and discuss applications in multicast routing, vehicle path planning, resource allocation, and board game programming.
(BibTeX -- Citations -- ACM DL (FOCS) -- ACM DL (SJC))
\- \!all \!a:ge \!a:smyth \!graph:all \!graph:random \!c:other \!j:other \!y:1999 \!y:2000 \!y:2001 \# sent by smyth to IEEE Trans. Inf. Th. 25 Mar 1999 \# accepted as a correspondence 17 Jul 2000 \# revised version forwarded to publisher 31 Jan 2001 \# sent by smyth to IEEE Information Theory Symp, Sept 1999 \# saw acceptance on conf web site 9 Feb 2000 \# (see http://www.dia.unisa.it/isit2000/ for conf info) \!y:1999
- The distribution of cycle lengths in graphical models for iterative decoding.
X. Ge, D. Eppstein, and P. Smyth.
arXiv:cs.DM/9907002.
Tech. Rep. 99-10, ICS, UCI, 1999.
IEEE Int. Symp. Information Theory, Sorrento, Italy, 2000.
IEEE Trans. Information Theory 47(6):2549-2553, 2001.We compute the expected numbers of short cycles of each length in certain classes of random graphs used for turbocodes, estimate the probability that there are no such short cycles involving a given vertex, and experimentally verify our estimates. The scarcity of short cycles may help explain the empirically observed accuracy of belief-propagation based error-correction algorithms. Note, the TR, conference, and journal versions of this paper have slightly different titles.
(BibTeX -- Citations: TR/ISIT -- CiteSeer)
\- \!all \!pure \!rec \!geom:all \!geom:misc \!a:bern \!a:demaine \!a:kuo \!a:mantler \!a:snoeyink \!c:cccg \!c:wcg \!p:ununfold \!j:cgta \!y:1999 \!y:2003 \# submitted by ED to special issue of CGTA for WCG, Nov 1999 \# accept subject to revn 20 Nov 2000
- Ununfoldable polyhedra.
M. Bern, E. Demaine, D. Eppstein, E. Kuo, A. Mantler, and J. Snoeyink.
arXiv:cs.CG/9908003.
Tech. rep. CS-99-04, Univ. of Waterloo, Dept. of Computer Science, Aug. 1999.
11th Canad. Conf. Comp. Geom., 1999.
4th CGC Worksh. Computational Geometry, Johns Hopkins Univ., 1999.
Comp. Geom. Theory & Applications (special issue for 4th CGC Worksh.) 24(2):51-62, 2003.We prove the existence of polyhedra in which all faces are convex, but which can not be cut along edges and folded flat.
Note variations in different versions: the CCCG one was only Bern, Demain, Eppstein, and Kuo, and the WCG one had the title "Ununfoldable polyhedra with triangular faces". The journal version uses the title "Ununfoldable polyhedra with convex faces" and the combined results from both conference versions.
(BibTeX -- Erik's publication page -- CiteSeer -- ACM DL)
\- \!all \!pure \!rec \!geom:all \!geom:misc \!a:demaine \!a:mdemaine \!a:frederickson \!a:friedman \!c:cccg \!j:cgta \!p:hinged \!y:1999 \!y:2005 \# sent by Erik to Jack Snoeyink, CGTA special for CCCG99, 30 Sep 1999
- Hinged dissections of polyominos and polyforms.
E. Demaine, M. Demaine, D. Eppstein, G. Frederickson, and E. Friedman.
arXiv:cs.CG/9907018.
11th Canad. Conf. Comp. Geom., 1999.
Computational Geometry: Theory and Applications 31(3):237-262, 2005 (special issue for 11th CCCG).We show that, for any n, there exists a mechanism formed by connecting polygons with hinges that can be folded into all possible n-ominos. Similar results hold as well for n-iamonds, n-hexes, and n-abolos.
(BibTeX -- Erik's CCCG publication page -- Erik's CGTA publication page -- Citations)
\- \!all \!geom:all \!geom:misc \!a:bern \!a:agarwal \!a:amenta \!a:chew \!a:dobkin \!a:edelsbrunner \!a:guibas \!a:plassman \!a:snoeyink \!c:other \!j:no \!y:1999
- Emerging challenges in computational topology.
M. Bern, D. Eppstein, et al.
arXiv:cs.CG/9909001.
This is the report from the ACM Workshop on Computational Topology run by Marshall and myself in Miami Beach, June 1999. It details goals, current research, and recommendations in this emerging area of collaboration between computer science and mathematics.
(BibTeX -- Citations -- CiteSeer)
\- \!all \!pure \!rec \!geom:all \!geom:circle \!a:solo \!c:no \!j:other \!p:tstc \!y:1999 \!y:2001 \# sent to Horn for Amer. Math. Monthly 24 Sep 1999 \# accepted 14 Dec 1999
- Tangent spheres and triangle centers.
D. Eppstein.
arXiv:math.MG/9909152.
Amer. Math. Monthly 108(1):63-66, 2001.Any four mutually tangent spheres determine three coincident lines through opposite pairs of tangencies. As a consequence, we define two new triangle centers. These centers arose as part of a compass-and-straightedge construction of Soddy circles; also available are some Mathematica calculations of trilinear coordinates for the new triangle centers.
(BibTeX -- Citations -- CiteSeer)
\- \!all \!geom:all \!geom:deep \!pure \!stat \!a:bern \!c:scg \!j:dcg \!p:multivariate \!y:1999 \!y:2000 \!y:2002
- Multivariate regression depth.
M. Bern and D. Eppstein.
arXiv:cs.CG/9912013.
16th ACM Symp. Comp. Geom., Hong Kong, 2000, pp. 315-321.
Disc. Comp. Geom. 28(1):1-17, 2002.We generalize regression depth to k-flats. The k=0 case gives the classical notion of center points. We prove that for any set of n points in Rd there always exists a k-flat with depth at least a constant fraction of n. As a consequence, we derive a linear-time (1+epsilon)-approximation algorithm for the deepest flat. The full version of this paper also includes results from "Computing the Depth of a Flat".
(BibTeX -- SCG paper -- Citations -- CiteSeer)
\- \!all \!rec \!a:solo \!c:other \!graph:path \!j:book \!y:2000 \!y:2002 \# sub by email to MSRI conf comb games, 27 Apr 2000 \# acc. to proceedings and returned final revision 15 Mar 2001
- 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.
(BibTeX -- MSRI talk on streaming video and talk slides -- Citations -- CiteSeer)
\- \!all \!geom:all \!geom:dyn \!graph:all \!graph:dyn \!a:solo \!c:other \!y:2000
- Graphs for dynamic geometry.
D. Eppstein.
Invited talk, Worksh. Dynamic Graph Algorithms, Victoria, Canada, 2000.This talk surveys work on computational geometry algorithms that use dynamic graph data structures, and the different kinds of geometric graph arising in this work.
\- \!all \!graph:all \!graph:color \!exponential \!a:beigel \!j:algs \!p:3color2 \!y:2000 \!y:2005 \# esub to J. Algorithms 13 Oct 2000 \# revised 18 Apr 2003
- 3-coloring in time O(1.3289^n).
R. Beigel and D. Eppstein.
arXiv:cs.DS/0006046.
J. Algorithms 54:2 (2005) 168-204.Journal paper combining 3-coloring algorithms from our FOCS '95 paper with improved bounds from our SODA '01 paper.
\- \!all \!rec \!a:moore \!c:other \!j:book \!graph:path \!y:2000 \!y:2002
- 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.
(BibTeX -- Citations -- Cris' MSRI talk on streaming video -- Cris' publications page -- CiteSeer)
\- \!all \!rec \!graph:path \!a:demaine \!a:mdemaine \!c:no \!j:book \!y:2000 \!y:2002
- 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.
(BibTeX -- Citations -- Erik's publications page -- CiteSeer)
\- \!all \!graph:all \!graph:random \!graph:path \!a:wang \!c:soda \!j:jga \!y:2000 \!y:2001 \!y:2004 \# esub by JW to DT for JA 16 Feb 2001
- Fast approximation of centrality.
D. Eppstein and J. Wang.
arXiv:cs.DS/0009005.
12th ACM-SIAM Symp. Discrete Algorithms, Washington, 2001, pp. 228-229.
J. Graph Algorithms & Applications 8(1):27-38, 2004.We use random sampling to quickly estimate, for each vertex in a graph, the average distance to all other vertices.
(BibTeX -- SODA paper -- Citations -- CiteSeer)
\- \!all \!graph:all \!graph:color \!exponential \!a:solo \!c:soda \!p:3color3 \!y:2000 \!y:2001
- Improved algorithms for 3-coloring, 3-edge-coloring, and constraint
satisfaction.
D. Eppstein.
arXiv:cs.DS/0009006.
12th ACM-SIAM Symp. Discrete Algorithms, Washington, 2001, pp. 329-337.Summarizes recent improvements to "3-Coloring in time O(1.3446n): a no-MIS algorithm". Merged with that paper for the journal version.
(SODA talk slides -- BibTeX -- SODA paper -- CiteSeer)
\- \!all \!geom:all \!geom:deep \!stat \!a:bern \!c:soda \!p:compflat \!y:2000 \!y:2001
- Computing the depth of a flat.
M. Bern and D. Eppstein.
arXiv:cs.CG/0009024.
12th ACM-SIAM Symp. Discrete Algorithms, Washington, 2001, pp. 700-701.We compute the regression depth of a k-flat in a set of n d-dimensional points, in time O(nd-2), an order of magnitude faster than the best known algorithms for computing the depth of a point or of a hyperplane. The results from this conference paper have been merged into the full version of "Multivariate Regression Depth".
(SODA talk slides -- SODA paper -- BibTeX -- Citations -- CiteSeer)
\- \!all \!geom:all \!usesgeom \!a:muthu \!c:soda \!j:no \!y:2000 \!y:2001
- Internet packet filter management and rectangle geometry.
D. Eppstein and S. Muthukrishnan.
arXiv:cs.CG/0010018.
12th ACM-SIAM Symp. Discrete Algorithms, Washington, 2001, pp. 827-835.Rule sets for internet routers and firewalls can be represented as sets of prioritized rectangles; the rule to use for a packet is the maximum priority rectangle containing its (source,destination) address pair. We develop efficient data structures for performing these queries, and find an O(n3/2) time algorithm for testing whether a rule set contains any ambiguities.
(BibTeX -- Citations -- SODA paper -- CiteSeer)
\- \!all \!graph:all \!graph:color \!exponential \!pure \!a:solo \!c:wads \!j:jga \!y:2000 \!y:2001 \!y:2003 \# sub to JGAA special issue 29 Aug 2001 \# accept w/minor changes, returned revision 3 Apr 2002
- Small maximal independent sets and faster exact graph coloring.
D. Eppstein.
arXiv:cs.DS/0011009.
7th Worksh. Algorithms and Data Structures, Providence, Rhode Island, 2001.
Lecture Notes in Comp. Sci. 2125, 2001, pp. 462-470, © Springer-Verlag.
J. Graph Algorithms and Applications (special issue for WADS'01) 7(2):131-140, 2003.We show that any graph can be colored in time O(2.415n), by a dynamic programming procedure in which we extend partial colorings on subsets of the vertices by adding one more color for a maximal independent set. The time bound follows from limiting our attention to maximal independent subsets that are small relative to the previously colored subset, and from bounding the number of small maximal independent subsets that can occur in any graph.
(BibTeX -- Citations -- CiteSeer -- WADS talk slides -- ACM DL)
\- \!all \!geom:all \!geom:tri \!geom:lp \!geom:circle \!geom:hyperbolic \!graph:all \!gdraw \!a:bern \!c:wads \!j:no \!p:omt \!y:2001 \# esub to WADS01 14 Feb 2001
- Optimal Möbius transformations for information visualization
and meshing.
M. Bern and D. Eppstein.
arXiv:cs.CG/0101006.
7th Worksh. Algorithms and Data Structures, Providence, Rhode Island, 2001.
Lecture Notes in Comp. Sci. 2125, 2001, pp. 14-25, © Springer-Verlag.We give linear-time quasiconvex programming algorithms for finding a Möbius transformation of a set of spheres in a unit ball or on the surface of a unit sphere that maximizes the minimum size of a transformed sphere. We can also use similar methods to maximize the minimum distance among a set of pairs of input points. We apply these results to vertex separation and symmetry display in spherical graph drawing, viewpoint selection in hyperbolic browsing, and element size control in conformal structured mesh generation.
(BibTeX -- Citations -- CiteSeer -- WADS talk slides -- ACM DL)
\- \!all \!geom:all \!geom:lp \!geom:zono \!a:bern \!c:wads \!j:no \!y:2001 \# esub to WADS01 by Bern, 19 Feb 2001
- Optimization over zonotopes and training support vector machines.
M. Bern and D. Eppstein.
arXiv:cs.CG/0105017.
7th Worksh. Algorithms and Data Structures, Providence, Rhode Island, 2001.
Lecture Notes in Comp. Sci. 2125, 2001, pp. 111-121, © Springer-Verlag.We use the ellipsoid method to develop (theoretically) efficient algorithms for optimizing linear functions on intersections of zonotopes, and show how to apply this to train soft-margin support vector classifiers.
(BibTeX -- Citations -- CiteSeer -- WADS talk slides -- ACM DL)
\- \!all \!pure \!rec \!geom:all \!geom:misc \!a:solo \!c:no \!j:no \!y:2001
- Hinged kite mirror dissection.
D. Eppstein.
arXiv:cs.CG/0106032.We show that any polygon can be cut into kites, connected into a chain by hinges at their vertices, and that this hinged assemblage can be unfolded and refolded to form the mirror image of the polygon.
\- \!all \!pure \!geom:all \!geom:misc \!a:demaine \!a:erickson \!a:ghart \!a:orourke \!c:scg \!j:book \!y:2001 \!y:2002 \!y:2003 \# sub to Kuperberg festschrift 26 Oct 2001 \# sub to SCG Dec 2001
- 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
(BibTeX -- Jeff's pubs page)
\- \!all \!pure \!geom:all \!geom:tri \!a:solo \!c:other \!y:2001
- Topological issues in hexahedral meshing.
D. Eppstein.
Invited talk at Conf. Algebraic Topology Methods in Computer Science, Stanford, 2001.We consider the problem of subdividing a polyhedral domain in R^3 into cuboids meeting face-to-face. For topological subdivisions (cell complexes in which each cell is combinatorially equivalent to a cube, but may not be embedded as a polyhedron) and simply-connected domains, a simple necessary and sufficient condition for the existence of a hexahedral mesh is known: a domain with quadrilateral faces can be meshed if and only if there is an even number of faces. However, conditions for the existence of polyhedral meshes remain open, as do the topological versions of the problem for more complicated domain topologies.
\- \!all \!pure \!geom:all \!geom:tri \!a:bern \!a:erickson \!c:imr \!j:other \!y:2001 \!y:2002 \# sub to Sheffer for special IMR issue of Engineering w/Computers 28 Nov 2001
- Flipping cubical meshes.
M. Bern D. Eppstein, and J. Erickson.
arXiv:cs.CG/0108020.
10th Int. Meshing Roundtable, Newport Beach, 2001, pp. 19-29.
Engineering with Computers 18(3):173-187, 2002.We examine flips in which a set of mesh cells connected in a similar pattern to a subset of faces of a cube or hypercube is replaced by cells in the pattern of the complementary subset. We show that certain flip types preserve geometric realizability of a mesh, and use this to study the question of whether every topologically meshable domain is geometrically meshable. We also study flip graph connectivity, and prove that the flip graph of quadrilateral meshes has exactly two connected components.
Note that the Meshing Roundtable version was by Bern and Eppstein. Erickson was added as a co-author during the revisions for the journal version.
(talk slides -- BibTeX -- Citations -- CiteSeer)
\- \!all \!pure \!rec \!geom:all \!a:solo \!c:other \!y:2001
- Triangles and squares.
D. Eppstein.
Invited talk at EuroConf. Combinatorics, Graph Theory, and Applications, Bellaterra, Spain, 2001, p. 114.Which unit-side-length convex polygons can be formed by packing together unit squares and unit equilateral triangles? For instance one can pack six triangles around a common vertex to form a regular hexagon. It turns out that there is a pretty set of 11 solutions. We describe connections from this puzzle to the combinatorics of 3- and 4-dimensional polyhedra, using illustrations from the works of M. C. Escher and others.
\- \!all \!pure \!geom:all \!graph:all \!gdraw \!ramsey \!a:solo \!c:no \!j:no \!p:septhick \!y:2001 \# email sub to lazebnik 30 Oct 2001, reject 12 Jun 2002
- Separating geometric thickness from book thickness.
D. Eppstein.
arXiv:math.CO/0109195.We show that geometric thickness and book thickness are not asymptotically equivalent: for every t, there exists a graph with geometric thickness two and book thickness > t.
\- \!all \!a:lueker \!c:other \!j:other \!y:2001 \!y:2002 \!param \!usesgeom \!geom:zono \# sub by GL to special issue of RSA, 30 Sep 2001 \# acc 27 Jun 2002
- The minimum expectation selection problem.
D. Eppstein and G. Lueker.
10th Int. Conf. Random Structures and Algorithms, Poznan, Poland, August 2001.
arXiv:cs.DS/0110011.
Random Structures and Algorithms 21:278-292, 2002.We define the min-min expectation selection problem (resp. max-min expectation selection problem) to be that of selecting k out of n given discrete probability distributions, to minimize (resp. maximize) the expectation of the minimum value resulting when independent random variables are drawn from the selected distributions. Such problems can be viewed as a simple form of two-stage stochastic programming. We show that if d, the number of values in the support of the distributions, is a constant greater than 2, the min-min expectation problem is NP-complete but admits a fully polynomial time approximation scheme. For d an arbitrary integer, it is NP-hard to approximate the min-min expectation problem with any constant approximation factor. The max-min expectation problem is polynomially solvable for constant d; we leave open its complexity for variable d. We also show similar results for binary selection problems in which we must choose one distribution from each of n pairs of distributions.
\- \!all \!geom:all \!geom:tri \!a:solo \!c:imr \!y:2001
- Global optimization of mesh quality.
D. Eppstein.
Tutorial at 10th Int. Meshing Roundtable, Newport Beach, 2001.Delaunay triangulation has been a staple of triangular mesh generation for a long time. Why? As well as being simple, fast, and visually pleasing, Delaunay triangulations can be shown to be optimal for various measures of mesh quality; for instance, they avoid sharp angles to the maximum extent possible. We review these and other results on construction of meshes that optimize given quality measures, including recent work on postprocessing tetrahedral meshes to eliminate slivers.
\- \!all \!a:wang \!graph:all \!graph:random \!c:other \!j:no \!y:2002
- A steady state model for graph power laws.
D. Eppstein and J. Wang.
2nd Int. Worksh. Web Dynamics, Honolulu, 2002.
arXiv:cs.DM/0204001.We propose a random graph model that (empirically) appears to have a power law degree distribution. Unlike previous models, our model is based on a Markov process rather than incremental growth. We compare our model with others in its ability to predict web graph clustering behavior.
(BibTeX -- Citations -- CiteSeer)
\- \!all \!a:kuperberg \!a:ziegler \!geom:misc \!geom:circle \!geom:all \!geom:hyperbolic \!pure \!c:no \!j:book \!y:2002 \!y:2003
- 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.
\- \!all \!pure \!geom:all \!graph:all \!gdraw \!ramsey \!a:solo \!c:gd \!j:book \!y:2002 \!y:2004 \# esub to GD'02 19 Apr 2002 \# sub to J.Pach special volume on geometric graph th. 29 Jan 2003 \# accept w/revisions 23 Jul 2003
- Separating thickness from geometric thickness.
D. Eppstein.
arXiv:math.CO/0204252.
10th Int. Symp. Graph Drawing, Irvine, 2002.
Lecture Notes in Comp. Sci. 2528
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".
(BibTeX -- GD'02 talk slides -- Citations -- ACM DL)
\- \!all \!graph:all \!graph:cube \!a:falmagne \!c:other \!j:other \!p:algmed \!y:2002 \!y:2003 \!y:2008 \# sub to Mel Janowitz for OSDA special issue of Discrete Math, 13 Apr 2004 \# revised 27 Jul 2005
D. Eppstein and J.-C. Falmagne.
arXiv:cs.DS/0206033.
Int. Conf. Ordinal and Symbolic Data Analysis, Irvine, 2003.
Discrete Applied Mathematics 156(8):1308-1320, 2008.
Falmagne recently introduced the concept of a medium, a combinatorial object encompassing hyperplane arrangements, topological orderings, acyclic orientations, and many other familiar structures. We find efficient solutions for several algorithmic problems on media: finding short reset sequences, shortest paths, testing whether a medium has a closed orientation, and listing the states of a medium given a black-box description.
(BibTeX -- Citations -- OSDA talk slides)
\- \!all \!geom:all \!geom:misc \!a:bern \!c:soda \!j:no \!p:minni \!y:2002 \!y:2003 \# esub to SODA 9 Jul 2002
M. Bern and D. Eppstein.
arXiv:cs.CG/0207081.
14th ACM-SIAM Symp. Discrete Algorithms, Baltimore, 2003, pp. 128-129.
Natural neighbor interpolation is a well-known technique for fitting a surface to scattered data, with some nice properties including smoothness everywhere except the data and exact fitting of linear functions. The interpolated surface is formed from a weighted combination of data values at the "natural neighbors" (neighbors in the Delaunay triangulation), with weights related to Voronoi cell areas. We describe a variation of natural neighbor interpolation, using different weights based on Delaunay circle angles, that remains invariant when the data is transformed by Möbius transformations, and reconstructs harmonic functions in the limit of dense data on a circle.
(BibTeX -- SODA talk slides)
\- \!all \!graph:dyn \!graph:all \!a:solo \!c:soda \!j:no \!p:dyngen \!y:2002 \!y:2003 \# esub to SODA 27 Jun 2002
D. Eppstein.
arXiv:cs.DS/0207082.
14th ACM-SIAM Symp. Discrete Algorithms, Baltimore, 2003, pp. 599-608.
We describe a decomposition of graphs embedded on 2-dimensional manifolds into three subgraphs: a spanning tree, a dual spanning tree, and a set of leftover edges with cardinality determined by the genus of the manifold. This tree-cotree decomposition allows us to find efficient data structures for dynamic graphs (allowing updates that change the surface), better constants in bounded-genus graph separators, and efficient algorithms for tree-decomposition of bounded-genus bounded-diameter graphs.
(BibTeX -- SODA talk slides -- Citations)
\- \!all \!misc \!a:givargis \!c:other \!j:other \!y:2002 \!y:2005
D. Eppstein and T. Givargis.
Worksh. Embedded System Codesign (ESCODES'02), San Jose, 2002, pp. 43-48.
J. Microprocessors & Microsystems 29(4):145-153, 2005.
We study the problem of minimizing transitions in address signals on a bus. The UDRC part of the title refers to an algorithm for coding signals with at most one transition per signal (using an increased number of wires); we combine this with a scheme for caching previously coded addresses and use trace data to compare our technique with previous approaches.
(BibTeX -- Citations -- CiteSeer)
\- \!all \!geom:all \!geom:misc \!geom:lp \!a:bern \!c:scg \!j:no \!p:gamut \!y:2002 \!y:2003
M. Bern and D. Eppstein.
arXiv:cs.CG/0212007.
19th ACM Symp. Comp. Geom., San Diego, 2003, pp. 274-281.
We consider the problem of finding a large color space that can be generated by all units in multi-projector tiled display systems. Viewing the problem geometrically as one of finding a large parallelepiped within the intersection of multiple parallelepipeds, and using colorimetric principles to define a volume-based objective function for comparing feasible solutions, we develop an algorithm for finding the optimal gamut in time O(n3), where n denotes the number of projectors in the system. We also discuss more efficient quasiconvex programming algorithms for alternative objective functions based on maximizing the quality of the color space extrema.
(BibTeX -- SCG talk slides)
\- \!all \!geom:all \!graph:all \!graph:sgi \!gdraw \!a:dickerson \!a:goodrich \!a:meng \!c:gd \!j:jga \!p:confluent \!y:2002 \!y:2003 \!y:2004 \!y:2005
M. Dickerson, D. Eppstein, M. T. Goodrich, and J. Meng.
arXiv:cs.CG/0212046.
11th Int. Symp. Graph Drawing, Perugia, Italy, 2003.
Lecture Notes in Comp. Sci. 2912, 2004, pp. 1-12, © Springer-Verlag.
J. Graph Algorithms and Applications (special issue for GD'03) 9(1):31-52, 2005.
We describe a new method of drawing graphs, based on allowing the edges to be merged together and drawn as "tracks" (similar to train tracks). We present heuristics for finding such drawings based on my previous algorithms for finding maximal bipartite subgraphs, prove that several important families of graphs have confluent drawings, and provide examples of other graphs that can not be drawn in this way.
\- \!geom:all \!geom:misc \!all \!a:solo \!c:other \!y:2003
D. Eppstein.
Talk at SIAM Conf. on Computational Science and Engineering, San Diego, 2003.
This talk, for the CSE session on combinatorial scientific computing, surveys my work with Marshall Bern on optimal Möbius transformation and Möbius-invariant natural neighbor transformation.
\- \!all \!geom:all \!geom:tri \!a:sullivan \!a:ungor \!c:no \!j:cgta \!y:2003 \!y:2004 \# Alper was going to sub to CGTA on or around 19 Feb 2003
D. Eppstein, J. M. Sullivan, and A. Üngör.
arXiv:cs.CG/0302027.
Comp. Geom. Theory & Applications 27(3):237-255, 2004.
We show it is possible to triangulate three-dimensional space using only tetrahedra with acute dihedral angles. We present several constructions to achieve this, including one in which all dihedral angles are less than 77.08 degrees, and another which tiles a slab in space.
(BibTeX)
\- \!all \!graph:all \!tsp \!exponential \!a:solo \!c:wads \!j:jga \!y:2003 \!y:2007 \# esub to JGAA 19 Apr 2004
D. Eppstein.
arXiv:cs.DS/0302030.
8th Worksh. Algorithms and Data Structures, Ottawa, 2003.
Lecture Notes in Comp. Sci. 2748, 2003, pp. 307-318, © Springer-Verlag.
J. Graph Algorithms and Applications 11(1):61-81, 2007.
We find improved exponential-time algorithms for exact solution of the traveling salesman problem on graphs of maximum degree three and four. We also consider related problems including counting the number of Hamiltonian cycles in such graphs.
(BibTeX -- WADS talk slides -- Citations)
\- \!all \!geom:all \!geom:dyn \!a:cardinal \!c:other \!j:no \!y:2003 \!y:2004
J. Cardinal and D. Eppstein.
Tech. Rep. 502, Univ. Libre de Bruxelles, Computer Science Dept., 2003.
Worksh. Algorithm Engineering and Experiments (ALENEX), New Orleans, 2004.
Joint Proc. Worksh. Algorithm Engineering and Experiments (ALENEX) and Worksh. Analytic Algorithmics and Combinatorics (ANALCO), 2004, pp. 112-119.
We modify my previous data structures for dynamic closest pairs, to use a lazy deletion mechanism, and show in experiments that the results are an improvement on the unmodified structures.
\- \!all \!a:solo \!geom:all \!geom:lp \!exponential \!c:soda \!j:algs \!p:qaba \!y:2003 \!y:2004 \!y:2006 \# esub to Trans. Alg. special issue for SODA'04, 2 Jun 2004
D. Eppstein.
arXiv:cs.DS/0304018.
15th ACM-SIAM Symp. Discrete Algorithms, New Orleans, 2004, pp. 781-790.
ACM Trans. Algorithms 2(4):492-509 (special issue for SODA 2004), 2006.
We consider a class of multivariate recurrences frequently arising in the worst case analysis of Davis-Putnam-style exponential time backtracking algorithms for NP-hard problems. We describe a technique for proving asymptotic upper bounds on these recurrences, by using a suitable weight function to reduce the problem to that of solving univariate linear recurrences; show how to use quasiconvex programming to determine the weight function yielding the smallest upper bound; and prove that the resulting upper bounds are within a polynomial factor of the true asymptotics of the recurrence. We develop and implement a multiple-gradient descent algorithm for the resulting quasiconvex programs, using a real-number arithmetic package for guaranteed accuracy of the computed worst case time bounds.
The journal version uses the longer title "Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms".
(BibTeX -- SODA talk slides -- Citations)
\- \!all \!geom:all \!geom:deep \!stat \!a:solo \!c:other \!y:2003
D. Eppstein.
Invited talk at DIMACS Worksh. on Data Depth, New Brunswick, NJ, 2003.
Invited talk at MSRI Introductory Worksh. Discrete & Computational Geometry, Berkeley, CA, 2003.
Surveys projective duality and its uses in algorithms for robust regression. The MSRI talk used the alternative title "Computational geometry and robust statistics" but contained essentially the same content.
(DIMACS talk slides -- video and slides of MSRI talk)
\- \!all \!geom:all \!geom:lp \!geom:tri \!exponential \!gdraw \!stat \!survey \!a:solo \!c:other \!y:2003 \!y:2004 \!y:2005 \# sub to Goodman for MSRI volume 28 Feb 2004, acc late November 2004
D. Eppstein.
Invited talk at DIMACS Worksh. on Geometric Optimization, New Brunswick, NJ, 2003.
Plenary talk at ALGO 2004, Bergen, Norway, 2004.
arXiv:cs.CG/0412046.
Combinatorial and Computational Geometry, Goodman, Pach, and Welzl, eds., MSRI Publications 52, 2005, pp. 287-331.
Defines quasiconvex programming, a form of generalized linear programming in which one seeks the point minimizing the pointwise maximum of a collection of quasiconvex functions. Surveys algorithms for solving quasiconvex programs either numerically or via generalizations of the dual simplex method from linear programming, and describe varied applications of this geometric optimization technique in meshing, scientific computation, information visualization, automated algorithm analysis, and robust statistics.
(DIMACS talk slides -- ALGO talk slides)
\- \!all \!geom:all \!geom:misc \!a:solo \!c:no \!j:dcg \!y:2003
D. Eppstein.
Disc. Comp. Geom. 30:1-2, 2003 (special issue for 17th Symp. Comp. Geom.)
(BibTeX)
\- \!all \!geom:all \!mst \!graph:all \!gdraw \!a:solo \!c:soda \!j:talg \!y:2003 \!y:2004 \!y:2009 \# esub to SODA 1 Jul 2003 \# esub to TALG 8 May 2006
D. Eppstein.
arXiv:cs.CG/0307023.
15th ACM-SIAM Symp. Discrete Algorithms, New Orleans, 2004, pp. 853-861.
ACM Trans. Algorithms 5(2):15, 2009.
We consider problems of partitioning sets of geometric objects into two subsets, such that no two objects within the same subset intersect each other. Typically, such problems can be solved in quadratic time by constructing the intersection graph and then applying a graph bipartiteness testing algorithm; we achieve subquadratic times for general objects, and O(n log n) times for balls in R^d or simple polygons in the plane, by using geometric data structures, separator based divide and conquer, and plane sweep techniques, respectively. We also contrast the complexity of bipartiteness testing with that of connectivity testing, and provide evidence that for some classes of object, connectivity is strictly harder due to a computational equivalence with Euclidean minimum spanning trees.
(BibTeX -- Citations -- SODA talk slides)
\- \!all \!geom:all \!geom:approx \!geom:deep \!stat \!a:goodrich \!a:bagchi \!a:amic \!c:scg \!j:talg \!y:2003 \!y:2004 \!y:2007 \# esub to SODA, reject 9 Sep 2003 \# esub to SCG, 10 Dec 2003
A. Bagchi, A. Chaudhary, D. Eppstein, and M. T. Goodrich.
arXiv:cs.CG/0307027.
20th ACM Symp. Comp. Geom., Brooklyn, 2004, pp. 144-151.
ACM Trans. Algorithms 3(2):A16, 2007.
We describe an efficient streaming-model construction of epsilon-nets and epsilon-approximations, and use it to find deterministic streaming-model approximation algorithms for iceberg range queries and for various robust statistics problems.
\- \!all \!geom:all \!gdraw \!a:goodrich \!c:gd \!j:no \!y:2003 \!y:2004
F. J. Brandenburg, D. Eppstein, M. T. Goodrich, S. G. Kobourov, G. Liotta, and P. Mutzel.
11th Int. Symp. Graph Drawing, Perugia, Italy, 2003.
Lecture Notes in Comp. Sci. 2912, 2004, pp. 515-539, © Springer-Verlag.
We survey a number of open problems in theoretical and applied graph drawing.
\- \!all \!pure \!geom:all \!geom:misc \!a:dillencourt \!c:no \!j:other \!y:2003 \# esub to eg-models.de 14 Aug 2003
M. Dillencourt and D. Eppstein.
Electronic Geometry Models 2003.08.001.
We find an example of a three-dimensional polyhedron, with four edges per vertex, that can not be placed in convex position with all vertices on the surface of a sphere.
\- \!all \!geom:all \!geom:lp \!geom:hyperbolic \!a:solo \!c:other \!y:2003
D. Eppstein.
Invited talk at MSRI Introductory Worksh. Discrete & Computational Geometry, Berkeley, CA, 2003.
Describes extensions of computational geometry algorithms to hyperbolic geometry, including an output-sensitive 3d Delaunay triangulation algorithm of Boissonat et al. and my own research on optimal Möbius transformation.
\- \!all \!a:duncan \!a:kobourov \!pure \!geom:all \!graph:all \!gdraw \!c:scg \!j:no \!y:2003 \!y:2004 \# esub to SoCG
C. Duncan, D. Eppstein, and S. Kobourov.
arXiv:cs.CG/0312056.
20th ACM Symp. Comp. Geom., Brooklyn, 2004, pp. 340-346.
We show that graphs with maximum degree four have geometric thickness at most two, by partitioning them into degree two subgraphs and applying simultaneous embedding techniques.
\- \!all \!a:gopi \!geom:all \!geom:tri \!graph:all \!graph:match \!tsp \!c:scg \!c:other \!j:no \!p:singlestrip \!y:2004 \# esub long version to EuroGraphics 2 Feb 2004 \# sub to SoCG video 8 Feb 2004
D. Eppstein and M. Gopi.
13th Video Review of Computational Geometry, 2004.
20th ACM Symp. Comp. Geom., Brooklyn, 2004, pp. 455-456 (abstract for video).
25th Conf. Eur. Assoc. for Computer Graphics (EuroGraphics '04), Grenoble, 2004 (2nd best paper award).
Eurographics Forum 23(3):371-379, 2004.
arXiv:cs.CG/0405036.
We describe a new algorithm, based on graph matching, for subdividing a triangle mesh (without boundary) so that it has a Hamiltonian cycle of triangles, and prove that this subdivision process increases the total number of triangles in the mesh by at most a factor of 3/2. We also prove lower bounds on the increase needed for meshes with and without boundary.
(Graphics lab pubs page -- Citations)
\- \!all \!graph:all \!graph:misc \!a:amic \!a:bagchi \!a:bhargava \!a:scheideler \!graph:all \!graph:misc \!c:other \!j:other \!y:2004 \!y:2006
A. Bagchi, A. Bhargava, A. Chaudhary, D. Eppstein, and C. Scheideler.
arXiv:cs.DC/0404029.
16th ACM Symp. Parallelism in Algorithms and Architectures, Barcelona, 2004, pp. 286-293.
Theory of Computing Systems 39(6):903-928, 2006.
Studies the resilience of distributed computation networks against adversarial and random fault models; shows that, in both models, certain networks can withstand constant fault probabilities and still contain a large subnetwork with similar expansion to the original.
\- \!all \!pure \!graph:all \!graph:cube \!graph:match \!a:solo \!c:no \!j:other \!p:latdim \!y:2004 \!y:2005 \# sub w/Ovchinnik tree paper to Deza for Eur. J. Comb. 12 Feb 2004 \# acc subj to revision 4 May 2004, revised and fully accepted
D. Eppstein.
arXiv:cs.DS/0402028.
Eur. J. Combinatorics 26(6):585-592, 2005.
Describes a polynomial time algorithm for isometrically embedding graphs into an integer lattice of the smallest possible dimension. The technique involves maximum matching in an auxiliary graph derived from a partial cube representation of the input.
\- \!all \!gdraw \!geom:all \!graph:all \!graph:cube \!a:solo \!c:gd \!j:no \!p:afdm \!y:2004 \# esub to GD04 30 May 2004, conf# DE32 \# sub to JGAA special issue 1 Dec 2004 \# see email "Old forgotten JGAA submission", April 20, 2009
D. Eppstein.
arXiv:cs.DS/0406020.
12th Int. Symp. Graph Drawing, New York, 2004.
Lecture Notes in Comp. Sci. 3383, 2004, pp. 173-183.
We describe two algorithms for finding planar layouts of partial cubes: one based on finding the minimum-dimension lattice embedding of the graph and then projecting the lattice onto the plane, and the other based on representing the graph as the planar dual to a weak pseudoline arrangement.
Due to editorial mishandling there will be no journal version of this paper: I submitted it to a journal in 2004, the reviews were supposedly sent back to me in 2005, but I didn't receive them and didn't respond to them, leading the editors to assume that I intended to withdraw the submission. Large portions of the paper have since been incorporated into my book Media Theory, making journal publication moot.
(GD04 talk slides -- BibTeX -- Citations -- GDEA)
\- \!all \!geom:all \!graph:all \!graph:color \!gdraw \!a:goodrich \!a:meng \!c:gd \!j:algo \!y:2004 \!y:2005 \!y:2007 \# sub by JM to GD03 contest 15 Aug 2003, under title \# Dancing bicliques: visualizing bipartite subgraph cover in layered graphs \# sub by JM to GD04 as full paper 31 May 2004? \# sub by JM to Algorithmica special issue 15 Nov 2004
D. Eppstein, M. T. Goodrich, and J. Meng.
12th Int. Symp. Graph Drawing, New York, 2004.
Lecture Notes in Comp. Sci. 3383, 2004, pp. 184-194.
arXiv:cs.CG/0507051.
Algorithmica 47(4):439-452 (special issue for Graph Drawing), 2007.
Describes a graph drawing technique combining ideas of confluent drawing with Sugiyama-style layered drawing. Uses a reduction to graph coloring to find and visualize sets of bicliques in each layer.
\- \!all \!graph:all \!graph:dyn \!exponential \!kbest \!a:solo \!c:soda \!j:talg \!y:2004 \!y:2005 \!y:future \# esub to TALG 31 Oct 2006
D. Eppstein.
arXiv:cs.DS/0407036.
16th ACM-SIAM Symp. Discrete Algorithms, Vancouver, 2005, pp. 451-459.
ACM Trans. Algorithms, to appear.
We show how to apply reverse search to list all maximal independent sets in bounded-degree graphs in constant time per set, in graphs from minor closed families in linear time per set, and in sparse graphs in subquadratic time per set. The latter two results rely on new data structures for maintaining a dynamic vertex set in a graph and quickly testing whether the set dominates all other vertices.
(SODA05 talk slides -- BibTeX)
\- \!all \!geom:all \!geom:lp \!geom:path \!a:wortman \!c:scg \!j:cgta \!y:2004 \!y:2005 \!y:2007 \# esub to SODA05, rejected \# esub to SoCG05, accepted \# invited to special issue of CGTA, submitted 27 Jul 2005
D. Eppstein and K. Wortman.
arXiv:cs.CG/0412025.
21st ACM Symp. Comp. Geom., Pisa, 2005, pp. 321-326.
Comp. Geom. Theory & Applications 37(1):27-37, 2007.
We show how to test the dilation of a star, embedded in a Euclidean space of bounded dimension, in time O(n log n), and how to find the star center that has the minimum dilation for a given set of leaf points in randomized expected time O(n log n). For two-dimensional points, we can find the minimum dilation center, constrained to be one of the input points, in time O(n 2α(n) log2n). The unconstrained center placement algorithm involves quasiconvex programming, and is used as a subroutine in the constrained center placement algorithm.
(SoCG05 talk slides -- Citations -- BibTeX)
\- \!all \!geom:all \!geom:deep \!geom:hyperbolic \!stat \!a:solo \!c:no \!j:other \!y:2004
D. Eppstein.
J. Amer. Stat. Assoc. 99(468):976-979, 2004.
Discusses a paper by Mizera and Müller on depth-based methods for simultaneously fitting both a center and a radius to a set of sample points, by viewing the points as lying on the boundary of a model of a higher dimensional hyperbolic space. Reformulates their method in combinatorial terms more likely to be familiar to computational geometers, and discusses the algorithmic implications of their work.
\- \!all \!misc \!a:goodrich \!a:hirschberg \!c:wads \!j:sjc \!y:2005 \!y:2007 \# esub to STOC05 3 Nov 2004, rejected \# esub to WADS05 14 Feb 2005 \# sub to SICOMP 18 May 2005, accept 7 Jun 2006
D. Eppstein, M. T. Goodrich, and D. S. Hirschberg.
9th Worksh. Algorithms and Data Structures, Waterloo, 2005.
Lecture Notes in Comp. Sci. 3608, 2005, pp. 86-98.
arXiv:cs.DS/0505048.
SIAM J. Computing 36(5):1360-1375, 2007.
We study practically efficient methods for finding few flawed items among large sets of items, by testing whether there exist flaws in each of a small number of batches of items.
(BibTeX -- Mike's WADS talk slides)
\- \!all \!geom:all \!geom:qt \!a:goodrich \!a:sun \!c:scg \!j:ijcga \!y:2005 \!y:2008 \# submitted to special issue of IJCGA, 7 Sep 2005
D. Eppstein, M. T. Goodrich, and J. Z. Sun.
21st ACM Symp. Comp. Geom., Pisa, 2005, pp. 296-305.
arXiv:cs.CG/0507049.
Int. J. Comp. Geom. & Appl. 18(1-2):131-160, 2008.
We describe a data structure consisting of a sequence of compressed quadtrees for successively sparser samples of an input point set, with connections between the same squares in successive members of the sequence. Using this structure, we can insert or delete points and answer approximate range queries and approximate nearest neighbor queries in O(log n) time per operation.
(SoCG05 talk slides -- BibTeX)
\- \!all \!geom:all \!geom:qt \!a:arge \!a:goodrich \!c:other \!j:no \!y:2005 \# esub to PODC05, accepted
L. Arge, D. Eppstein, and M. T. Goodrich.
Proc. 24th ACM SIGACT-SIGOPS Symp. Principles of Distributed Computing (PODC 2005), Las Vegas, July 2005, pp. 69-76.
arXiv:cs.DC/0507050.
Describes efficient distributed versions of skip quadtrees and related spatial searching structures.
\- \!all \!graph:all \!graph:misc \!param \!a:carlson \!c:swat \!j:no \!y:2005 \!y:2006
J. Carlson and D. Eppstein.
arXiv:cs.CG/0503023.
Proc. 10th Scand. Worksh. Algorithm Theory (SWAT 2006).
Lecture Notes in Comp. Sci. 4059, 2006, pp. 397-408.
We give a linear time algorithm for pruning a node-weighted tree to maximize the average node weight of the pruned subtree; this problem was previously studied under the less obvious name "The Fractional Prize-Collecting Steiner Tree Problem on Trees".
(BibTeX)
\- \!all \!geom:all \!graph:all \!gdraw \!a:goodrich \!a:meng \!c:gd \!j:no \!y:2005
D. Eppstein, M. T. Goodrich, and J. Meng.
13th Int. Symp. Graph Drawing, Limerick, Ireland, 2005.
Lecture Notes in Comp. Sci. 3843, 2006, pp. 165-176.
arXiv:cs.CG/0510024.
We characterize the graphs that can be drawn confluently with a single confluent track that is tree-like except for three-way Delta junctions, as being exactly the distance hereditary graphs. Based on this characterization, we develop efficient algorithms for drawing these graphs.
(BibTeX -- GD'05 talk slides)
\- \!all \!rec \!graph:all \!graph:path \!c:no \!j:no \!y:2005
D. Eppstein.
arXiv:cs.DS/0507053.
We describe algorithms and hardness results for finding paths in edge-labeled graphs such that no two consecutive edges have the same label, and use our algorithms to implement heuristics for a program that automatically solves and generates Sudoku puzzles.
\- \# single strips for manifolds with boundary \# myself, gopi; gopi's students pablo and anusheel? \# submitted anonymously to geometry processing symp 27 Apr 2005 \# reject 25 May 2005 \!all \!geom:all \!graph:all \!gdraw \!a:dujmovic \!a:suderman \!a:wood \!c:no \!j:cgta \!y:2006 \!y:2007
V. Dujmović, D. Eppstein, M. Suderman, and D. R. Wood.
arXiv:math.CO/0606450.
Comp. Geom. Theory & Applications 38:194-212, 2007.
We study straight-line drawings of planar graphs with few segments and few slopes. Optimal results are obtained for all trees. Tight bounds are obtained for outerplanar graphs, 2-trees, and planar 3-trees. We prove that every 3-connected plane graph on n vertices has a plane drawing with at most 5n/2 segments and at most 2n slopes. We prove that every cubic 3-connected plane graph has a plane drawing with three slopes (and three bends on the outerface).
\- \!all \!geom:all \!graph:all \!graph:cube \!pure \!a:solo \!c:no \!j:other \!y:2005 \!y:2006 \# esub to EJC 24 Apr 2006 \# revised per very minor suggestions and reformatted for EJC 20 Aug 2006
D. Eppstein.
arXiv:math.CO/0510263.
Electronic J. Combinatorics 13(1) #R79, 2006.
We show how to construct a cubic partial cube from any simplicial arrangement of lines or pseudolines in the projective plane. As a consequence, we find nine new infinite families of cubic partial cubes as well as many sporadic examples.
\- \!all \!a:bushan \!a:diaz-gutierrez \!a:gopi \!geom:all \!geom:tri \!graph:all \!graph:match \!tsp \!c:other \!j:no \!y:2005 \!y:2006 \# an esub and reject or two that I've lost track of, ask Gopi \# esub SIBGRAPI 13 May 2006
A. Bushan, P. Diaz-Gutierrez, D. Eppstein, and M. Gopi.
Tech. Rep. 05-11, UC Irvine, School of Information and Computer Science, 2005.
Proc. 19th Brazilian Symp. Computer Graphics and Image Processing (SIBGRAPI 2006), pp. 221-228.
This follows on to our previous paper on using graph matching to cover a triangulated polyhedral model with a single triangle strip by extending the algorithms to models with boundaries. We provide two methods: one is based on using an algorithm for the Chinese Postman problem to find a small set of triangles to split in order to find a perfect matching in the dual mesh, while the other augments the model with virtual triangles to remove the boundaries and merges the strips formed by our previous algorithm on this augmented model. We implement the algorithms and report some preliminary experimental results.
\- \!all \!geom:all \!geom:path \!a:wortman \!a:augustine \!c:no \!j:no \!y:2006 \# esub to SoCG06, reject \# esub to WADS, reject
J. Augustine, D. Eppstein, and K. Wortman.
arXiv:cs.CG/0602029.
The problem is to quickly find, in a set of sites with weights, the site maximizing the product of its weight with its distance from the query point. Our solution combines known results on core-sets with a reduction from the weighted to the unweighted problem that works in any metric space. This leads to fast approximation algorithms for the constrained minimum dilation star problem in any fixed dimension.
\- \!all \!geom:all \!geom:misc \!a:goodrich \!a:sitchinava \!c:scg \!j:no \!y:2006 \!y:2007 \# esub to SoCG06, rejected \# esub to SODA07
D. Eppstein, M. T. Goodrich, and N. Sitchinava.
arXiv:cs.CG/0603057.
23rd ACM Symp. Comp. Geom., Gyeongju, South Korea, 2007, pp. 27-36.
The problem is to place as few wedges as possible in the plane such that a desired polygon can be formed as some monotone Boolean combination of the wedges. The motivation is for wireless devices to prove that they are located within a target area by their ability to communicate with a subset of base stations (the wedges). We provide upper and lower bounds on the number of wedges needed for several classes of polygons.
\- \#all \#misc \#a:goodrich \#a:sitchinava \#c:no \#j:no \# esub to FOCS06, reject \# esub to SODA07, reject \# esub to SPAA07, reject \# esub to PODC07, reject \# esub to SPAA08, reject
D. Eppstein, M. T. Goodrich, and N. Sitchinava.
\- \!all \!geom:all \!geom:mst \!stat \!a:solo \!c:soda \!geom:hyperbolic \!j:talg \!y:2006 \!y:2007 \!y:2009 \# esub to FOCS06, reject \# esub to SODA07 \# email to Gabow for TALG SODA special 5 Feb 2007
D. Eppstein.
arXiv:cs.CG/0604034.
18th ACM-SIAM Symp. Discrete Algorithms, New Orleans, 2007, pp. 29-38.
ACM Trans. Algorithms 5(3): Article 29, 2009.
We find efficient constant factor approximation algorithms for hierarchically clustering of a point set in any metric space, minimizing the sum of minimimum spanning tree lengths within each cluster, and in the hyperbolic or Euclidean planes, minimizing the sum of cluster perimeters. Our algorithms for the hyperbolic and Euclidean planes can also be used to provide a pants decomposition with approximately minimum total length.
\- \!all \!graph:all \!graph:misc \!a:bozorgzadeh \!a:singhal \!c:no \!j:other \!y:2007 \# esub by Singhal to TCAD, 9 May 2006
L. Singhal, E. Bozorgzadeh, and D. Eppstein.
IEEE Trans. CAD 26(10):1803-1817, 2007.
We consider a problem of assigning delays to components in a circuit so that each component is part of a critical path, but the number of edges belonging to critical paths is minimized. We show the problem to be NP-complete via a reduction from finding independent dominating sets in bipartite graphs minimizing dominated edges, and give experimental results on heuristics.
\- \!all \!gdraw \!geom:all \!graph:all \!graph:cube \!a:solo \!c:gd \!j:jga \!y:2006 \!y:2007 \!y:2008 \# esub to GD06 3 Jun 2006 \# sub to JGAA special issue 24 Oct 2006 \# revised February 2008
D. Eppstein.
arXiv:cs.CG/0607094.
14th Int. Symp. Graph Drawing, Karlsruhe, Germany, 2006.
Lecture Notes in Comp. Sci. 4372, 2007, pp. 282-293, © Springer-Verlag.
J. Graph Algorithms and Applications 12(1):51-72, 2008 (special issue for GD'06).
We consider graph drawing algorithms for learning spaces, a type of st-oriented partial cube derived from antimatroids and used to model states of knowledge of students. We show how to draw any st-planar learning space so all internal faces are convex quadrilaterals with the bottom side horizontal and the left side vertical, with one minimal and one maximal vertex. Conversely, every such drawing represents an $st$-planar learning space. We also describe connections between these graphs and arrangements of translates of a quadrant.
\- \!all \!gdraw \!geom:all \!graph:all \!a:carlson \!c:gd \!j:no \!y:2006 \!y:2007 \# esub to GD06 3 Jun 2006
J. Carlson and D. Eppstein.
arXiv:cs.CG/0607113.
14th Int. Symp. Graph Drawing, Karlsruhe, Germany, 2006.
Lecture Notes in Comp. Sci. 4372, 2007, pp. 77-88, © Springer-Verlag.
We consider drawings of trees which, if the leaf edges were extended to infinite rays, would form partitions of the plane into unbounded convex polygons. For such a drawing the edges may be chosen independently without any possibility of edge crossing. We show how to choose the angles of such drawings to optimize the angular resolution of the drawing.
\- \!all \!gdraw \!geom:all \!graph:all \!graph:color \!a:dillencourt \!a:goodrich \!c:gd \!j:no \!y:2006 \!y:2007 \# esub to GD06 3 Jun 2006
M. Dillencourt, D. Eppstein, and M. T. Goodrich.
arXiv:cs.CG/0609033.
14th Int. Symp. Graph Drawing, Karlsruhe, Germany, 2006.
Lecture Notes in Comp. Sci. 4372, 2007, pp. 294-305, © Springer-Verlag.
We show how to choose colors for the vertices of a graph drawing in such a way that all colors are easily distinguishable, but such that adjacent vertices have especially dissimilar colors, by considering the problem as one of embedding the graph into a three-dimensional color space.
\- \!all \!geom:all \!geom:tri \!geom:path \!graph:all \!graph:cube \!a:solo \!c:scg \!j:sub \!y:2006 \!y:2007 \# esub to SoCG07 20 Nov 2006 \# sub to JOCG 6 Oct 2009
D. Eppstein.
arXiv:cs.CG/0610092.
23rd ACM Symp. Comp. Geom., Gyeongju, South Korea, 2007, pp. 92-101.
We show that the triangulations of a finite point set form a flip graph that can be embedded isometrically into a hypercube, if and only if the point set has no empty convex pentagon. Point sets of this type include convex subsets of lattices, points on two lines, and several other infinite families. As a consequence, flip distance in such point sets can be computed efficiently.
\- \!all \!geom:all \!geom:hyperbolic \!graph:all \!graph:cube \!pure \!a:solo \!c:no \!j:other \!p:manhattan \!y:2006 \!y:2009 \# esub to Topology and its Applications, 10 May 2007 \# revised 4 Apr 2009
D. Eppstein.
arXiv:math.MG/0612109.
Topology and its Applications 157(2): 494-507, 2009.
We investigate a class of metrics for 2-manifolds in which, except for a discrete set of singular points, the metric is locally isometric to an L1 metric, and show that with certain additional conditions such metrics are injective. We use this construction to find the tight span of squaregraphs and related graphs, and we find an injective metric that approximates the distances in the hyperbolic plane analogously to the way the rectilinear metrics approximate the Euclidean distance.
\- \!all \!geom:all \!graph:all \!gdraw \!a:kreveld \!a:mumford \!a:speckmann \!c:other \!c:wads \!j:cgta \!y:2007 \!y:2009 \# longer version submitted (?) to WADS07 \# esub to CGTA special for EWCG07, 1 Jun 2007
D. Eppstein, M. van Kreveld, E. Mumford, and B. Speckmann.
23rd European Workshop on Computational Geometry (EWCG'07), Graz, 2007.
10th Worksh. Algorithms and Data Structures, Halifax, Nova Scotia, 2007.
Lecture Notes in Comp. Sci. 4619, 2007, pp. 77-88, © Springer-Verlag.
Tech. Rep. UU-CS-2007-042, Utrecht Univ., Dept. of Information and Computing Sciences, 2007.
arXiv:0705.0413.
Comp. Geom. Theory & Applications 42(8): 790-802, 2009 (special issue for EWCG'07).
We show how to solve several versions of the problem of casing graph drawings: that is, given a drawing, choosing to draw one edge as upper and one lower at each crossing in order to improve the drawing's readability.
\- \!all \!misc \!a:goodrich \!c:wads \!j:other \!y:2007 \!y:future \# esub to WADS07, 1 Mar 2007 \# sub to IEEE TKDE 5 May 2009
D. Eppstein, and M. T. Goodrich.
10th Worksh. Algorithms and Data Structures, Halifax, Nova Scotia, 2007.
Lecture Notes in Comp. Sci. 4619, 2007, pp. 637-648, © Springer-Verlag.
arXiv:0704.3313.
IEEE Trans. Knowledge and Data Engineering, to appear.
We consider data structures for handling streams of check-in and check-out requests, and that must identify the set of check-ins that are not matched by a corresponding check-out. We show that, if this set has size k, it is possible to handle this problem in space O(k log n) by a deterministic data structure. However, if check-outs may occur that do not match any check-in, then no low-space deterministic solution is possible; instead, we provide a randomized solution with near-optimal space and high probability of answering queries correctly.
\- \!all \!graph:all \!graph:cube \!a:falmagne \!a:uzun \!c:no \!j:other \!y:2007 \!y:2009 \# esub by jcf to J. Mathematical Psychology, 19 May 2007 \# revision 17 Nov 2007
D. Eppstein, J.-C. Falmagne, and H. Uzun.
arXiv:0704.2919.
38th Meeting of the European Mathematical Psychology Group, Luxembourg, 2007.
J. Mathematical Psychology 53(1):34-39, 2009.
We describe tests for whether the union-closure of a set family is well-graded, and algorithms for finding a minimal well-graded union-closed superfamily of a given set family.
\- \!all \!graph:all \!graph:cube \!a:solo \!c:soda \!j:no \!y:2007 \!y:2008
D. Eppstein.
arXiv:0705.1025.
19th ACM-SIAM Symp. Discrete Algorithms, San Francisco, 2008, pp. 1258-1266.
We show how to test whether a graph is a partial cube, and if so embed it isometrically into a hypercube, in time O(n2), improving previous O(nm)-time solutions; here n is the number of vertices and m is the number of edges. The ideas are to use bit-parallelism to speed up previous approaches to the embedding step, and to verify that the resulting embedding is isometric using an all-pairs shortest path algorithm from "algorithms for media".
(slides)
\- \!all \!graph:all \!graph:cube \!pure \!a:solo \!c:other \!j:no \!y:2007
D. Eppstein.
Invited talk at 6th Slovenian International Conference on Graph Theory, Bled, Slovenia, 2007.
I survey some of my recent results on geometry of partial cubes, including lattice dimension, graph drawing, cubic partial cubes, and partial cube flip graphs of triangulations.
\- \!all \!graph:all \!geom:all \!gdraw \!pure \!a:solo \!c:gd \!j:no \!y:2007 \!y:2008 \# esub to SoCG08, reject \# esub to Graph Drawing 2008
D. Eppstein.
arXiv:0709.4087.
Proc. 16th Int. Symp. Graph Drawing, Heraklion, Crete, 2008.
Lecture Notes in Computer Science 5417, 2009, pp. 78-89.
Defines a class of orthogonal graph drawings formed by a point set in three dimensions for which axis-parallel line contains zero or two vertices, with edges connecting pairs of points on each nonempty axis-parallel line. Shows that the existence of such a drawing can be defined topologically, in terms of certain two-dimensional surface embeddings of the same graph. Based on this equivalence, describes algorithms, graph-theoretic properties, and hardness results for graphs of this type.
(Slides from talk at U. Arizona, February 2008 -- Slides from GD08) )
\- \!all \!graph:all \!graph:cube \!pure \!a:falmagne \!a:ovchinnikov \!y:2007
D. Eppstein, J.-C. Falmagne, and S. Ovchinnikov.
Springer-Verlag, 2007, ISBN 978-3-540-71696-9.
Many combinatorial structures such as the set of acyclic orientations of a graph, weak orderings of a set of elements, or chambers of a hyperplane arrangement have the structure of a partial cube, a graph in which vertices may be labeled by bitvectors in such a way that graph distance equals Hamming distance. This book analyzes these structures in terms of operations that change one vertex to another by flipping a single bit of the bitvector labelings.
(Publisher's web site -- Reinhard Suck's review in J. Math. Psych. -- Reinhard Suck's review in MathSciNet)
\- \!all \!graph:all \!graph:cube \!a:solo \!c:no \!j:no \!y:2008
D. Eppstein.
arXiv:0803.4030.
How to implement an antimatroid, with applications in computerized education.
\- \!all \!geom:all \!graph:all \!gdraw \!a:solo \!c:no \!j:no \!y:2008
D. Eppstein.
Talk at Inst. for Mathematical Behavioral Sciences, May 2008.
Talk at Technical University of Eindhoven, September 2008.
\- \!all \!geom:all \!geom:tri \!graph:all \!graph:sgi \!a:goodrich \!a:kim \!a:tamstorf \!c:other \!j:other \!y:2008 \!y:2009 \# esub to Shape Modeling International SMI'08
D. Eppstein, M. T. Goodrich, E. Kim, and R. Tamstorf.
Proc. IEEE Int. Conf. Shape Modeling and Applications (SMI 2008), Stony Brook, New York, pp. 83-92.
The Visual Computer 25(8): 771-783, 2009.
We formalize problems of finding large approximately-matching regions of two related but not completely isomorphic quadrilateral meshes, show that these problems are NP-complete, and describe a natural greedy heuristic that is guaranteed to find good matches when the mismatching parts of the meshes are small.
(Preprint)
\- \!all \!geom:all \!geom:ss \!geom:tri \!a:goodrich \!a:kim \!a:tamstorf \!c:other \!j:other \!y:2008 \# esub to SoCG08, reject \# esub to Geometry Processing, accept
D. Eppstein, M. T. Goodrich, E. Kim, and R. Tamstorf.
Proc. 6th Symp. Geometry Processing, Copenhagen, Denmark, 2008.
Computer Graphics Forum 27(5):1477-1486, 2008.
We use a construction inspired by the motorcycle graphs previously used in straight skeleton construction, to partition quadrilateral meshes into a small number of structured submeshes. Our construction is canonical in that two copies of the same mesh will always be partitioned in the same way, and can be used to speed up graph isomorphism computations for geometric models in feature animation.
\- \!all \!geom:all \!geom:misc \!geom:ss \!a:barequet \!a:goodrich \!a:vaxman \!c:esa \!j:no \!y:2008 \# esub to SoCG08, reject \# esub to ESA08
G. Barequet, D. Eppstein, M. T. Goodrich, and A. Vaxman.
arXiv:0805.0022.
Proc. 16th European Symp. Algorithms, Karlsruhe, Germany, 2008.
Lecture Notes in Comp. Sci. 5193, 2008, pp. 148-160.
A straight skeleton is defined by the locus of points crossed by the edges and vertices of a polyhedron as it undergoes a continuous shrinking process in which the faces move inwards at constant speed. We resolve some ambiguities in the definition of these shapes, define efficient algorithms for polyhedra with axis-parallel faces, show that arbitrary polyhedra have strictly more complicated straight skeletons, and report on results from an implementation of our algorithm for arbitrary polyhedra.
\- \!all \!graph:all \!geom:all \!geom:hyperbolic \!gdraw \!a:goodrich \!c:gd \!j:sub \!y:2008 \# esub to Graph Drawing 2008 \# sub IEEE Trans Networking, 6 May 2009 \# under title Succinct Greedy Geometric Routing Using Hyperbolic Geometry \# reject/withdraw after referees failed to see the point of the paper \# sub IEEE Trans Comput, 2 Oct 2009
D. Eppstein and M. T. Goodrich.
arXiv:0806.0341.
Proc. 16th Int. Symp. Graph Drawing, Heraklion, Crete, 2008.
Lecture Notes in Computer Science 5417, 2009, pp. 14-25.
Greedy drawing is an idea for encoding network routing tables into the geometric coordinates of an embedding of the network, but most previous work in this area has ignored the space complexity of these encoded tables. We refine a method of R. Kleinberg for embedding arbitrary graphs into the hyperbolic plane, which uses linearly many bits to represent each vertex, and show that only logarithmic bits per point are needed.
\- \!all \!graph:all \!geom:all \!gdraw \!graph:cube \!pure \!a:solo \!c:gd \!j:no \!y:2008 \# esub to Graph Drawing 2008
D. Eppstein.
arXiv:0807.2218.
Proc. 16th Int. Symp. Graph Drawing, Heraklion, Crete, 2008.
Lecture Notes in Computer Science 5417, 2009, pp. 384-389.
We describe polynomial time algorithms for determining whether an undirected graph may be embedded in a distance-preserving way into the hexagonal tiling of the plane, the diamond structure in three dimensions, or analogous structures in higher dimensions. The graphs that may be embedded in this way form an interesting subclass of the partial cubes.
(Slides)
\- \!all \!geom:all \!geom:path \!graph:all \!graph:path \!a:goodrich \!c:other \!j:sub \!y:2008 \# esub to SoCG08, reject \# title was: Linear-Time Algorithms for Voronoi Diagrams, Shortest Paths, \# and Minimum Spanning Trees in Road Networks \# \# esub to ACM GIS \# esub to Networks (with slightly different title) 14 May 2009
D. Eppstein, and M. T. Goodrich.
arXiv:0808.3694.
Proc. 16th ACM SIGSPATIAL Int. Conf. Advances in Geographic Information Systems (ACM GIS 2008), Article 16 (best paper award).
Invited talk at INFORMS 2009, San Diego.
We examine US road network data and show that, contrary to the assumptions of much past GIS work, these networks are highly nonplanar. We introduce a class of "multiscale dispersed" networks that better fit the data; these networks are defined by a family of disks of varying sizes such that, if a small number of outliers is removed, the remaining disks cover each point of the plane a constant number of times. As we show, these networks have good graph separators, allowing for efficient algorithms for minimum spanning trees, graph Voronoi diagrams, and related problems.
\- \!all \!geom:all \!geom:misc \!a:mumford \!c:soda \!j:no \!y:2008 \!y:2009 \# esub to SoCG08, reject \# esub to ESA08, reject \# esub to SODA09
D. Eppstein and E. Mumford.
arXiv:0806.1724.
20th ACM-SIAM Symp. Discrete Algorithms, New York, 2009, pp. 160-169.
We consider problems of determining when a curve in the plane is the projection of a 3d surface with no vertical tangents. Several problems of this type are NP-complete, but can be solved in polynomial time if a casing of the curve is also given.
\- \!all \!geom:all \!geom:path \!graph:all \!graph:path \!a:goodrich \!a:strash \!c:soda \!j:no \!y:2008 \!y:2009 \# esub to SODA09
D. Eppstein, M. T. Goodrich, and D. Strash.
arXiv:0812.0893.
20th ACM-SIAM Symp. Discrete Algorithms, New York, 2009, pp. 150-159.
If a connected graph corresponds to a set of points and line segments in the plane, in such a way that the number of crossing pairs of line segments is sublinear in the size of the graph by an iterated-log factor, then we can find the arrangement of the segments in linear time. It was previously known how to find the arrangement in linear time when the number of crossings is superlinear by an iterated-log factor, so the only remaining open case is when the number of crossings is close to the size of the graph.
\- \!all \!graph:all \!graph:misc \!a:solo \!c:no \!j:jga \!y:2008 \!y:2009 \# esub to JGAA, 1 Jul 2008
D. Eppstein.
arXiv:0807.0007.
J. Graph Algorithms and Applications 13(2):197-204, 2009.
Proves that it's NP-complete to compute the Hadwiger number of a graph.
\- \!all \!geom:all \!geom:misc \!pure \!a:dickerson \!a:wortman \!c:no \!j:no \!y:2008 \# submitted to SoCG, November 2008, rejected \# submitted to SODA, June 2009, rejected
M. Dickerson, D. Eppstein, and K. Wortman.
arXiv:0812.0607.
Investigates Voronoi diagrams for a "smoothed distance" in which the distance between two points p and q is inversely weighted by the perimeter of triangle opq for a fixed point o, its relation to dilation of star networks centered at o, and its generalization to minimization diagrams of certain convex functions. When the function to be minimized is suitably well-behaved, its level sets form pseudocircles, the bisectors of the minimization diagram form pseudoline arrangements, and the diagram itself has linear complexity.
\- \!all \!geom:all \!geom:misc \!graph:all \!graph:cube \!a:mumford \!a:speckmann \!a:verbeek \!c:scg \!c:other \!j:no \!y:2009 \# submitted to SoCG, November 2008 \# also to be submitted to EuroCG
D. Eppstein, E. Mumford, B. Speckmann, and K. Verbeek.
arXiv:0901.3924.
25th Eur. Worksh. Comp. Geom., Brussels, Belgium, 2009.
25th ACM Symp. Comp. Geom., Aarhus, Denmark, 2009, pp. 267-276.
A partition of a rectangle into smaller rectangles is "area-universal" if any vector of areas for the smaller rectangles can be realized by a combinatorially equivalent partition. These partitions may be applied, for instance, to cartograms, stylized maps in which the shapes of countries have been distorted so that their areas represent numeric data about the countries. We characterize area-universal layouts, describe algorithms for finding them, and discuss related problems. The algorithms for constructing area-universal layouts are based on the distributive lattice structure of the set of all layouts of a given dual graph.
\- \!all \!geom:all \!geom:misc \!a:dickerson \!c:scg \!j:no \!y:2009
M. Dickerson and D. Eppstein.
25th ACM Symp. Comp. Geom., Aarhus, Denmark, 2009, video and multimedia track, pp. 92-93.
We investigate distance from a pair of sites defined as the sum of the distances to each site minus a parameter times the distance between the two sites. A given set of n sites defines n(n-1)/2 pairs and n(n-1)/2 distances in this way, from which we can determine a Voronoi diagram. As we show, for a wide range of parameters, the diagram has relatively few regions because the pairs that have nonempty Voronoi regions must be Delaunay edges.
\- \!all \!graph:all \!graph:cube \!pure \!a:cabello \!a:klavzar \!c:no \!j:sub \!y:2009 \# esub to Electronic J. Combinatorics, March 2009
S. Cabello, D. Eppstein, and S. Klavžar.
IMFM Preprint 1084, Institute of Mathematics, Physics and Mechanics, Univ. of of Ljubljana, 2009.
arXiv:0903.2507.
We investigate isometric embeddings of other graphs into Fibonacci cubes, graphs formed from the families of fixed-length bitstrings with no two consecutive ones.
\- \!all \!graph:all \!graph:dyn \!graph:sgi \!a:spiro \!c:wads \!j:no \!y:2009 \# esub to WADS09
D. Eppstein and E. S. Spiro.
arXiv:0904.3741.
Algorithms and Data Structures Symposium (WADS), Banff, Canada.
Lecture Notes in Comp. Sci. 5664, 2009, pp. 278-289.
We define the h-index of a graph to be the maximum h such that the graph has h vertices each of which has degree at least h. We show that the h-index, and a partition of the graph into high and low degree vertices, may be maintained in constant time per update. Based on this technique, we show how to maintain the number of triangles in a dynamic graph in time O(h) per update; this problem is motivated by Markov Chain Monte Caro simulation of the Exponential Random Graph Model used for simulation of social networks. We also prove bounds on the h-index for scale-free graphs and investigate the behavior of the h-index on a corpus of real social networks.
\- \!all \!misc \!a:du \!a:goodrich \!a:lueker \!c:wads \!j:no \!y:2009 \# submitted to KDD08, rejected \# esub to SODA09, rejected \# esub to STACS09, rejected \# esub to WADS09
W. Du, D. Eppstein, M. T. Goodrich, G. Lueker.
arXiv:0904.3756.
Algorithms and Data Structures Symposium (WADS), Banff, Canada.
Lecture Notes in Comp. Sci. 5664, 2009, pp. 242-253.
We investigate several simplified models for k-anonymization in databases, show them to be hard to solve exactly, and provide approximation algorithms for them.
The min-max bin covering problem is closely related to one of our models. An input to this problem consists of a collection of items with sizes and a threshold size. The items must be grouped into bins such that the total size within each bin is at least the threshold, while keeping the maximum bin size as small as possible.
\- \!all \!geom:all \!geom:misc \!graph:all \!graph:cube \!a:mumford \!c:wads \!j:no \!y:2009 \# esub to WADS09
D. Eppstein and E. Mumford.
arXiv:0904.4312.
Algorithms and Data Structures Symposium (WADS), Banff, Canada.
Lecture Notes in Comp. Sci. 5664, 2009, pp. 266-277.
We show how to find a stylized map in which regions have been replaced by rectangles, preserving adjacencies between regions, with constraints on the orientations of adjacencies between regions. For an arbitrary dual graph representing a set of adjacencies, and an arbitrary set of orientation constraints, we can determine whether there exists a rectangular map satisfying those constraints in polynomial time. The algorithm is based on a representation of the set of all layouts for a given dual graph as a distributive lattice, and on Birkhoff's representation theorem for distributive lattices.
\- \!all \!geom:all \!geom:path \!param \!a:wortman \!c:wads \!j:no \!p:oesm \!y:2009 \# esub to SODA09, rejected \# esub to WADS09
D. Eppstein and K. Wortman.
arXiv:0905.0283.
Algorithms and Data Structures Symposium (WADS), Banff, Canada (best paper award).
Lecture Notes in Comp. Sci. 5664, 2009, pp. 290-301.
We provide an O(n3 log2n) algorithm for finding a non-distance-decreasing mapping from a given metric into a star metric with as small a dilation as possible. The main idea is to reduce the problem to one of parametric shortest paths in an auxiliary graph. Specifically, we transform the problem into the parametric negative cycle detection problem: given a graph in which the edge weights are linear functions of a parameter λ, find the minimum value of λ for which the graph contains no negative cycles. We find a new strongly polynomial time algorithm for this problem, and use it to solve the star metric embedding problem.
\- \!all \!graph:all \!graph:cube \!pure \!a:bandelt \!a:chepoi \!c:no \!j:sub \!y:2009 \# submitted to SIAM J. Discrete Mathematics, 27 May 2009
H.-J. Bandelt, V. Chepoi, and D. Eppstein.
arXiv:0905.4537.
Characterizes squaregraphs as duals of triangle-free hyperbolic line arrangements, provides a forbidden subgraph characterization of them, describes an algorithm for finding minimum subsets of vertices that generate the whole graph by medians, and shows that they may be isometrically embedded into Cartesian products of five (but not, in general, fewer than five) trees.
\- \#all \#exponential \#a:solo \#c:no \#j:no \# esub to SODA09, rejected \# not otherwise online, no point in listing in pubs
D. Eppstein.
We find upper and lower bounds on Knuth's dancing links algorithm for solving the exact cover problem, and on a refined version of the algorithm, expanding and improving on a blog post I made in January 2008 in honor of Knuth's 70th birthday.
\- \!all \!geom:all \!geom:misc \!graph:all \!graph:misc \!a:soda \!c:other \!j:no \!y:2009
D. Eppstein.
Invited talk at the 35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2009), Montpellier, France, 2009.
arXiv:0908.3916.
We survey problems in computational geometry that may be solved by constructing an auxiliary graph from the problem and solving a graph-theoretic problem on the auxiliary graph. The problems considered include the art gallery problem, partitioning into rectangles, minimum diameter clustering, bend minimization in cartogram construction, mesh stripification, optimal angular resolution, and metric embedding.
\- \!all \!graph:all \!graph:path \!geom:all \!gdraw \!param \!a:wortman \!c:no \!j:sub \# esub to Graph Drawing 2008, rejected \# accepted with minor changes to JGAA
D. Eppstein and K. Wortman.
arXiv:0907.5474.
We consider drawings of planar partial cubes in which all interior faces are centrally symmetric convex polygons, as in my previous paper Algorithms for Drawing Media. Among all drawings of this type, we show how to find the one with optimal angular resolution. The solution involves a transformation from the problem into the parametric negative cycle detection problem: given a graph in which the edge weights are linear functions of a parameter λ, find the minimum value of λ for which the graph contains no negative cycles.
\- \!all \!geom:all \!geom:misc \!a:gopi \!a:diaz-gutierrez \!c:other \!y:2009 \# esub to SIGGRAPH 2009, rejected \# esub to Pacific Graphics 2009
P. Diaz-Gutierrez, D. Eppstein, and M. Gopi.
17th Pacific Conf. Computer Graphics and Applications, Jeju, Korea, 2009.
Considers heuristic modifications to the tree-cotree decomposition of my earlier paper Dynamic generators of topologically embedded graphs, to make the set of fundamental cycles found as part of the decomposition follow the contours of a given geometric model.
\- \!all \!geom:all \!geom:misc \!graph:all \!graph:misc \!a:goodrich \!a:trott \!c:other \!j:no \!y:2009 \# sub to ACM GIS 2009
D. Eppstein, M. T. Goodrich, and L. Trott.
arXiv:0909.2891.
ACM SIGSPATIAL GIS 2009, Seattle.
Shows both theoretically and experimentally that the number of times a random line crosses a road network is asymptotically upper bounded by the square root of the number of road segments.
\- \!all \!graph:all \!graph:misc \!a:solo \!c:soda \!y:2009 \!y:2010 \# esub to SODA10
D. Eppstein.
arXiv:0909.1870.
21st ACM-SIAM Symp. Discrete Algorithms, Austin, Texas, 2010, to appear.
Considers situations in which two hard approximation problems are presented by means of a single input. In many cases it is possible to guarantee that one or the other problem can be approximated to within a better approximation ratio than is possible for approximating it as a single problem. For instance, it is possible to find either a (1+ε)-approximation to a 1-2 TSP defined from a graph or a nε-approximation to the maximum independent set of the same graph, despite lower bounds showing nonexistence of approximation schemes for 1-2 TSP and nonexistence of approximations better than n1 − ε for independent set. However, for some other pairs of problems, such as hitting set and set cover, we show that solving the paired problem approximately is no easier than solving either problem independently.
\- \!all \!geom:all \!geom:misc \!a:solo \!c:no \!j:no \!p:manhattan2 \!y:2009 \# sub to SODA 2010, rejected
arXiv:0909.1866.
D. Eppstein.
Shows that, when the tight span of a finite metric space is homeomorphic to a subset of the plane, it has the geometry of a Manhattan orbifold and can be constructed in time linear in the size of the input distance matrix. As a consequence, it can be tested in the same time whether a metric space is isometric to a subset of the L1 plane.
\- \!all \!geom:all \!geom:misc \!a:solo \!c:other \!j:no \!y:2009
D. Eppstein.
Invited talk at Fifth William Rowan Hamilton Geometry and Topology Workshop, Dublin, Ireland, 2009.
Invited talk at IPAM Workshop on Combinatorial Geometry, UCLA, 2009.
Surveys hyperconvex metric spaces, tight spans, and my work on Manhattan orbifolds, tight span construction, and optimal embedding into star metrics.
\- \!all \!graph:all \!graph:dyn \!graph:sgi \!a:goodrich \!a:strash \!a:trott \!c:sub \!j:no \# esub to LATIN 2010
D. Eppstein, M. T. Goodrich, D. Strash and L. Trott.
\- \!all \!geom:all \!geom:misc \!a:dickerson \!a:goodrich \!c:no \!j:no \# sub to SODA 2010, rejected
M. Dickerson, D. Eppstein, and M. T. Goodrich.
\- \# finish off list of papers, if keyword was one that included some papers \+ \!top \!geom \!auth \!graph \!subj \!year \!conf \!jour