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