| A new fast algorithm for computing the distance between two disjoint convex polygons based on Voronoi diagram |
| |
| 作者姓名： | YANG Cheng-lei QI Meng MENG Xiang-xu LI Xue-qing WANG Jia-ye |
| |
| 作者单位： | School of Computer Science and Technology，Shandong University，Jinan 250100，China |
| |
| 基金项目： | 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 |
| |
| 摘 要： | INTRODUCTION To compute the minimum distance between two convex polygons or polyhedrons is often a main step of many applications, such as collision detection (Choi et al., 2006; Li et al., 2003), path planning. In order to reduce the time complexity of the algorithm as much as possible, the convex property must be applied fully. Edelsbrunner (1985) proposed an algorithm for computing the minimum distance between two dis- joint convex polygons. The algorithm takes O(logm logn) time, and …
|
| 关 键 词： | 计算几何 多边形 沃罗诺框图 距离估计 快速算法 |
| 收稿时间： | 2005-05-20 |
| 修稿时间： | 2006-06-21 |
A new fast algorithm for computing the distance between two disjoint convex polygons based on Voronoi diagram |
| |
| YANG Cheng-lei QI Meng MENG Xiang-xu LI Xue-qing WANG Jia-ye.A new fast algorithm for computing the distance between two disjoint convex polygons based on Voronoi diagram[J].Journal of Zhejiang University Science,2006,7(9):1522-1529. |
| |
| Authors: | Cheng-lei Yang Meng Qi Xiang-xu Meng Xue-qing Li Jia-ye Wang |
| |
| Institution: | (1) School of Computer Science and Technology, Shandong University, Jinan, 250100, China |
| |
| 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.
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 |
| |
| Keywords: | Computational geometry Polygon Voronoi diagram Distance computation |
| 本文献已被 CNKI 维普 万方数据 SpringerLink 等数据库收录！ |
