1
$\begingroup$

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.

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).

Note - This question is directly related to computations one might like to perform for - Characterizing a tumbling convex polytope from the surface areas of its two-dimensional projections. I hope this follow-up post is appropriate...

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

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 $S^2$ by these planes moved to the center of that sphere. Within each cell of this arrangement of great circles on $S^2$, the area of the projection changes in a regular, computable manner (as a function of coordinates on $S^2$). 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).

For this arrangements viewpoint, see the paper by Michael McKenna and Raimund Seidel, "Finding the optimal shadows of a convex polytope," http://portal.acm.org/citation.cfm?id=323237 .

Improve this answer
$\endgroup$
1
$\begingroup$

There is a nice paper on a similar topic by Burger, Gritzmann and Klee "Polytope projection and projection polytopes" . 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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .