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 min...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) algo- rithm 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.展开更多
For some complicated graphs obtained by graph operations,it is very difficult to compute resistance distance and Kirchhoff index.Define a new graph operation,and obtain a class of new join graphs:the subdivision-verte...For some complicated graphs obtained by graph operations,it is very difficult to compute resistance distance and Kirchhoff index.Define a new graph operation,and obtain a class of new join graphs:the subdivision-vertex-vertex join G_1* G_2.Then,describe the Laplacian matrix of the graph G_1 * G_2 and use generalized inverse of the Laplacian matrix to get formulas for resistance distance and Kirchhoff index.Through the obtained formulas,the resistance distance of any pairs of vertices and Kirchhoff index of the join graph can be computed.展开更多
基金Project supported by the National Nature Science Foundation of China (Nos. 60473103 and 60473127) and the Natural Science Foundation of Shandong Province (No. Y2005G03), China
文摘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) algo- rithm 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.
基金National Natural Science Foundation of China(No.11361033)
文摘For some complicated graphs obtained by graph operations,it is very difficult to compute resistance distance and Kirchhoff index.Define a new graph operation,and obtain a class of new join graphs:the subdivision-vertex-vertex join G_1* G_2.Then,describe the Laplacian matrix of the graph G_1 * G_2 and use generalized inverse of the Laplacian matrix to get formulas for resistance distance and Kirchhoff index.Through the obtained formulas,the resistance distance of any pairs of vertices and Kirchhoff index of the join graph can be computed.
