求平面内两互不相交的凸多边形的内公切线的最优算法  

AN OPTIMAL ALGORITHM TO FIND INTERNALLY COMMON TANGENTS OF TWO CONVEX POLYGONS

作　　者：覃中平[1] 张焕国[2] 

机构地区：[1]华中理工大学数学系,武汉430074 [2]武汉大学计算机科学系,武汉430072

出　　处：《计算机学报》1991年第11期851-857,共7页Chinese Journal of Computers

摘　　要：设P与Q为平面内两个互不相交的分别具有m与n个顶点的凸多边形,它们的顶点用直角坐标描述并且沿其边界按顺时针方向依次列出.本文给出求P与Q的内公切线(或称斜支撑线)的时间复杂度为O(logm+logn)的最优算法,从而突破了李辉关于解决同一问题的时间复杂度为O(m+n)的算法是最优的论断.Let P and Q denote two convex polygons. The computational complexity of finding the internally common tangents of P and Q is studied. An algorithm is described that determines the internally common tangents of P and Q in O(logm+logn} time, where m and n denote the number of vertices of P and Q, respectively. This is optimal in the worst case.

关 键 词：凸多边形 内公切线 计算几何 算法 

分 类 号：TP302.8[自动化与计算机技术—计算机系统结构]