# Advanced Vectors Question

**URL:** <https://boards.straightdope.com/t/advanced-vectors-question/304047>\
**Category:** Factual Questions\
**Created:** [May 16, 2005, 11:24am UTC](https://boards.straightdope.com/t/advanced-vectors-question/304047 "2005-05-16T11:24:17Z")\
**Posts on this page:** 2\
**Page:** 2

<div class="post-metadata">

**Author:** ![Omphaloskeptic](https://avatars.discourse-cdn.com/v4/letter/o/bcef8e/32.png) [@Omphaloskeptic](https://boards.straightdope.com/u/Omphaloskeptic)\
**Post date:** [May 16, 2005, 7:46pm UTC](https://boards.straightdope.com/t/advanced-vectors-question/304047/21 "2005-05-16T19:46:44Z")

</div>

> [@Omphaloskeptic](#):
>
> For this I think what you want is the Delaunay triangulation of your points; this is the triangulation such that the circumcircle of each triangle contains none of the given points in its interior. In your case, since all of the vectors are unit vectors, this triangulation is essentially the same as the convex hull; so you can find this with a convex-hull algorithm that returns a list of faces (not just the extremal points).

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

---

<div class="post-metadata">

**Author:** ![Punoqllads](https://avatars.discourse-cdn.com/v4/letter/p/d2c977/32.png) [@Punoqllads](https://boards.straightdope.com/u/Punoqllads)\
**Post date:** [May 16, 2005, 9:28pm UTC](https://boards.straightdope.com/t/advanced-vectors-question/304047/22 "2005-05-16T21:28:52Z")

</div>

> [@Punoqllads](#):
>
> Actually, maybe it’s not O(n[sup]3[/sup]) in the worst case because you’re eliminating many planes from being tested against many vectors. I’ll think about it more.

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.

[Previous page](https://boards.straightdope.com/t/advanced-vectors-question/304047.md?page=1)