Institutional Repository
| 在二、三维空间中求两凸几何体间距离的算法 | |
| 陈亮 | |
| Major | 计算机科学理论 |
| 1994 | |
| Degree Grantor | 中国科学院软件研究所 |
| Degree Level | 博士 |
| Place of Degree Grantor | 中国科学院软件研究所 |
| English Abstract | 本文主要研究工作分为两部分：1）研究平面上两已知互不相交的凸几何体间的距离的计算。为求平面上的直线和凸多边形、线段和凸多边形的距离及一近点对找到了O(logn)(n为凸多边形顶点数)时间复杂度的快速算法；为求平面上两凸多边形间的距离及一近点对找到了O(logN)(N为两凸多边形顶点总数)时间复杂度的快速算法。2）研究三维空间中两已知不相交的凸几何体间的距离的计算。为在空间中求直线和凸多边形、线段和凸多边形、平面和凸多边形间的距离及一近点对找到了O(logn)(n为凸多边形顶点数)时间复杂度的快速算法，为求空间中两个凸多边形间的距离及一近点对找到了O(logN)(N为两凸多边形顶点数)时间复杂度的快速算法。 |
| Abstract | 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). |
| Pages | 92 |
| Language | 中文 |
| Content Type | 学位论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/6288 |
| Collection | 中科院软件所_中科院软件所 |
| Recommended Citation GB/T 7714 | 陈亮. 在二、三维空间中求两凸几何体间距离的算法[D]. 中国科学院软件研究所. 中国科学院软件研究所,1994. |
| Files in This Item: | ||||||
| File Name/Size | DocType | Version | Access | License | ||
| N90448.pdf（4230KB） | 限制开放 | -- | Application Full Text | |||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment