Quote: Original post by Christer Ericson
Anyone who can read can easily verify that the well-known Lin-Canny paper from 1991 (A Fast Algorithm for Incremental Distance Calculation) describes Voronoi feature walking and predates the Mirtich V-Clip report from 1997 by six years. Thus _clearly_ the approach did not originate with Mirtich.
Yes you are right there, John Canny first distance walking was brilliant, but unfortunately it only had theoretical value and not practical application, as it was extremely numerical unstable, and required too many tolerances to be tuned. Since then he has being refining it and with every each new student he mentor a new variant has been publicized. The difference is that each new variance comes with a real mathematical improvement that allow for some more rigorous application.
Ming C was a student of John Canny, and so was Mirty, that’s why I said his method has roots in Canny closest distance method, and so are all of the other variance of the same method. But the Voronoi distance walk was a new idea that goes to Mirty, and that is a fact.
As it stand now there are only two practical way to calculate distance on convex objects, Closest feature walk, and Minkousky difference, and there are many new variance that exploit one or other property of the principle.
All of then are written, well documenrted and they are of public knowledge. There is not evidence that any variance is better than other, the only evidence of that is the decoration the implementer gives to his/her approach of the moment in his dissertation or publication.
In my time algorithms were measured by time complexity, and numerical robustness not by measuring if you implemented a methid with two dot products and somebody else did it with three products, which seems to be the standard now. Implementation details had never been a factor is determining algorithm uniqueness and robustness.
