Heya :) I've seen numerous references all over the web that optimal BSP tree creation is an NP-complete problem. That is great, but none of the references that I've browsed through actually make a reference to any specific paper or result that proves this. Can somebody please point me at a paper, article, etc that actually has a discussion on the matter? (I've run into a few references to other articles that state that BSPs are NP-complete, but they don't make any specific mention of where this is proven...) thanks!

I can't prove it for you, but it's simple to see the problem:

Building a bsp tree from a polygon soup involves splitting the set in two halves using one of the polygons as an infinite plane. Technically, you could go one step further and argue that the set should be split in two, using a plane that might be part of the input set, but also might be some other plane. The problem is finding the 'best' plane.

'Best' can be defined in several ways: It could be the plane that results in an equal number of polygons on either side, but you might also add to the equation the total amount of polygons after splitting, as splitting will probably result in more polygons. And then there is balancing.

That's where the NP-completeness comes in: Theoretically, you have to evaluate *each* possible plane, not just for the current level, but all the way down to the termination criterium to evaluate it's 'cost' (which could be defined in terms of balancing and total number of primitives stored in the leaves). Even for a small set of input polygons, this is completely infeasible.

I understand the problem; the issue is that your description just proves that the problem is solved in non-polynomial time, not that it is also NP-complete. At least to my knowledge. :)

Yeah I feared that you would be better at math terminology than I am, so I refrained from analysing the big O, luckily. :)

I looked up 'NP-completeness' on Wikipedia, and found a tidbit on the related 'P and NP classes':

"the class NP consists of all those decision problems whose positive solutions can be verified in polynomial time given the right information."

If I understand this correctly, than the problem with BSP trees is that the parameters for a perfect tree are undefined, i.e. how should the cost of tree balance compare to the cost of splitted polygons. Even worse; the optimal multipliers could be different per tree level. That would indeed make tree construction NP-complete.

Better?

Quote:Original post by LoreKeeper
I understand the problem; the issue is that your description just proves that the problem is solved in non-polynomial time, not that it is also NP-complete. At least to my knowledge. :)

Ah, very interresting. So you want a way to reduce an NP-complete problem to optimal BSP tree creation? I'll have to think about that... My guess is that some of the partitioning algorithms will do the trick. The data in the BSP probably has to be positioned so it is never split (points will probably do).

As for what optimal means, I'd say it's minimal tree depth.

LtJax

yea, the complication of splitting unfortunately has to remain as part of the problem (I think at least).

It isn't that I want to find a way to do it - as (according to online articles) the NP-completeness has already been proven. The problem is that I cannot find a single absolute reference that actually does the proof. :(


phantomus

NP-completeness goes beyond the basic classification of P vs NP - an NP-complete problem is such, that if you can proof that it cannot be solved in P time (or proof that it can be solved in P time) then ALL problems in NP are not (or are) solvable in P time.

Quote:Original post by LoreKeeper
LtJax

yea, the complication of splitting unfortunately has to remain as part of the problem (I think at least).

It isn't that I want to find a way to do it - as (according to online articles) the NP-completeness has already been proven. The problem is that I cannot find a single absolute reference that actually does the proof. :(

nah, you can safely discard complexity (in this case the splitting) if you can still solve other NP-complete problems with it.
but you're right that the proof seems to be kinda hard to find. I've searched for a while now too and come up with nothing. so since that doesn't seem to be all popular and revolutional, I thought we might be able to figure out a proof by ourselves.
I'm pretty sure the path of enlightment only requires to use point BSPs and that the key is that optimal BSPs roughly half their point count each layer..