Question

问题

计算数学 >> 数据结构
Questions in category: 数据结构 (Data Structure).

平面上 $N$ 个点所组成凸包的算法.

Posted by haifeng on 2018-05-15 18:33:52 last update 2018-05-15 18:35:11 | Answers (0) | 收藏


凸包(convex hull)问题是找出一个将平面上的点集围住的(面积)最小的凸多边形的问题.
 

试给出寻找凸包的一个 $O(N\log N)$ 算法.

 


References:

Mark Allen Weiss, Data Structures and Algorithm Analysis in C++, Third Edition.

张怀勇 等译. Ex. 10.51, P.349