| 求平面点集独立线段的一个联机算法 |
| |
| 引用本文： | 徐寅峰 陈丽华. 求平面点集独立线段的一个联机算法[J]. 工程数学学报, 1995, 12(4): 99-102 |
| |
| 作者姓名： | 徐寅峰 陈丽华 |
| |
| 作者单位： | 西安交通大学管理学院，北京科技大学 |
| |
| 摘 要： | ![]()
令Ｓ为一个有限平面点集合，线段Ｌ（ｐ，ｑ），ｐ，ｑ∈Ｓ称为Ｓ的一个独立线段当且仅当不存在两个端点在Ｓ中的线段与Ｌ（ｐ，ｑ）相交。本文给出了时间复杂度为Ｏ（ｎ＾２ｌｏｇｎ）和修正时间复杂度为Ｏ（ｎｌｏｇｎ）的联机算法。这一算法与已知的脱算法具有相同的时间复杂度。
|
| 关 键 词： | 平面点集 独立线段 联机算法 时间复杂度 |
An On-line Algorithm for Finding Stable Line Segments of a Planar Point Set |
| |
| Xu Yinfeng. An On-line Algorithm for Finding Stable Line Segments of a Planar Point Set[J]. Chinese Journal of Engineering Mathematics, 1995, 12(4): 99-102 |
| |
| Authors: | Xu Yinfeng |
| |
| Abstract: | ![]()
|
| |
| Keywords: | on-line algorithm stable line segment convex hull |
| 本文献已被 CNKI 维普 等数据库收录！ |
