1993
Note that a paper may appear in listings for multiple years due to multiple publication (of tech. report, conference, and journal versions).- 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.
- Efficient algorithms for sequence analysis.
D. Eppstein, Z. Galil, R. Giancarlo, and G.F. Italiano.
International Advanced Workshop on Sequences, Positano, Italy, 1991.
Sequences II: Methods in Communication, Security, and Computer Science, R.M. Capocelli, A. De Santis, and U. Vaccaro, eds., Springer, 1993, pp. 225–244.
Surveys results on speeding up certain dynamic programs used for sequence comparison and RNA structure prediction.
- 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.
- 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 \(K_3\) or \(K_4\). That is, \(K_3\) and \(K_4\) have linear subgraph multiplicity. This paper shows that the graphs with linear subgraph multiplicity in the planar graphs are exactly the 3-connected planar graphs. Also, the graphs with linear subgraph multiplicity in the outerplanar graphs are exactly the 2-connected outerplanar graphs.
More generally, let \(\mathcal{F}\) be a minor-closed family, and let \(x\) be the smallest number such that some complete bipartite graph \(K_{x,y}\) is a forbidden minor for \(\mathcal{F}\). Then the \(x\)-connected graphs have linear subgraph multiplicity for \(\mathcal{F}\), and there exists an \((x-1)\)-connected graph (namely \(K_{x-1,x-1}\) that does not have linear subgraph multiplicity. When \(x\le 3\) or when \(x=4\) and the minimal forbidden minors for \(\mathcal{F}\) are triangle-free, then the graphs with linear subgraph multiplicity for \(\mathcal{F}\) are exactly the \(x\)-connected graphs.
Please refer only to the journal version, and not the earlier technical report: the technical report had a bug that was repaired in the journal version.
- 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.
Springer, 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.
- 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.
- 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.
- 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\).
- 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".
- 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.
- 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.
(SODA paper – Full paper)
- Dynamic geometric optimization.
D. Eppstein.
Invited talk, 3rd MSI Worksh. Computational Geometry, 1993, p. 14.
- 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".
- 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.
- 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).
- Parallel construction of quadtrees and quality triangulations.
M. Bern, D. Eppstein, and S.-H. Teng.
3rd Worksh. Algorithms and Data Structures, Montreal, 1993.
Springer, Lecture Notes in Comp. Sci. 709, 1993, pp. 188–199.
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.
- 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.