David Eppstein - Publications

Circles, spheres, and sphere packing

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

  (BibTeX -- Citations -- CiteSeer)

• Faster circle packing with application to nonobtuse triangulation.
  D. Eppstein.
  Tech. Rep. 94-33, ICS, UCI 1994.
  Int. J. Comp. Geom. & Appl. 7(5):485-491, 1997.

  Speeds up a triangulation algorithm of Bern et al. ["Linear-Size Nonobtuse Triangulation of Polygons"] by finding a collection of disjoint circles which connect up the holes in a non-simple polygon. The method is to use a minimum spanning tree to find a collection of overlapping circles, then shrink them one by one to reduce the number of overlaps, using Sleator and Tarjan's dynamic tree data structure to keep track of the connectivity of the shrunken circles.

  (BibTeX -- Citations)

• Faster construction of planar two-centers.
  D. Eppstein.
  Tech. Rep. 96-12, ICS, UCI, 1996.
  8th ACM-SIAM Symp. Discrete Algorithms, New Orleans, 1997, pp. 131-138.

  Improving on a recent breakthrough of Sharir, we use data structures from "Dynamic three-dimensional linear programming" to find two circular disks of minimum radius covering a set of points in the Euclidean plane, in randomized expected time O(n log² n).

  (BibTeX -- SODA paper -- Citations -- DREI and SODA talk slides -- CiteSeer)

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

  (BibTeX -- Citations -- CiteSeer)

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

  (preprint at Erik's web site -- BibTeX -- CiteSeer)

• Tangent spheres and triangle centers.
  D. Eppstein.
  arxiv:math.MG/9909152.
  Amer. Math. Monthly 108(1):63-66, 2001.

  Any four mutually tangent spheres determine three coincident lines through opposite pairs of tangencies. As a consequence, we define two new triangle centers. These centers arose as part of a compass-and-straightedge construction of Soddy circles; also available are some Mathematica calculations of trilinear coordinates for the new triangle centers.

  (BibTeX -- Citations -- CiteSeer)

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

  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.

  (BibTeX -- Citations -- CiteSeer -- WADS talk slides -- ACM DL)

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

  (BibTeX -- Citations)

Geometry -- Publications -- David Eppstein -- Theory Group -- Inf. & Comp. Sci. -- UC Irvine

Semi-automatically filtered from a common source file.