Prof. Dr. Jay Martin Anderson
Professor Emeritus of Computer Science, Franklin & Marshall College
  • home
  • Development
    • Gallery
    • Stop and Pray
    • Stations at St. Thomas
    • PricePer
    • What's It Cost?
    • my own
    • at F&M
    • for clients
  • Small Gallery
  • LVC
  • Visualization
    • Algorithm Visualization >
      • Binary Space Partition
      • Convex Hull >
        • Extreme Point algorithm
        • Extreme Edge algorithm
        • "Gift Wrap" algorithm
        • Incremental algorithm
        • Incremental algorithm in three dimensions
        • "QuickHull" algorithm
      • Delaunay triangulation >
        • Incremental algorithm
        • from the Voronoi diagram
      • Line intersection >
        • a "brute force" algorithm
        • Sweepline algorithm
      • Motion planning
      • Point-in-Polygon >
        • Plumbline algorithm
        • Trapezoidal Map
        • Winding Number
      • Polygon triangulation >
        • "Art Gallery" Problem
        • Recursive algorithm
        • Make Monotone Polygons
        • Triangulate a Monotone Polygon
      • Voronoi diagram >
        • Fortune's algorithm
        • Intersection of Half-Planes
        • Quadtree algorithm
    • Data Visualization
  • OpenGL
    • OpenGL for Apple Software Developers
  • iBooks
  • about me
    • contact
Convex Hull:  the Extreme Point algorithm
Picture
The extreme point algorithm has to be among one of the worst, in terms of efficiency. It has quartic order (that is, O(N4)), which means that the algorithm will run 10,000 times longer for only ten times as many points. Nonetheless, these movies show clearly how much thrashing goes on in a really inefficient algorithm.

The idea is simple: for each point, see if that point lies within a triangle formed using all possible combinations of three other points. If it does, then it must lie within the convex hull; if it does not, then it lies on the perimeter of the convex hull, and must therefore be a vertex of the convex hull. The algorithm identifies the vertices of the convex hull, but it does not connect them in either clockwise or counterclockwise order.

The algorithm is so inefficient that even the formation of the convex hull of relatively few points makes a long movie.  Click the Download button at the right to download all movies described on this page.

Download
Proudly powered by Weebly