如果每个点的每个坐标都是有理数,则在O(n)时间内采用凸壳

Question

如果每个点的每个坐标是p/q形式的有理数,并且p和q的有界值,则表明在平面中n个点的凸包可以在O(n)时间内计算.

注意:这是一个家庭作业问题.我可以想到以某种方式避免扫描所有点使用Jarvis March.也许这可以通过向固定方向投射光线(使用合理条件)来检查下一个点存在的位置来完成.

Answer 1

不要使用Jarvis March,因为它有时间复杂性O(nh).在最坏的情况下,h可能会一样大n.注意,这h是船体上的点数.

相反,您应该使用例如时间复杂度为的Graham扫描O(nlogn).在格雷厄姆扫描算法中,时间复杂度主要是对所有点进行排序.注意,基于比较的排序算法具有时间复杂度O(nlogn).

在你的作业问题中,你可以使用基数排序而不是任何基于比较的排序算法来击败上限,O(nlogn)因为假设点的坐标都是有界的.注意,当要排序的输入是有界时,可以使用基数排序,其具有复杂性O(n).

请参阅此处以了解各种凸包算法的比较.