##
1.6.2 Convex Hull

##
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
.