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 Edge algorithm
Picture
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.

Download
Proudly powered by Weebly