> "pan" <pan### [at] syixcom> wrote:
>> Question: I had doubts about nodes|edges not intersecting
>> via this method so I wrapped the object file with intersection { }.
>> Since nothing rendered I assume this means there are no
>> intersections of objects.
>> Is this a fair assumption?
> 
> Actually, no, if you're talking about PAIRWISE intersections.  This
> woud just show that there's no point in the intersection of all the
> objects. 
> 
> That is, if A = {1,2}, B = {2,3} and C = {3,4},
> intersection {object{A} object{B} object{C} } would be empty.
> 
> Dave Matthews

Good remark!
Your wrapping would in fact have taken advantage of my interunion
patch... 

Now, the question from a mathematical point-of-view is:
 In a 2D plane, is there a configuration of vertex so that it is
 possible for the tree to cross itself. 

I would say that it is, alas, possible, if the distance between the
vertex are not proportional to the cost of the link/edge. 

If the cost of the link is proportionnal to the distance between the
ends of it, you could demonstrate that a ST crossing itself is not a
MST. (because, by replacing 2 long link with 2 smaller not crossing, you
have a gain toward the MST). Therefore, A MST on such condition would
not cross itself. 

Now, let's figure distance is not proportional to link cost. You got a
problem... 

A <0,0>
B <1,0>
C <1,1>
D <0,1>

Cost matrix (symetry implied, I will let you deal with non-symetric cost
another time...): 
 AB: 1000
 AC: 1
 AD: 1000
 BC: 1
 BD: 1
 CD: 1000

The MST is ACBD (or whatever you order them along that path).
But AC and BD are crossing!

Have a nice week-end!
-- 




l'habillement, les chaussures que le maquillage et les accessoires.

Post a reply to this message