Straight skeletons
Raising roofs, crashing cycles, and playing pool: applications of a data structure for finding pairwise interactions.
D. Eppstein and J. Erickson.
14th ACM Symp. Comp. Geom., Minneapolis, 1998, pp. 58–67.
Disc. Comp. Geom. 22 (4): 569–592, 1999 (special issue for SCG 1998).We use my dynamic closest pair data structure from "Dynamic Euclidean minimum spanning trees" to detect collisions among a collection of moving objects in sublinear time per collision. As one application, we can construct the straight skeleton of Aichholzer et al (and the mitered offset curves from which it is defined) in subquadratic time.
Motorcycle graphs: canonical quad mesh partitioning.
D. Eppstein, M. T. Goodrich, E. Kim, and R. Tamstorf.
Proc. 6th Symp. Geometry Processing, Copenhagen, Denmark, 2008.
Computer Graphics Forum 27 (5): 1477–1486, 2008.We use a construction inspired by the motorcycle graphs previously used in straight skeleton construction, to partition quadrilateral meshes into a small number of structured submeshes. Our construction is canonical in that two copies of the same mesh will always be partitioned in the same way, and can be used to speed up graph isomorphism computations for geometric models in feature animation.
Straight skeletons of three-dimensional polyhedra.
G. Barequet, D. Eppstein, M. T. Goodrich, and A. Vaxman.
arXiv:0805.0022.
Proc. 16th European Symp. Algorithms, Karlsruhe, Germany, 2008.
Springer, Lecture Notes in Comp. Sci. 5193, 2008, pp. 148–160.A straight skeleton is defined by the locus of points crossed by the edges and vertices of a polyhedron as it undergoes a continuous shrinking process in which the faces move inwards at constant speed. We resolve some ambiguities in the definition of these shapes, define efficient algorithms for polyhedra with axis-parallel faces, show that arbitrary polyhedra have strictly more complicated straight skeletons, and report on results from an implementation of our algorithm for arbitrary polyhedra.