RE: [Algorithms] exploiting convexity in minkowski sum edge vs ed g ecase

[Jonathan H. <jhe...@cs...>]

> > I think this method is interesting, but it only tells you 
> if P and Q are
> > touching or not.  Beyond that, it says very little.  The 
> authors mention
> > that alpha is the separation or penetration distance along 
> the line c-o.
> > But the line c-o is completely arbitrary.  It is not the least 
> penetration
> > or nearest distance vector, which is what you'd really like to get.
> 
> But even if its not, you have found the optimal face using 
> hill climbing 
> so
> all you have to do is find the distance of the non-dual image 
> of the face
> to the origin to get the minimum directed distance, no?

I don't think so.  The "optimal face" is simply the face pierced by the ray
c->o.  If o is inside M, clearly any face could be "optimal" depending on
what you choose for c.  In other words, if two convex are overlapping there
are any number of ways you can pull them apart to remove the overlap (but
some are longer than others).  And if o is outside M, there may be several
faces on M facing o that can be optimal, depending on the choice of c.
Thus, you will get a positive separation, but not necessarily the nearest
separating distance.  To see what I mean, just draw an octahedron for M and
pick o and c different places.

jh