Similar articles

Abstract: Computing the distance between two convex polygons is often a basic step to the algorithms of collision detection and path planning. Now, the lowest time complexity algorithm takes O(logm+logn) time to compute the minimum distance between two disjoint convex polygons P and Q, where n and m are the number of the polygons’ edges respectively. This paper discusses the location relations of outer voronoi diagrams of two disjoint convex polygons P and Q, and presents a new O(logm+logn) algorithm to compute the minimum distance between P and Q. The algorithm is simple and easy to implement, and does not need any preprocessing and extra data structures.

[1] Choi, Y.K., Li, X.Q., Rong, F.G., Wang, W.P., Cameron, S., 2006. Computing the Minimum Directional Distance between Two Convex Polyhedra. HKU CS Tech Report TR-2006-01, University Of Hong Kong. Http://www. cs.hku.hk/research/techreps/document/TR-2006-01.pdf.

[2] Cohen, J.D., Lin, M.C., Manocha, D., Ponamgi, M.K., 1995. I-collide: An Interactive and Exact Collision Detection System for Large Scale Environments. Proceedings of ACM International 3D Graphics Conference, ACM Press, New York, 1:189-196.

[3] Dobkin, D., Kirkpatrick, D., 1990. Determining the separation of preprocessed polyhedra—A unified approach. Lecture Notes in Computer Science, 443(ICALP-90):400-413.

[4] Edelsbrunner, H., 1985. Computing the extreme distance between two convex polygons. J. Algorithms, 6(2):213-224.

[5] Guibas, L., Hsu, D., Zhang, L., 2000. A hierarchical method for real-time distance computation among moving convex bodies. Computational Geometry: Theory and Applications, 15(1-3):51-68.

[6] Hudson, T.C., Lin, M.C., Cohen, J.D., Gottschalk, S., Manocha, D., 1997. V-collide: Accelerated Collision Detection for VRML. Proceeding of VRML 1997: Second Symposium on the Virtual Reality Modeling Language. ACM Press, New York, p.119-125.

[7] Li, X.Q., Meng, X.X., Wang, C.Y., Wang, W.P., Chung, K., Yiu, S.M., 2003. Detect collision of polytopes using a heuristic search for separating vectors. Chinese Journal of Computer, 26(7):837-847.

[8] Lin, M.C., Canny, J.F., 1991. A Fast Algorithm for Incremental Distance Calculation. Proceeding of the IEEE International Conference on Robotics and Automation. IEEE Computer Society Press, Sacramento, CA, 2:1008-1014.

[9] Lin, M.C., Manocha, D., Canny, J.F., 1994. Fast Contact Determination in Dynamic Environments. Proceeding of the IEEE International Conference on Robotics and Automation. IEEE Computer Society Press, San Dieg, CA, 1:602-608.

[10] Mirtich, B., 1998. V-clip: fast and robust polyhedral collision detection. ACM Trans. on Graphics, 17(3):177-208.

[11] O’Rourke, J., 1994. Computational Geometry in C. Cambridge University Press, New York, p.260.

[12] Ponamgi, M.K., Manocha, D., Lin, M.C., 1997. Incremental algorithms for collision detection between polygonal models. IEEE Trans. on Visualization and Computer Graphics, 3(1):51-64.