K Nearest Neighbor in the Presence of a Circle as an Obstacle
Keywords:
Curve Obstacles, Dijkstra Algorithm, K Nearest Neighbor Query, Nearest Nearest Neighbor Query, PoligonizationAbstract
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.
References
Agarwal, P. K., Sharathkumar, R., & Yu, H. (2009). Approximate Euclidean shortest paths amid convex obstacles. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms.
Chang, E. C., Choi, S. W., Kwon, D. Y., Park, H., & Yap, C. K. (2006). Shortest path AMIDST disc obstacles is computable. International Journal of Computational Geometry and Applications, 16(5), 567-590.
Chazelle, B., Edelsbrunner, H., Grigni, M., Guibas, L., Hershberger, J., Sharir, M., & Snoeyink, J. (1994). Ray shooting in polygons using geodesic triangulations. Algorithmica, 12(1).
Chew, L. P. (1985). Planning the shortest path for a disc in O(n2 log n) time. Proceedings of the 1st Annual Symposium on Computational Geometry, SCG 1985.
Cover, T. M., & Hart, P. E. (1967). Nearest Neighbor Pattern Classification. IEEE Transactions on Information Theory, 13(1), 21-27.
Cruz, G. C. S., & Encarnação, P. M. M. (2012). Obstacle avoidance for unmanned aerial vehicles. Journal of Intelligent and Robotic Systems: Theory and Applications, 65(1), 203-217.
Gao, Y., Zheng, B., Chen, G., Lee, W. C., Lee, K. C. K., & Li, Q. (2009). Visible reverse k-nearest neighbor query processing in spatial databases. IEEE Transactions on Knowledge and Data Engineering, 21(9), 1314-1327.
Ghosh, S. K., & Mount, D. M. (1991). Output-sensitive algorithm for computing visibility graphs. SIAM Journal on Computing, 20(5), 888-910.
Guibas, L., Hershberger, J., Leven, D., Sharir, M., & Tarjan, R. E. (1987). Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorithmica, 2(1), 209-233.
Güting, R. H. (1994). An introduction to spatial database systems. The VLDB Journal, 3(4), 357-399.
Hershberger, J., & Suri, S. (1999). An optimal algorithm for Euclidean shortest paths in the plane. SIAM Journal on Computing, 28(6), 2215-2256.
Kapoor, S., & Maheshwari, S. N. (1988). Efficient algorithms for Euclidean shortest path and visibilty problems with polygonal obstacles. Proceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988, 172-182.
Lozano-Pérez, T., & Wesley, M. A. (1979). An algorithm for planning collision-free paths among polyhedral obstacles. Communications of the ACM, 22(10), 560-570.
Mitchell, J. S., Mount, D. M., & Papadimitriou, C. H. (1987). The discrete geodesic problem. SIAM Journal on Computing, 16(4), 647-668.
Nutanong, S., Tanin, E., & Zhang, R. (2007). Visible nearest neighbor queries. In International Conference on Database Systems for Advanced Applications, 876-883. Berlin, Heidelberg: Springer Berlin Heidelberg.
Papadias, D., Zhang, J., Mamoulis, N., & Tao, Y. (2003). Query processing in spatial network databases. In Proceedings 2003 VLDB Conference: 29th International Conference on Very Large Databases (VLDB), 802-813. Morgan Kaufmann.
Sharifzadeh, M., Kolahdouzan, M., & Shahabi, C. (2008). The optimal sequenced route query. VLDB Journal, 17(4), 765-787.
Storer, J. A., & Reif, J. H. (1994). Shortest paths in the plane with polygonal obstacles. Journal of the ACM (JACM), 41(5), 982-1012.
Taniar, D., & Rahayu, W. (2013). A taxonomy for nearest neighbour queries in spatial databases. Journal of Computer and System Sciences, 79(7), 1017-1039.
Wang, Y. Q., Xu, C. F., Yu, G., Gu, Y., & Chen, M. (2010). Visible k nearest neighbor queries over uncertain data. Jisuanji
Xuebao/Chinese Journal of Computers, 33(10), 1943-1952.
Wang, Y., Zhang, R., Xu, C., Qi, J., Gu, Y., & Yu, G. (2014). Continuous visible k nearest neighbor query on moving objects. Information Systems, 44, 1-21.
Welzl, E. (1985). Constructing the visibility graph for n-line segments in O(n2) time. Information Processing Letters, 20(4), 167-171.
Xu, H., Li, Z., Lu, Y., Deng, K., & Zhou, X. (2010). Group visible nearest neighbor queries in spatial databases. In International Conference on Web-Age Information Management, 333-344. Berlin, Heidelberg: Springer Berlin Heidelberg.
Xu, J., & Güting, R. H. (2015). Querying visible points in large obstructed space. GeoInformatica, 19(3), 435-461.
Zhang, J., Papadias, D., Mouratidis, K., & Manli, Z. (2005). Query processing in spatial databases containing obstacles. International Journal of Geographical Information Science, 19(10), 1091-1111.
Zhang, J., Papadias, D., Mouratidis, K., & Zhu, M. (2004). Spatial queries in the presence of obstacles. In International conference on extending database technology – EDBT 2004 Proceedings, 66-384. Berlin, Heidelberg: Springer Berlin Heidelberg.
