Convex Hull: the Extreme Edge algorithm
|
The extreme edge algorithm us almost as bad as the "extreme point" algorithm in efficiency. It has cubic order (O(N3)), which means that the algorithm will run 1000 times longer (in time) for ten times as many points. Nonetheless, these movies show clearly how much thrashing goes on, even in a really inefficient algorithm.
Example: for each pair of points, which form a potential edge of the convex hull, see if all other points like on the same side of the edge connecting the two points. If they do, then this line is an edge of the convex hull. The algorithm identifies the edges of the convex hull, but it does not either connect them in either a clockwise or counterclockwise order. Click the Download button at the right to download a zipped file of all movies on this page. |