View Question
Q: finding the convex hull of a polygon in computational geometry ( Answered,   0 Comments )
 Question
 Subject: finding the convex hull of a polygon in computational geometry Category: Computers > Algorithms Asked by: eddixxx-ga List Price: \$200.00 Posted: 04 Jan 2003 05:57 PST Expires: 03 Feb 2003 05:57 PST Question ID: 137349
 ```A polygon with n vertexes in plane - 2 dimensions. the polygon is not necessarily convex. the vertexes are given in their order of appearence. I need to find the convex of the polygon in complexity O(n) - linear complexity``` Request for Question Clarification by dannidin-ga on 04 Jan 2003 06:44 PST ```eddixxx, i have found linear time algorithms for computing the convex hull of a SIMPLE polygon, i.e. a polygon that does not intersect itself. is this sufficient to answer your question? i am still looking for algorithms for non-simple polygons, but i suspect that it may not be known how to do this in linear time, or if it can be done at all. for the general problem of finding the convex hull of a set of points in two dimensions, the best algorithms have O(n log(n)) complexity, and it is an open problem whether this can be improved. so i will keep looking, but tell me if you know your polygons to be simple. dannidin``` Request for Question Clarification by dannidin-ga on 04 Jan 2003 07:13 PST ```eddixxx, please ignore my last request for clarification. i foolishly overlooked the fact that the problem of computing the convex hull of a NONSIMPLE polygon is the same problem as computing the convex hull of an arbitrary set of points. therefore by what i mentioned earlier, it is an open problem whether this can be done in time less than O(n log(n)). therefore i will assume that you meant a simple polygon when you said just polygon. i will now get to work on writing a complete answer for you. dannidin```
 ```Hi eddixxx, First, a summary of your answer: -------------------------------- 1. The bad news: For the general problem of finding the convex hull of a set of n points in the plane, the best algorithm has complexity O(n log(n)), and it is not known whether this can be improved. 2. The good news: when the set of points are the vertices of a simple polygon, given in order of their appearance, there are several algorithms to compute the convex hull in linear time. In light of item 1 above, I assume that when you wrote "polygon" you meant "simple polygon". I will not write an algorithm for computing the convex hull for you, but instead refer you to one excellent on-line source where you can read a description of such an algorithm, and several more journal articles where you can read more in depth about the various existing algorithms. 3. Resources: I wrote a full list of references, including web resources and journal articles, at the end. The best source I found, and the one I would most recommend to begin with, is Pierre Lang's web page [W1], [4] http://www.cs.mcgill.ca/~plang/copgeo/copgeo.html which has a very readable explanation and a Java implementation of one of the simple algorithms due to Melkman [5]. Now, a more detailed answer: ---------------------------- 1. The bad news: Here is an excerpt from the Eric Weisstein's World of Mathematics http://www.mathworld.wolfram.com entry on convex hulls: http://www.mathworld.wolfram.com/ConvexHull.html "In d dimensions, the "gift wrapping" algorithm, which has complexity n^(floor(d/2)+1), can be used (Skiena 1997, p. 352). In two and three dimensions, however, specialized algorithms exist with complexity O(n log(n)) (Skiena 1997, pp. 351-352). Yao (1981) has proved that any decision-tree algorithm for the two-dimensional case requires quadratic or higher-order tests, and that any algorithm using quadratic tests (which includes all currently known algorithms) cannot be done with lower complexity than O(n log(n)). However, it remains an open problem whether better complexity can be obtained using higher-order polynomial tests (Yao 1981)." Regarding the same matter, here is an excerpt from the introduction to Melkman's paper [5], which I found using the MathSciNet database http://www.ams.org/mathscinet (this is a subscription service, you'll probably have access to it if you work in an academic institute): "After D. McCallum and D. Avis [1] showed that the convex hull of a simple polygon P with n vertices can be constructed in O(n) time, several authors devised simplified algorithms for this problem. R. L. Graham and F. F. Yao [2] presented a particularly simple and elegant one. After finding two points of the convex hull, their algorithm generated all other hull vertices using only one stack for intermediate storage. It is the purpose of this brief article to show that a slightly modified version of their algorithm constructs, online, the convex hull of any simple polyline in O(n) time. In contrast, the on-line construction of a nonsimple polyline requires O(n log n) time, as shown by F. P. Preparata [6]." (a polyline is like a polygon except it doesn't "close", i.e. the two ends don't join.) 2. The good news: The convex hull of a simple polygon in the plane can be computed in linear time. This result has a curious history, described in Hochstatter, Kromberg, and Moll's paper [W2], [3]. The first linear algorithm for this problem was suggested by Sklansky in 1972. However, it was later shown to be incorrect. The first correct algorithm was given by Avis and McCallum [1] in 1979, and several other algorithms were given later. One particularly simple algorithm is due to Melkman [5]. Pierre Lang from Mcgill University wrote a web page [W1], [4] which explains Melkman's algorithm, proves its correctness and demonstrates it with a Java applet (source code included). Hochstatter, Kromberg and Moll [W2], [3] gave in 1994 an algorithm correcting the fault in Sklansky's original algorithm. 3. List of resources: Web resources: [W1] Pierre Lang's implementation of Melkman's algorithm http://www.cs.mcgill.ca/~plang/copgeo/copgeo.html [W2] Hochstatter, Kromberg and Moll's paper A new linear time algorithm for computing the convex hull of a simple polygon in the plane www.uni-koeln.de/ftp/reports/zpr/94/94-94160/94-94160.ps (this paper has some more related references. you must have postscript viewing software to read it). Full list of resources: [1] D. Avis,. D. McCallum. A linear algorithm for finding the convex hull of a simple polygon. Information Processing Letters, vol. 9, no. 5, 201-206, 1979. [2] R. Graham, F. Yao. Finding the convex hull of a simple polygon. Journal of Algorithms 4, 324-331, 1983. [3] W. Hochstatter, S. Kromberg, C. Moll. A new linear time algorithm for computing the convex hull of a simple polygon in the plane. Technical report no. 94.160, University of Cologne, 1994. www.uni-koeln.de/ftp/reports/zpr/94/94-94160/94-94160.ps [4] Pierre Lang's implementation of Melkman's algorithm http://www.cs.mcgill.ca/~plang/copgeo/copgeo.html [5] A. A. Melkman. On-line construction of the convex hull of a simple polyline. Information Processing Letters 25 (1987) 11-12. [6] F. P. Preparata. An optimal real-time algorithm for planar convex hulls. Comm. ACM 22 (1979), no. 7, 402-405. Search strategy: google search on terms "convex hull" "polygon" "linear complexity". I hope this is the information you were looking for, if you still have questions please ask for clarification and I will try to help. Regards, dannidin```