David Eppstein - Publications

Publications with Marshall Bern

• 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\alpha(n,k))\). The first bound is tight, but it remains open whether the second is, or whether only linear complexity is possible.

• The expected extremes in a Delaunay triangulation.
  M. Bern, D. Eppstein, and F. Yao.
  18th Int. Coll. Automata, Languages and Programming, Madrid, Spain, 1991.
  Springer, 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 \(O(\log n / \log\log n)\).

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

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

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

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

  In this paper, we construct triangulations of point sets and polygons by using quadtrees to add extra vertices to the input. As a result we can guarantee that all triangles have angles bounded away from zero, using a number of triangles within a constant of optimal; this was the first paper to provide simultaneous bounds on mesh element quality and mesh complexity of this form, and therefore the first to provide finite element mesh generation algorithms that guarantee both the robustness of the algorithm against unexpected input geometries and the quality of its output.

  In the same paper we also use quadtrees to triangulate planar point sets so that all angles are non-obtuse, using linearly many triangles, and to triangulate higher dimensional point sets with no small solid angles and a number of simplices within a constant of optimal. Also, we can augment any higher dimensional point set so the Delaunay triangulation has linear complexity.

  In later follow-up work, I showed that the same technique can also be used to find a triangulation whose edges have total length within a constant factor of optimal. Bern, Mitchell, and Ruppert showed that alternative methods can be used to triangulate any polygon without obtuse angles; see "Faster circle packing with application to nonobtuse triangulation" for an algorithmic improvement to their technique. Additionally, with Bern, Chew, and Ruppert, we showed that any point set in higher dimensions can be triangulated with nonobtuse simplices. Bern and I surveyed these and related results in our paper "Mesh generation and optimal triangulation".

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

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

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

  (Preprint of SCG version)

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

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

  (SODA paper)

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

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

• Application Challenges to Computational Geometry.
  The Computational Geometry Impact Task Force 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.
  
• 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 R^d from which a d-1 dimensional convex set subtends a given solid angle is convex.

  (SODA paper)

• The crust and the beta-skeleton: combinatorial curve reconstruction.
  N. Amenta, M. Bern, and D. Eppstein.
  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. There have been many follow-up papers suggesting alternative methods, generalizing the problem to the reconstruction of curves with sharp corners or to curves and surfaces in higher dimensions, etc.

  (Preprint version)

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

  1. The elements form the cells of a Voronoi diagram,
  2. The elements each have two opposite 90 degree angles,
  3. All elements are kites, or
  4. All angles are at most 120 degrees.

  In each case the total number of elements is \(O(n)\). The 120-degree bound is optimal; if a simply-connected region has all angles at least 120 degrees, any mesh of that region has a 120 degree angle.

  

• 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.
  Origami³: 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.

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

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

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

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

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

• 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(n^d-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)

• 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.
  Springer, Lecture Notes in Comp. Sci. 2125, 2001, pp. 14–25.

  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.

  (WADS talk slides)

• 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.
  Springer, Lecture Notes in Comp. Sci. 2125, 2001, pp. 111–121.

  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.

  (WADS talk slides)

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

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

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