Delaunay tesselations and convex hulls
The relationship I remember is that the Delaunay tessalation is the "visual complement" of Voronoi cells.

I just found this paper on Google which has a nice figure as to why finding the convex hull in d+a dimensions is equivalent to finding the Delaunay tessalation:

http://www.cs.mtu.edu/~shene/PUBLICATIONS/2004/Hull2VD.pdf

What's also interesting from a theoretical cs perspective is that the knn problem can be mapped to the Voronoi cell problem, and by extension to the Delaunay tesselation and the convex hull problem. Known algorithms in d-dimensions typically have an exponential dependency on dimension.