In the twodimensional convexhull problem we are given a multiset S
of points and the task is to find those points of S that are the
vertices of the smallest convex polygon enclosing all the points
of S. In the output the vertices must be reported in the order in
which they appear along the boundary of the polygon—either in clockwise
or counterclockwise order. Further, when the coordinates of the points
are integers, the computed output should always be correct. This collection contains our implementations of the following
convexhull algorithms: planesweep, torch,
divide & conquer, quickhull,
polesfirst, throwaway, introhull, and
bucketing. For an
input of size n, none of our implementations use more than
O(√n) extra words of memory and all run in linear expected
time when the input points are randomly distributed. As far as we
know, this collection contains the best known algorithms—both with
respect to time and space usage. If you know a better algorithm—or
a better implementation written in C++—and think that it
should be in this collection, let us know. Keep in mind that we
promise a reward of 2.56 brownie points for every person who is the
first to report an error in one of the programs released in this
collection.
