Can Qhull construct convex hulls and Delaunay triangulations one point at a time?
The Qhull library may be used to construct convex hulls and Delaunay triangulations one point at a time. It may not be used for deleting points or moving points. Qhull is designed for batch processing. Neither Clarkson’s randomized incremental algorithm nor Qhull are designed for on-line operation. For many applications, it is better to reconstruct the convex hull or Delaunay triangulation from scratch for each new point. With random point sets and on-line processing, Clarkson’s algorithm should run faster than Qhull. Clarkson uses the intermediate facets to reject new, interior points, while Qhull, when used on-line, visits every facet to reject such points. If used on-line for n points, Clarkson may take O(n) times as much memory as the average off-line case, while Qhull’s space requirement does not change. If you triangulate the output before adding all the points (option ‘Qt’ and procedure qh_triangulate), you must set option ‘Q11’. It duplicates the normals of triangulated facets
