Yes, it is possible to find the nearest point set associated with the Delaunay cell containing a given point . As we discussed in Section 3.3, the Delaunay complex can be represented by the convex hull of appropriately lifted points in , and the non-vertical facets coincide with the Delaunay cells once they are projected to the original space. Thus the problem of determining the Delaunay cell containing a given point can be reduced to finding the first facet of a polyhedron ``shoot'' by a ray.
To be more precise, let , and let for . Then the lower hull of the lifted points :
Now every Delaunay cell is a projection of a non-vertical facet of . We are thus looking for an inequality satisfying (9), (10) and . By scaling with , we may assume . For a given point , let , and let , . Determining the Delaunay cell containing is equivalent to finding the last inequality ``hit'' by the halfline . More precisely, it is to find a non-vertical facet inequality such that the intersecion point of the corresponding hyperplane and the half line is highest possible.
By substituting for in with , we obtain
minimize | (11) | |||||
subject to | for all |
It is important to note that the above LP might be unbounded. If it is unbounded, it can be easily shown that is not in any Delaunay cell, i.e., not in the convex hull of . A certificate of unboundedness actually induces a hyperplane strongly separating from . (why?)