Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Metric combinatorics of convex polyhedra: cut loci and nonoverlapping unfoldings
Miller E., Pak I. Discrete & Computational Geometry39 (1):339-388,2008.Type:Article
Date Reviewed: Apr 8 2010

This is a long, complex, and incredibly rich paper. It contains, in some sense, one main result: the source unfolding that unfolds the surface of a convex polyhedron P to a planar, nonoverlapping polygon that generalizes to higher dimensions.

This unfolding is defined with respect to a point x on the polyhedron P. This point determines the cut locus Kx: roughly, the set of all the endpoints of shortest paths emanating from x and covering the surface of P. The idea is that one “cuts” along the network of lines that constitute the cut locus, and the surface unfolds like a flower to the planar polygon , and notably without overlapping itself.

The generalization to higher dimensions starts with a convex polytope P in dimension d, and establishes the analogous result: “cutting” the cut locus Kx for a point x results in a nonoverlapping “polyhedral foldout” in dimension d-1. The cutting is now a higher-dimensional slice. For example, if P is the hypercube in d=4, and x a point in the center of a cubical facet, then the source unfolding is a polyhedron in 3-space with six “spikes” symmetrically surrounding a central cube.

One of the authors’ achievements en route to their main result is precisely defining the cut locus in the higher-dimensional context and establishing its properties. Another achievement is an algorithm for constructing the polyhedral foldout.

The paper closes with a series of observations concerning possible extensions, and a series of conjectures that map out many fascinating lines of research. The authors’ last conjecture--that self-intersection can be avoided during the “blooming” process as well as in the final foldout--has recently been settled affirmatively for three-dimensional polyhedra [1], but remains untouched for d > 3.

Reviewer:  Joseph O’Rourke Review #: CR137898 (1008-0841)
1) Demaine, E.; Demaine, M.; Hart, V.; Iacono, J.; Langerman, S.; O'Rourke, J. Continuous blooming of convex polyhedra. In Abstracts from the 7th Japan Conference on Computational Geometry and Graphs (Kanazawa, Ishikawa, Japan, Nov. 11-13, 2009), JCCGG, 2009, 123–124. http://arxiv.org/abs/0906.2461
Bookmark and Share
  Reviewer Selected
Featured Reviewer
 
 
Curve, Surface, Solid, And Object Representations (I.3.5 ... )
 
 
Combinatorial Algorithms (G.2.1 ... )
 
 
Geometrical Problems And Computations (F.2.2 ... )
 
 
Combinatorics (G.2.1 )
 
 
Nonnumerical Algorithms And Problems (F.2.2 )
 
Would you recommend this review?
yes
no
Other reviews under "Curve, Surface, Solid, And Object Representations": Date
An introduction to the curves and surfaces of computer-aided design
Beach R., Van Nostrand Reinhold Co., New York, NY, 1991. Type: Book (9780442005030)
Apr 1 1992
Tree visualization with tree-maps
Shneiderman B. ACM Transactions on Graphics (TOG) 11(1): 92-99, 1992. Type: Article
Apr 1 1993
Closed smooth piecewise bicubic surfaces
Lee S., Majid A. ACM Transactions on Graphics (TOG) 10(4): 342-365, 1991. Type: Article
Dec 1 1992
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy