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

Joseph O'Rourke gives eleven defining descriptions of the convex hull in his book, Computational Geometry in C (Cambridge University Press, 1994).  Perhaps useful definitions are:  (1) The convex hull of a set of points in the plane is the smallest convex polygon which encloses those points; (2) the convex hull of a set of points in the plane is the enclosing convex polygon with the smallest area.  A convex polygon is a polygon for which the line connecting any two points in the polygon lies within the polygon.
The convex hull is a useful geometrical construct in many application areas, and algorithms for computing the convex hull are studied in their own right as test cases for algorithm analysis and algorithm efficiency.
In addition to O'Rourke's book cited above, references include deBerg, M, van Kreveld, M, Overmars, M, and Schwarzkopf, O., Computational Geometry: Algorithms and Applications (Springer, 2000); Preparata, Franco and Shamos, Michael, Computational Geometry: An Introduction (Springer, 1985).
Proudly powered by Weebly