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

Springer,*Lecture Notes in Comp. Sci.*6506, 2010, p. 1.

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.

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

*Comp. Geom. Theory & Applications*49: 8–16, 2015 (special issue for CCCG 2012).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.

(Slides)

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

HAL-Inria open archive oai:hal.inria.fr:hal-00846953.

*25th Canadian Conference on Computational Geometry*, Waterloo, Canada, 2013.

*J. Graph Algorithms and Applications*18 (3): 313–324, 2014.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.(Slides)

**Folding polyominoes into (poly)cubes**.

O. Aichholzer, M. Biro, E. Demaine, M. Demaine, D. Eppstein, S. P. Fekete, A. Hesterberg, I. Kostitsyna, and C. Schmidt.

*27th Canadian Conference on Computational Geometry*, Kingston, Ontario, Canada, 2015, pp. 101–106.

arXiv:1712.09317.

*Int. J. Comp. Geom. & Appl.*, to appear.We classify the polyominoes that can be folded to form the surface of a cube or polycube, in multiple different folding models that incorporate the type of fold (mountain or valley), the location of a fold (edges of the polycube only, or elsewhere such as along diagonals), and whether the folded polyomino is allowed to pass through the interior of the polycube or must stay on its surface.

**Maximizing the sum of radii of disjoint balls or disks**.

D. Eppstein.

arXiv:1607.02184.

*Proc. 28th Canadian Conference on Computational Geometry*, Vancouver, BC, Canada, 2016, pp. 260–265.

*J. Computational Geometry*8 (1): 316–339, 2017.

We show how to find a system of disjoint balls with given centers, maximizing the sum of radius of the balls. Our algorithm takes cubic time in arbitrary metric spaces and can be sped up to subquadratic time in Euclidean spaces of any bounded dimension.

(Slides)

**Forbidden configurations in discrete geometry**.

D. Eppstein.

Paul Erdős Memorial Lecture, 29th Canadian Conference on Computational Geometry, Ottawa, Canada, 2017.

Invited talk, 20th Japan Conference on Discrete and Computational Geometry, Graphs, and Games, Tokyo, 2017.

Invited talk, 5th International Combinatorics Conference, Melbourne, Australia, 2017.

Cambridge University Press, 2018.We survey problems on finite sets of points in the Euclidean plane that are monotone under removal of points and depend only on the order-type of the points, and the subsets of points (forbidden configurations) that prevent a point set from having a given monotone property.

(CCCG talk slides – CCCG talk video)

**Geometric fingerprint matching via oriented point-set pattern matching**.

D. Eppstein, M. T. Goodrich, J. Jorgensen, and M. Torres.

*Proc. 30th Canadian Conference on Computational Geometry*, Winnepeg, Canada, 2018, to appear.

When matching fingerprints, the data involves planar points each of which has an associated direction. Motivated by this application, we consider point matching problems in which the distance between points combines both their translational distance and the rotation needed to make their directions align. We provide fast and simple approximation schemes for matching oriented point sets under the directed Hausdorff distance with different allowed groups of transformations.

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

Semi-automatically filtered from a common source file.