| 在二、三维空间中求两凸几何体间距离的算法 |
| 陈亮
|
| 专业 | 计算机科学理论
|
| 1994
|
| 学位授予单位 | 中国科学院软件研究所
|
| 学位 | 博士
|
| 学位授予地点 | 中国科学院软件研究所
|
| 摘要 | 本文主要研究工作分为两部分：1）研究平面上两已知互不相交的凸几何体间的距离的计算。为求平面上的直线和凸多边形、线段和凸多边形的距离及一近点对找到了O(logn)(n为凸多边形顶点数)时间复杂度的快速算法；为求平面上两凸多边形间的距离及一近点对找到了O(logN)(N为两凸多边形顶点总数)时间复杂度的快速算法。2）研究三维空间中两已知不相交的凸几何体间的距离的计算。为在空间中求直线和凸多边形、线段和凸多边形、平面和凸多边形间的距离及一近点对找到了O(logn)(n为凸多边形顶点数)时间复杂度的快速算法，为求空间中两个凸多边形间的距离及一近点对找到了O(logN)(N为两凸多边形顶点数)时间复杂度的快速算法。 |
| 其他摘要 | The main research work presented can be divided into two parts. The first part contains the study on the computing of planar distances. Fast algorithms for computing the distances between a convex polygon and a line, a convex polygon and a line, a convex polygon and a line segment are given. Both of them run in time O(logn), where n is the number of the vertices in the polygon considered. A fast algorithm for computing the distance between two convex polygons, in which the total number of vextices is N, is also given. Its time complexity bounds is O(logN). The second part investigates the problem cast in three-dimensions. The algorithms for computing the distances between a convex polygon and a line, a convex polygon and a lien segment, a convex polygon and a plane, two convex polygons in three dimensional space separately are described. The last algorithm runs in time O(logN), (where N denotes the total number of vertices in both poiygons), while each of the first three in O(logn) (where n is the number of vertices in the polygon considered). |
| 页数 | 92
|
| 语种 | 中文
|
| 内容类型 | 学位论文
|
| URI标识 | http://ir.iscas.ac.cn/handle/311060/6288
|
| 专题 | 中科院软件所_中科院软件所
|
推荐引用方式
GB/T 7714 |
陈亮. 在二、三维空间中求两凸几何体间距离的算法[D]. 中国科学院软件研究所. 中国科学院软件研究所,1994.
|
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。
修改评论