6
$\begingroup$

Does anyone know a way to do a quick sort with trivalued logic?

The problem I’m trying to solve is this: I’m trying to display a view of a complex 3d object from a given viewing angle. I’ve broken the object into many 2d surfaces that I can draw separately, but to display the image properly, I need to determine the z-order of the surfaces – a classic computer drawing problem. It’s guaranteed that none of the surfaces intersect, so the problem is solvable. It would be simple if on comparing any two surfaces, I could always determine which one is in front – then a simple mergesort would suffice. But very often, if I compare two surfaces, it’ll turn out that, with the angle I’m viewing from, there’s no overlap at all. One surface is over here, and the other surface is over there, so it’s impossible to say which one is in front.

In mathematical terms, what I’m trying to do is sort a set of entities - call them a, b, c, etc. Transitivity is guaranteed: If a < b is true and b< c is true then a < c is always true. But the complicating factor is the trivalued logic: a < b could be unknown. A consequence is the final sorted list may contain small sets of elements within which the order doesn’t matter, eg. The result may be a < (b, c) < d etc.

Note that even if a < b is unknown, other comparisons may indirectly force a certain ordering for a, b. Eg. If a < b is unknown, but it turns out that a < c = true and b < c is false, then the sorted order must be a < c < b.

I can solve the problem with a bubble sort, but that’s bad because O(N^2) comparisons, and each comparison is very expensive (since it involves figuring out whether two surfaces can block each other when viewed from a certain angle). Is there a way to solve this with a faster sort? (eg. Some adaptation of a mergesort)?

  • 0
    If you drop $c$onvexity, then in addition to the problem in leif's link you face the possibility of two U-shaped objects partially occluding each other.2011-06-29

2 Answers 2

3

What you have is not really a trivalued logic, but a partially ordered set (aka poset). There is a fairly large body of research on sorting partially ordered sets (a quick googling for "poset sorting" gives some good hits). In particular, you may want to look for something called a "chain merge data structure". Also, a paper called "Sorting and Selection in Posets".

  • 0
    Thanks aubrey, I found the paper you meant, at [link](http://ar$x$iv.org/PS_cache/arxiv/pdf/0707/0707.1532v1.pdf), and it does exactl$y$ answer my question, although it looks like the answer is so complex that I may just stick with a simple variant of bubble sort for now. Googling for poset also, interestingly, gave me this question on stack overflow: [link](http://stackoverflow.com/questions/4600258/sorting-a-poset) which asked the exact same question I asked, except that in that case the questioner knew the correct terminology so could make his question much shorter :)2011-03-20
-1

Though your surfaces are sometimes incomparable (this is the third value in you hoped for trivalent logic), I think it is not necessary to worry about it here. If for two surfaces, neither is in front of the other for the given viewpoint, then you can draw either one before the other, it doesn't matter. So when you sort your surfaces you can just arbitrarily pick one (or the other) to be drawn before the other and it won't mess up the drawing.

  • 0
    @joriki: Argh...yes. Then when you can't compare everything directly (the comparison relation is not total), then yes, use 'topological sort' on the poset of comparisons that you do have.2011-03-20