Proceedings of the 14th Annual ACM Symposium on Computational Geometry, 58-67, 1998.
Abstract:
The straight skeleton of a polygon is a variant of the medial axis introduced by Aichholzer et al., defined by a shrinking process in which each edge of the polygon moves inward at a fixed rate. We construct the straight skeleton of an n-gon with r reflex vertices in time O(n^{1+e} + n^{8/11+e}r^{9/11+e}) = O(n^{17/11+e}), for any fixed e>0, improving the previous best upper bound of O(nr log n). Our algorithm simulates the sequence of collisions between edges and vertices during the shrinking process, using a technique of Eppstein for maintaining extrema of binary functions to reduce the problem of finding successive interactions to two dynamic range query problems: (1) maintain a changing set of triangles in R^{3} and answer queries asking which triangle is first hit by a query ray, and (2) maintain a changing set of rays in R^{3} and answer queries asking for the lowest intersection of any ray with a query triangle. We also exploit a novel characterization of the straight skeleton as a lower envelope of triangles in R^{3}. The same time bounds apply to constructing non-self-intersecting offset curves with mitered or beveled corners, and similar methods extend to other problems of simulating collisions and other pairwise interactions among sets of moving objects.
Related work
- Some easy special cases of motorcycle graphs
- David's related research on maintaining closest pairs
- Florence Cloppet, Jean-Michel Oliva, and George Stamon, "Angular bisector network, a simplified generalized Voronoi diagram: Application to processing complex intersections in biomedical images", IEEE PAMI 22(1):120-128, 2000.
- Petr Felkel and Jirí Zara, "The Roof Construction Problem", Proc. CTU Workshop '93 Vol. I: Informatics & Cybernetics, 85-86, 1993. Possibly the earliest correct desription of the straight skeleton?
- Petr Felkel and Stepán Obdrzálek, "Straight skeleton implementation", Proc. 14th Spring Conf. Computer Graphics, 210-218, 1998. This paper describes a straight skeleton algorithm with running time O(n log n + nr), different from the one described in our paper and possibly discovered earlier. C++ source code is available from the authors.
- Jean-Michel Oliva, M. Perrin, Sabine Coquillart, "3d reconstruction of complex polyhedral shapes from contours using a simplified generalized Voronoï diagram", Computer Graphics Forum 15(3):C397-C408, 1996 (Proc. Eurographics '96). Defines the straight skeleton, here called the "angular bisector network", and uses it to reconstruct polyhedra from parallel slices.