Math @ Duke

Publications [#243931] of Ezra Miller
Papers Published
 with Miller, E; Pak, I, Metric combinatorics of convex polyhedra: Cut loci and nonoverlapping unfoldings,
Discrete & Computational Geometry, vol. 39 no. 13
(2008),
pp. 339388, ISSN 01795376 [MR2008m:52027], [math.MG/0312253], [doi]
(last updated on 2018/07/23)
Abstract: Let S be the boundary of a convex polytope of dimension d+1, or more generally let S be a convex polyhedral pseudomanifold. We prove that S has a polyhedral nonoverlapping unfolding into ℝd, so the metric space S is obtained from a closed (usually nonconvex) polyhedral ball in ℝd by identifying pairs of boundary faces isometrically. Our existence proof exploits geodesic flow away from a source point v S, which is the exponential map to S from the tangent space at v. We characterize the cut locus (the closure of the set of points in S with more than one shortest path to v) as a polyhedral complex in terms of Voronoi diagrams on facets. Analyzing infinitesimal expansion of the wavefront consisting of points at constant distance from v on S produces an algorithmic method for constructing Voronoi diagrams in each facet, and hence the unfolding of S. The algorithm, for which we provide pseudocode, solves the discrete geodesic problem. Its main construction generalizes the source unfolding for boundaries of threepolytopes into ℝ2. We present conjectures concerning the number of shortest paths on the boundaries of convex polyhedra, and concerning continuous unfolding of convex polyhedra. We also comment on the intrinsic nonpolynomial complexity of nonconvex manifolds. © 2008 Springer Science+Business Media, LLC.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

