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 |
