Is there a linear-time algorithm for finding the convex hull of a complex polygon?

I'm pretty sure not. Convex hull on arbitrary point sets can be shown to be equivalent to sorting. We can order an arbitrary point set and connect the points in sequence making it into a complex polygon thereby reducing the problem on arbitrary point sets to yours.

Up vote 2 down vote favorite share g+ share fb share tw.

I know there's a worst-case O(n log n) algorithm for finding the convex hull of a complex polygon and a worst-case O(n) algorithm for finding the convex hull of a simple polygon. Is there a worst-case O(n) algorithm for finding the convex hull of a complex polygon? A complex polygon is a polygon where the line segments may intersect.

Finding the convex hull of a complex polygon is equivalent to finding the convex hull of an unordered list of points. Algorithm polygon time-complexity convex-hull link|improve this question edited Jul 31 '10 at 19:33 asked Jul 30 '10 at 21:28Daniel Stutzbach8,9182134 85% accept rate.

I'm pretty sure not. Convex hull on arbitrary point sets can be shown to be equivalent to sorting. We can order an arbitrary point set and connect the points in sequence making it into a complex polygon, thereby reducing the problem on arbitrary point sets to yours.

Here is a link to a proof that convex hull is equivalent to sorting. I'm too damn lazy and too bad a typist to write it out myself.

The proof relies on the idea that sorting takes at least O(n log n). However, that's only true of comparison-based sorting. Since points are integers or floats, we have many more operations available than simply comparisons.

In particular, radix sort can sort points in O(n) time. – Daniel Stutzbach Aug 18 '10 at 14:13.

In general, no there is not a O(n) solution. There is a pixelated version that is better than O(n log n). It is, however, so hobbled in other ways that you'd be crazy to use it in practice.

You render the first polygon (using verts 0, 1, 2) into screen space, then re-render the verts themselves using a distinct ID so they can be identified later. For example, you might clear the frame buffer to RGBA ffffffff and use fffffffe for space that is covered by the convex hull. Each vertex would be rendered using its ID as its RGBA; 00000000, 00000001, etc. A 16-bit example: fffffffffffffff fffffff0fffffff ffffffeeeffffff fffffeeeeefffff ffffeeeeeeeffff fffeeeeeeeeefff ff2eeeeeeeee1ff fffffffffffffff Checking a new point is a simple lookup in the current frame buffer.

If the pixel it occupies is 'shaded' with polygon or with a vertex ID, the new vertex is rejected. If the new vertex is outside the existing polygon, you find the first pixel between the new vertex and some point inside the convex hull (something in the middle of the first poly works fine) and march along the circumference of the hull - in both directions - until you find yourself on the far side of the hull from the new vertex. (I'll leave this as an exercise to the user.

There are plenty of solutions that all suck, from an efficiency perspective. ) Fill in the poly defined by these two points and the new vertex with the ID for polygon space - being careful not to erase any vertex IDs - and go on to the next pixel. When you're done, any pixel which contains a vertex ID that is not completely surrounded by hull IDs is a convex hull vertex.

While the algorithm's complexity is O(n) with the number of vertices, it's deficiencies are obvious. Nobody in their right mind would use it unless they had a ridiculous, insane, staggering number of points to process so that nearly every vertex would be immediately rejected, and unless they could accept the limitation of an aliased result. Friends don't let friends implement this algorithm.

It sounds like when the algorithm adds a vertex (which it must do O(n) times), it must march along the circumference of the hull-so-far (which will take O(n) time). Isn't that O(n**2)? Perhaps I'm misunderstanding the algorithm.

– Daniel Stutzbach Jul 31 '10 at 6:25 Nope. The circumference is bounded by the size of the frame buffer, and its traversal's complexity is not affected by the number of vertexes in it - only the number of pixels it contains. It takes the same ammount of time to trace a frame buffers of the same size with 3 verts and 3,000,000 verts.

– user30997 Aug 2 '10 at 17:07 @user30997: I see. If we treat the size of the frame buffer in pixels (p) as a variable rather than a constant, what is the time complexity in terms of n and p? – Daniel Stutzbach Aug 4 '10 at 13:40 If n is the number of verts and the frame buffer is p pixels on a side then, given that the longest traverse you could ever make of the circumference of the convex hull is 2p, you have a complexity of 2np.

N, being independent of p, gives a Big-O time complexity of O(n). However, the cost-per-operation is extremely high, so the algorithm is only useful to a narrow subset of applications. This isn't unusual in algorithms: consider, for example, the "almost sorted" list where you know that no item is out of place by more than one position.

The sorting complexity there is O(n). – user30997 Aug 4 '10 at 21:22.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.