most recent 30 from http://mathoverflow.net 2013-06-19T07:04:01Z http://mathoverflow.net/feeds/question/24700 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/24700/calculating-the-surface-area-distribution-of-two-dimensional-projections-for-a-po Rob Grey 2010-05-15T06:08:18Z 2010-05-15T11:29:17Z

<p>My question concerns the existence of a nice (deterministic?) method/algorithm for calculating the distribution of surface areas for two-dimensional projections of an arbitrary polytope (or convex approximation of a polytope). Less optimistically, a method of finding the minimum, maximum, and perhaps, mean surface area of the polytope's projections.</p> <p>It is a relatively straightforward procedure to calculate a given two-dimensional surface projection along some orientational vector, and then calculate the approximate surface area of the projection (or its convex hull). But, beyond statistical sampling or methods related to simulated annealing, I'm having trouble imagining how to go about characterizing the full set of projections along all arbitrary vectors... and I haven't had any luck with a literature search (so far).</p> <p>Note - This question is directly related to computations one might like to perform for - <a href="http://mathoverflow.net/questions/24622/characterizing-a-tumbling-convex-polytope-from-the-surface-areas-of-its-two-dimen" rel="nofollow">http://mathoverflow.net/questions/24622/characterizing-a-tumbling-convex-polytope-from-the-surface-areas-of-its-two-dimen</a>. I hope this follow-up post is appropriate...</p>

http://mathoverflow.net/questions/24700/calculating-the-surface-area-distribution-of-two-dimensional-projections-for-a-po/24705#24705 Robby McKilliam 2010-05-15T07:39:45Z 2010-05-15T08:03:15Z

<p>There is a nice paper on a similar topic by <a href="http://www.jstor.org/pss/2974444" rel="nofollow">Burger, Gritzmann and Klee "Polytope projection and projection polytopes"</a> . They describe an $O(n^2)$ algorithm to compute the minimum surface area projection of an n-dimensional simplex. According to the paper it is NP-hard to find the maximum surface area projection of a n-dimensional simplex. </p>

http://mathoverflow.net/questions/24700/calculating-the-surface-area-distribution-of-two-dimensional-projections-for-a-po/24730#24730 Joseph O'Rourke 2010-05-15T11:29:17Z 2010-05-15T11:29:17Z

<p>If you take the arrangement of planes determined by the faces of your polytope, then the combinatorial structure of the projection is constant throughout all the viewpoints within one cell of the arrangement. An alternative viewpoint is to partition <code>$S^2$</code> by these planes moved to the center of that sphere. Within each cell of this arrangement of great circles on <code>$S^2$</code>, the area of the projection changes in a regular, computable manner (as a function of coordinates on <code>$S^2$</code>). None of this would be easy to implement, but it is computable in roughly $O(n^2)$ time for a 3-polytope of $n$ vertices. (Note here I am using $n$ for the number of vertices, and assuming you are working in $R^3$, whereas in Robby McKilliam's posting, $n$ is the dimension).</p> <p>For this arrangements viewpoint, see the paper by Michael McKenna and Raimund Seidel, "Finding the optimal shadows of a convex polytope," <a href="http://portal.acm.org/citation.cfm?id=323237" rel="nofollow">http://portal.acm.org/citation.cfm?id=323237</a> .</p>