Conic nearest neighbor queries and approximate Voronoi diagrams (Q2261577)

The paper deals with the conic nearest neighbour problem, i.e., given a cone \(C\) we want to preprocess a set \(S\) of \(n\) points in a Euclidean space so that for any query point \(q \in \mathbb R^d\) we can determine a nearest neighbour to \(q\) among points of \(S\) contained in cone \(C\) with apex at \(q\). The authors show how to construct an approximate conic Voronoi diagram of size \(O((n/\varepsilon^d)\log(1/\varepsilon))\) that can be used to answer approximate conic nearest neighbour queries in \(O(\log(n/\varepsilon))\), where \(\varepsilon > 0\) is a fixed approximation factor. The preprocessing time needed in the algorithm is \(O((n/\varepsilon^d)\log(n/\varepsilon)\log(1/\varepsilon))\). In the algorithm, the cells of the approximate conic Voronoi diagram are first generated and stored in quadtree-like data structure. Then, each cell \(u\) is assigned an appropriate point \(p_u\) satisfying two requirements: (1) the distance from \(q \in u\) to \(p_u\) can be slightly larger than the distance from \(q\) to its exact conic nearest neighbour, (2) \(p_u\) lies either in the cone \(C\) or slightly outside of \(C\). To achieve this, the authors use the top-down method of propagation of representatives. After presenting the construction of the approximate conic Voronoi diagram, the authors show how the processing of queries is performed and prove its correctness. Moreover, they show that the fixed direction and fixed angle cone restriction can be easily removed with an increase in space by a factor of \(O(1/\varepsilon^d)\).