is this possible to do in less than polynomial time?
+4
A:
Use more words.
We can;t know what exactly you are asking. We can only guess.
I don't think spaces could be convex or concave in general... maybe you mean volume or area? In any case I dont think you are going to beat polynomial time, given the complexity of the surface is going to be polynomial in nature.
Karl
2009-06-09 17:54:22
A:
Hmm... interesting question. I believe the answer is yes. Roughly, find the plane equation of each of the faces; for every pair of conjoined faces, if the angle between them is obtuse, the volume is concave. This should run in O(log(n)) time.
I'd bet there's some way of working this out using a graph-coloring algorithm, but I'm just not that clever...
McWafflestix
2009-06-09 17:59:53
Okay, what's with the downvote after this was accepted?
McWafflestix
2009-06-09 18:27:53
How is this O(log(n)) again?you are doing it for each plane..
Yogi
2009-06-10 16:04:34
@Yogi: what? finding the plane equation for each face is O(1); it's O(log(n)) because of comparing pairs of conjoined planes. Remember, finding the plane equation for a polygon is constant time, therefore it's O(1), therefore it doesn't affect the overall order of the algorithm.
McWafflestix
2009-06-10 16:30:39