首页 | 本学科首页   官方微博 | 高级检索  
     

求平面点集独立线段的一个联机算法
引用本文:徐寅峰,陈丽华.求平面点集独立线段的一个联机算法[J].工程数学学报,1995,12(4):99-102.
作者姓名:徐寅峰  陈丽华
作者单位:西安交通大学管理学院,北京科技大学
摘    要:令S为一个有限平面点集合,线段L(p,q),p,q∈S称为S的一个独立线段当且仅当不存在两个端点在S中的线段与L(p,q)相交。本文给出了时间复杂度为O(n^2logn)和修正时间复杂度为O(nlogn)的联机算法。这一算法与已知的脱算法具有相同的时间复杂度。

关 键 词:平面点集  独立线段  联机算法  时间复杂度

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 维普 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号