<![CDATA[Nearest Neighbour (NN) and k-Nearest Neighbour (kNN) queries, along with their various types, have found widespread applications in numerous real-world scenarios. As a result, they have garnered significant research attention over the past few decades. However, spatial queries involving curved obstacles present unique challenges due to the mathematical complexity of the curves themselves.Most existing algorithms address this issue by approximating curved obstacles as polygons and then applying visibility graphs to determine the shortest path. While effective in some cases, this polygonization approach becomes problematic when the obstacle contains a large number of polygonal points, which significantly increases the computational burden on both the visibility graph and Dijkstra’s algorithm. Alternatively, representing curved obstacles directly as mathematical equations offers a more efficient solution, with linear complexity in shortest path computation. Despite its potential, this approach has not yet been explored in the context of NN and kNN queries.In this research, we propose a novel approach to NN and kNN queries by modeling curved obstacles using curve equations, with circular shapes as the initial focus. Through theoretical analysis, we develop pruning techniques based on spatial relationships between query points, reference points, and obstacles. The correctness of our algorithms is rigorously validated through nine original lemmas, formulated independently without reference to existing papers or books.]]>
Copyrights © 2025
