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:  an incremental algorithm
Picture
This incremental algorithm depends on sorting:  the points are sorted from left to right (or bottom to top).  After the points are sorted, the efficiency of the algorithm is linear in the number of points; including the sorting, the efficiency is the order of the sorting, which can be made as good as O (n log n).  

After the points are sorted, the algorithm begins at the left, and places the first two points on the upper convex hull:  the portion of the convex hull below which all points lie.  It then includes points as vertices of the convex hull as long as including a vertex keeps the hull convex.  This means that all turns are right turns as one proceeds along the convex hull.  

Localization

The visualization of the incremental algorithm was done while I was a visiting professor at the University of Innsbruck (Austria), Institute for Mathematics.  Consequently, I asked the help of my students to translate the text (titles, subtitles, questions) to German, and included multiple language tracks in the movies so that the viewer could watch the movie in either English or German.  Subsequently, I added Italian.  

The viewer can choose the language in the QuickTime Player, by using the Movie menu, Choose Language item.  In addition, if the viewer is running either the German or Italian version of the operating system, QuickTime Player will automatically open the movie in German or Italian, respectively.

Click the Download button at the right to download a zipped file of all  movies described on this page.

Download
Proudly powered by Weebly