I was wrong about this. The Delaunay triangulation is not the same as the convex hull; so what you want is a Delaunay/Voronoi partitioning. The vertices of the Voronoi cells are those which are equidistant from (at least) three points, so these are the points to test (the test is still as I described above).
Okay, I think that my algorithm (with a minor reworking) is actually O(n[sup]3[/sup]) worst case, but has a constant less than just doing a brute force solution.
The minor reworking is to define it as a recursive function. At every level you, split the set of vectors in half if the number of vectors is 6 or greater, and recurse on each of them. If the result of either call is the empty set, return the empty set. Otherwise, merge the two results as specified above, and return that. If you didn’t recurse, construct the set of bounding planes for those vectors and return the set of those and the set of vectors on those planes.
For each merging, you have a two sets of vectors, worst case the exact same number of vectors you passed in, and a set of bounding planes, worst case the number of vectors returned. You test each plane in one set against each vector in the other set, leading to 2 * (n/2)[sup]2[/sup] tests, where n is the number of vectors that were passed in to this step. Next in that merge you test every plane defined by one vector from each set against the other vectors in each set for (n/2)[sup]2[/sup] * (n - 2) comparisons. In the worst case, the result is the n vectors passed in and n bounding planes. By my calculations in the limit as n goes to infinity, in the worst cases there are n[sup]3[/sup]/2 - n[sup]2[/sup] comparsions. Whereas for the brute force solution there are n(n - 1)(n - 2) = n[sup]3[/sup] - 3n[sup]2[/sup] + 2n tests.