统一确定两凸多边形支撑线的快速算法

• 作者: 刘金义 程小茁
• 来源期刊: 工程图学学报
• 学科: 工学
• 关键词: 凸多边形 支撑线 凸壳 可移动方向
• 年，卷（期）: 2000,（2）
• 所属期刊栏目: 计算机几何
• 页码范围: 52-58
• 页数: 7页
• 分类号: TP3
• 字数: 6070字
• 语种: 中文
• DOI: 10.3969/j.issn.1003-0158.2000.02.009

摘要

设P与Q为平面上两个互不相交的凸多边形,则在P与Q之间必存在两条正支撑线和两条斜支撑线,确定它们就可以确定P与Q的凸壳和P与Q的全部可移动方向,这在机器人学、几何布局及VLSI设计等领域具有重要实用意义.本文给出统一确定这些支撑线的快速算法,其时间复杂度为O(logm· logn) ,其中m与n分别为P与Q的顶点数.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘金义	抚顺石油学院计算机科学与技术系	9	113	6.0	9.0
2	程小茁	抚顺石油学院计算机科学与技术系	5	56	4.0	5.0