algorithm - 如果每个点的每个坐标都是有理数，则 O(n) 时间内的凸包

Question

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

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

Answer 1

不要使用 Jarvis March，因为它的时间复杂度为O(nh). 在最坏的情况下，h可能大到n。请注意，这h是船体上的点数。

相反，您应该使用时间复杂度为O(nlogn). 在格雷厄姆扫描算法中，时间复杂度主要由对所有点排序的时间复杂度决定。请注意，基于比较的排序算法的时间复杂度为O(nlogn).

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

有关各种凸包算法的比较，请参见此处。