A linear-time algorithm was recently published (International Conference Proceedings ofPacific Graphics' 94/CADDM' 94, August 26-29 , 1994 , Beijing , China) for computing the convexhull of a simple polygon. I...A linear-time algorithm was recently published (International Conference Proceedings ofPacific Graphics' 94/CADDM' 94, August 26-29 , 1994 , Beijing , China) for computing the convexhull of a simple polygon. In this note we present a counter-example to that algorithm by exhibiting afamily of polygons for which the algorithm discards vertices that are on the convex hull.展开更多
In this paper,we study the problem,of calculating the minimum collision distance between two planar convex polygons when one of them moves to another along a given direction.First,several novel concepts and properties...In this paper,we study the problem,of calculating the minimum collision distance between two planar convex polygons when one of them moves to another along a given direction.First,several novel concepts and properties are explored,then an optimal algorithm OPFIV with time complexity O(log(n+m))is developed and its correctness and optimization are proved rigorously.展开更多
文摘A linear-time algorithm was recently published (International Conference Proceedings ofPacific Graphics' 94/CADDM' 94, August 26-29 , 1994 , Beijing , China) for computing the convexhull of a simple polygon. In this note we present a counter-example to that algorithm by exhibiting afamily of polygons for which the algorithm discards vertices that are on the convex hull.
文摘In this paper,we study the problem,of calculating the minimum collision distance between two planar convex polygons when one of them moves to another along a given direction.First,several novel concepts and properties are explored,then an optimal algorithm OPFIV with time complexity O(log(n+m))is developed and its correctness and optimization are proved rigorously.
