David Eppstein - Publications

Canadian Conf. Computational Geometry (CCCG)

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

  (BibTeX -- Erik's publication page -- CiteSeer -- ACM DL)

• Hinged dissections of polyominos and polyforms.
  E. Demaine, M. Demaine, D. Eppstein, G. Frederickson, and E. Friedman.
  arXiv:cs.CG/9907018.
  11th Canad. Conf. Comp. Geom., 1999.
  Computational Geometry: Theory and Applications 31(3):237-262, 2005 (special issue for 11th CCCG).

  We show that, for any n, there exists a mechanism formed by connecting polygons with hinges that can be folded into all possible n-ominos. Similar results hold as well for n-iamonds, n-hexes, and n-abolos.

  (BibTeX -- Erik's CCCG publication page -- Erik's CGTA publication page -- Citations)

• Regular labelings and geometric structures.
  D. Eppstein.
  arXiv:1007.0221.
  Invited to 22nd Canadian Conference on Computational Geometry (CCCG 2010).
  Invited to Proc. 21st International Symposium on Algorithms and Computation (ISAAC 2010), Jeju, Korea, 2010.
  Lecture Notes in Comp. Sci. 6506, 2010, p. 1, Springer-Verlag.
  

  We survey regular labelings for straight-line embedding of planar graphs on grids, rectangular partitions, and orthogonal polyhedra, and the many similarities between these different types of labeling.

  (CCCG talk slides)

• Near-linear-time deterministic plane Steiner spanners and TSP approximation for well-spaced point sets.
  G. Borradaile and D. Eppstein.
  arXiv:1206.2254.
  24th Canadian Conference on Computational Geometry (CCCG 2012), Prince Edward Island, Canada, 2012, pp. 311-316.

  When a planar point set has the property that its Delaunay triangulation has no large angles, we show how to connect it by a plane graph (having linearly many additional Steiner vertices) in which the distances between the original points are approximations to their Euclidean distance, and in which the total graph weight is at most a constant times the minimum spanning tree weight. The time to construct this graph is near-linear, the same as for integer sorting. We use this result to approximate the traveling salesman problem, for these point sets, in the same time bound.

• Set-difference range queries.
  D. Eppstein, M. T. Goodrich, and J. Simons.
  arXiv:1306.3482.
  25th Canadian Conference on Computational Geometry, Waterloo, Canada, 2013.

  We show how to use invertible Bloom filters as part of range searching data structures that determine the differences between the members of two sets that lie in a given query range.

• Universal point sets for planar graph drawings with circular arcs.
  P. Angelini, D. Eppstein, F. Frati, M. Kaufmann, S. Lazard, T. Mchedlidze, M. Teillaud, and A. Wolff.
  25th Canadian Conference on Computational Geometry, Waterloo, Canada, 2013.

  For every positive integer n, there exists a set of n points on a parabola, with the property that every n-vertex planar graph can be drawn without crossings with its vertices at these points and with its edges drawn as circular arcs.

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

Semi-automatically filtered from a common source file.