如果每个点的每个坐标是一个有理数，则在O（n）时间中凸出壳 [英] Convex Hull in O(n) time if each coordinate of each point is a rational number

问题描述

表明，如果每个点的每个坐标都可以在 O（n）时间内计算出平面中 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.

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

推荐答案

请勿使用Jarvis March，因为它的时间复杂度为 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.

相反，您应该使用例如<一个href = http://en.wikipedia.org/wiki/Graham_scan rel = nofollow> Graham扫描，其时间复杂度为 O（nlogn）。在Graham扫描算法中，时间复杂度主要是对所有点进行排序。请注意，基于比较的排序算法的时间复杂度为 O（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).

在作业问题中，您可以使用基数排序，而不是使用任何基于比较的排序算法来突破<$ c $的上限c> O（nlogn），因为假设所有点的坐标都是有界的。请注意，当要排序的输入是有界的时，可以使用基数排序，其复杂度为 O（n）。

In your homework problem, you can use radix sort instead of any comparison based sorting algorithms to beat the upper 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.

这篇关于如果每个点的每个坐标是一个有理数，则在O（n）时间中凸出壳的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！