| Title: | 在二、三维空间中求两凸几何体间距离的算法 |
| Author: | 陈亮
|
| Issued Date: | 1994
|
| Major: | 计算机科学理论
|
| Degree Grantor: | 中国科学院软件研究所
|
| Place of Degree Grantor: | 中国科学院软件研究所
|
| Degree Level: | 博士
|
| Abstract: | 本文主要研究工作分为两部分：1）研究平面上两已知互不相交的凸几何体间的距离的计算。为求平面上的直线和凸多边形、线段和凸多边形的距离及一近点对找到了O(logn)(n为凸多边形顶点数)时间复杂度的快速算法；为求平面上两凸多边形间的距离及一近点对找到了O(logN)(N为两凸多边形顶点总数)时间复杂度的快速算法。2）研究三维空间中两已知不相交的凸几何体间的距离的计算。为在空间中求直线和凸多边形、线段和凸多边形、平面和凸多边形间的距离及一近点对找到了O(logn)(n为凸多边形顶点数)时间复杂度的快速算法，为求空间中两个凸多边形间的距离及一近点对找到了O(logN)(N为两凸多边形顶点数)时间复杂度的快速算法。 |
| English 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). |
| Language: | 中文
|
| Content Type: | 学位论文
|
| URI: | http://ir.iscas.ac.cn/handle/311060/6288
|
| Appears in Collections: | 中科院软件所
|
| File Name/ File Size |
Content Type |
Version |
Access |
License |
|
|---|
| N90448.pdf（4230KB） | -- | -- | 限制开放 | -- | 联系获取全文 |
|
| Recommended Citation: | |
陈亮. 在二、三维空间中求两凸几何体间距离的算法[D]. 中国科学院软件研究所. 中国科学院软件研究所. 1994-01-01.
|
|
|
