David Eppstein - Publications

2002

• 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(n^c), 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.

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

• 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 R^d 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".

  (SCG paper)

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

  (MSRI talk on streaming video and Slides)

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

  (Cris' MSRI talk on streaming video – Cris' publications page)

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

  (Erik's publications page)

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

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

  (Slides)

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

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

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

• Separating thickness from geometric thickness.
  D. Eppstein.
  arXiv:math.CO/0204252.
  10th Int. Symp. Graph Drawing, Irvine, 2002.
  Springer, Lecture Notes in Comp. Sci. 2528, 2002, pp. 150–161.
  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".

  (GD'02 talk slides)

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

• Reference caching using unit distance redundant codes for activity reduction on address buses.
  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.

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