(Approximate) Conic Nearest Neighbors and the induced Voronoi Diagram

(approximate) nearest neighbors of a query point but restricting only to
points that lie within a fixed cone with apex at the query point.
Apart from being a rather natural question to ask,
solutions to this problem have applications in surface reconstruction and dimension detection.

We investigate the structure of the Voronoi diagram induced by this notion of proximity and present
approximate and exact data structures for answering cone-restricted nearest neighbor queries. In particular
we develop an approximate Voronoi diagram of size $O((n/\epsilon^d)\log (1/\epsilon))$ that can be used
to answer cone-restricted nearest neighbor queries in $O(\log (n/\epsilon))$ time.