3
$\begingroup$

I'm given $n$ points $(p_1, p_2, \ldots, p_n)$, lying on the boundary of a polygon and constituting this polygon (not necessarily convex), whereby those points are given me in clockwise order and I want to compute the convex hull of this polygon, i.e. determine the set of points $S \subseteq \{p_1, p_2, \ldots, p_n\}$ s.t. the points in $S$ shape the convex hull of the polygon. The tricky part is that my runtime constraint is $O(n)$, which is why I'm very stuck on this task. One should output the points of the convex hull in counterclockwise order.

$\endgroup$
10
  • 1
    $\begingroup$ What do you mean by "compute the convex hull"? In what form do you want the output of your algorithm? $\endgroup$
    – Klaus
    May 30 at 9:57
  • 1
    $\begingroup$ Google it. You'll quickly find an answer. $\endgroup$ May 30 at 9:57
  • $\begingroup$ @uniquesolution unfortunately not, the runtime constraint makes it more difficult $\endgroup$
    – TaChu
    May 30 at 9:59
  • $\begingroup$ @Klaus I want the subset of the given points that shape the convex hull in form of a list, printed or whatever you prefer (that's not of much importance, rather how the algorithm works) $\endgroup$
    – TaChu
    May 30 at 10:00
  • 1
    $\begingroup$ It is claimed in this question that the convex hull of a simple polygon is found in linear time by Melkman's algorithm. $\endgroup$
    – Martin R
    May 30 at 10:09
2
$\begingroup$

One algorithm that does the above is Lee's algorithm, explained in this paper https://link.springer.com/content/pdf/10.1007/BF00993195.pdf

$\endgroup$
1
$\begingroup$

Given an unordered set of points, Graham scan yields their convex hull in O(N log N) time complexity. The limiting factor is the sort phase; everything else is linear in time, as the Wikipedia article explains.

When N is a positive integer with a known maximum (for example, 232-1 when using C uint32_t, or 264-1 when using C uint64_t type), you can use radix sort to do the sort phase in linear time, yielding an implementation of Graham scan with linear time complexity, but with a fixed upper limit for N.

If the points are given in a suitable order, other algorithms can be used to achieve linear time complexity.

Quite a few algorithms assume the points given are the vertices of a polygon in order – meaning that each consecutive pair of points given are connected with an edge in the polygon, with the initial and final points also connected with an edge.

Melkman's Convex Hull Algorithm is probably the best known of these; the Wikipedia Convex hull of a simple polygon article lists a couple more. These assume that the polygon given is simple (does not intersect itself, and has no holes); some also assume the polygon is not degenerate (a line segment) or that consecutive points (polygon vertices) are not collinear.

I would recommend you examine your data properties, to see how you can get under the O(N log N) time complexity boundary (due to sorting); either by (implicitly) limiting N (so you can use radix sort with linear time complexity), or by leveraging data order (avoiding the need to sort altogether).

Finally, note that time complexity is not a measure of computational efficiency, but of how an algorithm scales as the problem set grows. In particular, radix sort algorithms tend to be "slow" in practice, with several O(N log N) being "faster" up to a very large N (last time I checked, on the order of millions to hundreds of millions, depending on exact implementation – computer cache architecture details being a deciding factor!).

$\endgroup$
3
  • $\begingroup$ I've already found a solution in $O(n)$ time, your answer doesn't get the point of my question $\endgroup$
    – TaChu
    May 30 at 16:42
  • $\begingroup$ @TaChu: No, Lee's algorithm only works on simple polygons, just like Melkman's. Lee's algorithm is also listed on the Wikipedia "Convex hull of a simple polyhon" page I linked to above. Furthermore, the "simple polygon" argument in the question only applies if one assumes the points are given in order, and are not just an unordered set of points on the boundary of the polygon. But thanks for the downvote anyway. $\endgroup$
    – Glärbo
    May 30 at 22:24
  • $\begingroup$ I can't and wouldn't downvote your post (I have too few reputation). Moreover, I specified in my question that the order is clockwise $\endgroup$
    – TaChu
    Jun 1 at 9:27

Not the answer you're looking for? Browse other questions tagged or ask your own question.