显示，凸包的 N 分的飞机可以在 O（N）的时间来计算每个点的，如果每个坐标是有理数的形式的P / Q，与p和q有界值。的

Show that the convex hull of n points in the plane can be computed in O(n) time if each coordinate of each point is a rational number of the form p/q , with bounded values for p and q.

注：这是一个家庭作业的问题。我只能想到用贾维斯年3月被以某种方式避免了所有点的扫描。也许这可以通过抛出射线固定方向（用理性的条件），检查那里的下一个点的存在来完成。

Note : This is a homework problem. I can just think of using Jarvis March by somehow avoiding the scan of all points. Maybe this can be done by throwing rays in fixed directions (using the rational condition) to check where the next point exists.

推荐答案

不要使用贾维斯三月，因为它具有时间的复杂度为O（NH）。在最坏的情况下， ^ h 可能大如 N 。需要注意的是 ^ h 是点对船体的数量。

Don't use Jarvis March since it has time complexity of O(nh). In the worst case, h may be as large as n. Note that h is the number of points on the hull.

相反，你应该使用，例如， Graham扫描的时间复杂度为 O（ nlogn）。在Graham扫描算法中，时间复杂性是由所有点排序的支配。需要注意的是基于比较的排序算法有 0的时间复杂度（nlogn）。

Instead, you should use, for example, Graham scan whose time complexity is O(nlogn). In Graham scan algorithm, the time complexity is dominated by that of sorting all the points. Note that comparison based sorting algorithms have a time complexity of O(nlogn).

在你的家庭作业的问题，您可以使用基数排序，而不是基于排序算法进行任何比较打的下界 O（nlogn），因为有一个假设，即该点的坐标都是有界的。请注意，如果要排序的投入是有界的基数排序可以使用，它具有的复杂性 O（N）。

In your homework problem, you can use radix sort instead of any comparison based sorting algorithms to beat the lower bound of O(nlogn) since there's an assumption that the coordinates of the points are all bounded. Note that when the inputs to be sorted are bounded radix sort can be used, which has a complexity of O(n).

请参阅此处各种凸包算法进行比较。

See here for comparisons of various convex hull algorithms.