**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.**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.(Also available in HTML and Mathematica notebook formats)

**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.**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".

**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.

**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.

**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(*n*^{ceil(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.**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, "Diameter and treewidth in minor-closed graph families", 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.

**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.**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.

Springer,*Lecture Notes in Comp. Sci.*979, 1995, pp. 460–472.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)

**3-Coloring in time O(1.3446**.^{n}): 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.

(DIMACS abstract and slides)

**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.

**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.**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.**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. 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. Also discusses similar equivalent graph constructions for shortest paths, minimum cost flows, and bipartite matching.

**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.

**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".**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.

Years – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine

Semi-automatically filtered from a common source file.