Abstract: A new algorithm of computing convex hulls of plane point sets is presented，based on the research on a large amount of algorithms of computing the convex hulls of plane point sets.In the algorithm，the four extreme points are first computed，which compose a quadrangle，then for the points out of the quadrangle we figure out which line sections they belong to in order with the method of bisection.For the points in the same line section，we just find out the points on the right side，then connect them with the two endpoints of the line section separately to compose a new polygon chain，then process each point in the same way until the last one.In this way，four monotonic chains of simple polygons are obtained，then the vertices of the convex hulls of the four monotonic chains are computed.Its time complexity is O（n）.All the vertices are the ones of the convex hull of the plane point set.The total time complexity of this algorithm is not more than O（n log n）.

Key words: point set, monotonic chains, convex hull

摘要： 在研究了大量的求平面点集凸包的算法基础上，提出了一种新的构造平面点集的凸壳算法。此算法先求出四个极值点，构造出一个四边形。对于四边形外面的点依次用二分法进行判断是属于哪个线段区域；对于一个线段区域上的点只需要找出右侧的点，分别和线段的两个端点连接得到新的多边形链，依次这样处理每个点，直到结束。这样就得到四个简单多边形单调链，然后对单调链求凸点，时间复杂度为O（n），最后求得的每个凸点就是平面点集的凸壳，此算法总的时间复杂度不超过O（n log n）。

关键词: 点集, 单调链, 凸壳