1.6.2 Convex Hull

Problem Input | Problem Output 


INPUT                    OUTPUT

Input Description: A set S of n points in d -dimensional space.

Problem: Find the smallest convex polygon containing all the points of S .

Implementations

  • Qhull - higher dimensional convex hull program (C) (rating 10)
  • LEDA - A Library of Efficient Data Types and Algorithms (C++) (rating 6)
  • Clarkson's higher dimensional convex hull code (C) (rating 6)
  • Joseph O'Rourke's Computational Geometry (C) (rating 6)
  • Xtango and Polka Algorithm Animation Systems (C++) (rating 4)
  • Moret and Shapiro's Algorithms P to NP (Pascal) (rating 3)
  • Netlib / TOMS -- Collected Algorithms of the ACM (FORTRAN) (rating 3)

    Related Problems

  • Simplifying Polygons
  • Sorting
  • Traveling Salesman Problem
  • Voronoi Diagrams

    Go to the corresponding chapter in the book
    About the Book
    Send us Mail
    Go to Main Page

    This page last modified on Tue Jun 03, 1997 .