David Eppstein - Publications

2003

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

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

• 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.
  Springer, Lecture Notes in Comp. Sci. 2125, 2001, pp. 462–470.
  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.415ⁿ), 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.

  (WADS talk slides)

• 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

  (Jeff's pubs page)

• 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, (f₁+f₂)/(f₀+f₃). 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 R³. We show that fatness is not bounded for the more general class of strongly regular CW decompositions of the 3-sphere.

• Algorithms for media.
  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.

  (OSDA talk slides)

• Möbius-invariant natural neighbor interpolation.
  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.

  (SODA talk slides)

• Dynamic generators of topologically embedded graphs.
  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.

  (SODA talk slides)

• Optimized color gamuts for tiled displays.
  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(n³), 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.

  (SCG talk slides)

• Confluent drawings: visualizing non-planar diagrams in a planar way.
  M. Dickerson, D. Eppstein, M. T. Goodrich, and J. Meng.
  arXiv:cs.CG/0212046.
  11th Int. Symp. Graph Drawing, Perugia, Italy, 2003.
  Springer, Lecture Notes in Comp. Sci. 2912, 2004, pp. 1–12.
  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.

• Möbius transformations in scientific computing.
  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.

  (Slides)

• Tiling space and slabs with acute tetrahedra.
  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.

• The traveling salesman problem for cubic graphs.
  D. Eppstein.
  arXiv:cs.DS/0302030.
  8th Worksh. Algorithms and Data Structures, Ottawa, 2003.
  Springer, Lecture Notes in Comp. Sci. 2748, 2003, pp. 307–318.
  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.

  (WADS talk slides)

• Lazy algorithms for dynamic closest pair with arbitrary distance measures.
  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, 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.

• Quasiconvex analysis of backtracking algorithms.
  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".

  (SODA talk slides)

• Depth and arrangements.
  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)

• Quasiconvex programming.
  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)

• Guest editor's forward.
  D. Eppstein.
  Disc. Comp. Geom. 30: 1–2, 2003 (special issue for 17th Symp. Comp. Geom.)
  
• Testing bipartiteness of geometric intersection graphs.
  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.

  (SODA talk slides)

• Deterministic sampling and range counting in geometric data streams.
  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.

• Selected open problems in graph drawing.
  F. J. Brandenburg, D. Eppstein, M. T. Goodrich, S. G. Kobourov, G. Liotta, and P. Mutzel.
  11th Int. Symp. Graph Drawing, Perugia, Italy, 2003.
  Springer, Lecture Notes in Comp. Sci. 2912, 2004, pp. 515–539.

  We survey a number of open problems in theoretical and applied graph drawing.

• Uninscribable four-regular polyhedron.
  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.

• Hyperbolic geometry, Möbius transformations, and geometric optimization.
  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.

• The geometric thickness of low degree graphs.
  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.