Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
K-Vector ND và Ứng Dụng của Nó trong Việc Xây Dựng Danh Mục Nhận Diện Sao Phi Denim
Tóm tắt
Một thuật toán tìm kiếm theo phạm vi đa chiều trực giao, K-vector đa chiều (K-Vector ND), được trình bày. Thuật toán này được phân tích và cho thấy thời gian thực thi không phụ thuộc vào kích thước của cơ sở dữ liệu, đối với các tập dữ liệu phân bố đồng đều. Các thử nghiệm số được thực hiện nhằm xác định lợi thế hiệu suất so với cây bốn phân (Quad-Tree) đối với tập dữ liệu hai chiều. Kết quả dao động từ điểm hòa vốn đến hệ số 14, tùy thuộc vào kích thước của cơ sở dữ liệu. K-Vector ND sau đó được áp dụng vào vấn đề xây dựng một cơ sở dữ liệu nhận diện sao không có kích thước chứa tất cả các bộ ba sao có thể nhìn thấy. Hiệu suất của thuật toán K-Vector ND trong nhiệm vụ đó sau đó được so sánh với một vòng lặp lồng ghép đơn giản, và kết quả cho thấy dao động từ điểm hòa vốn đến hệ số 200, tùy thuộc vào kích thước của cơ sở dữ liệu.
Từ khóa
#K-Vector ND #tìm kiếm phạm vi đa chiều #cây bốn phân #nhận diện sao #thuật toán hiệu suấtTài liệu tham khảo
CORMEN, T.H., LEISERSON, C.E., RIVEST, R.L., and STEIN, C. Introduction to Algorithms, McGraw-Hill, Second Ed., 2003.
MORTARI, D. and NETA, B. “K-vector Range Searching Techniques,” Advances in the Astronautical Sciences, Vol. 105, 2000, pp. 449–464.
MORTARI, D. “Search-Less Algorithm for Star Pattern Recognition,” The Journal of the Astronautical Sciences, Vol. 45, April–June 1997, pp. 179–194.
SAMAAN, M.A., MORTARI, D., and JUNKINS, J.L. “Recursive Mode Star Identification Algorithms,” IEEE Transactions on Aerospace and Electronic Systems, Vol. 41, October 2005, pp. 1246–1254.
MORTARI, D. “SP-Search: A New Algorithm for Star Pattern Recognition,” Proceedings of the 9th Annual AAS/AIAA Space Flight Mechanics Meeting, Vol. 102, Breckenridge, CO, February 1999, pp. 1165–1174.
MEHLHORN, K. Data Structures and Algorithms 3, Vol. 3 of Monographs in Theoretical Computer Science. An EATCS Series. Springer, 1984.
BENTLEY, J.L. “Multidimensional Binary Search Trees Used for Associative Searching,” ACM, Vol. 18, No. 9, 1975, pp. 509–517.
AGARWAL, P.K. “Range Searching” Handbook of Discrete and Computational Geometry, Boca Raton, Florida: CRC Press, 1997, pp. 575–598.
PREPARATA, F.P. and SHAMOS, M.I. Computational Geometry, Springer-Vertag, New York, 1985.
BENTLEY, J.L. and FRIEDMAN, J.H. “Data Structures for Range Searching,” Computing Surveys, Vol. 111, No. 4, 1979, pp. 398–409.
OVERMARS, M.H. “Efficient Data Structures for Range Searching on a Grid,” Journal of Algorithms, Vol. 9, 1988, pp. 254–275.
ALSTRUP, S., BRODAL, G.S., and RAUHE, T. “New Data Structures for Orthogonal Range Searching,” Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000, pp. 198–207.
SUBRAMANIAN, S. and RAMASWAMY, S. “The P-Range Tree: A New Data Structure for Range Searching in Secondary Memory,” Proceedings of ACM SODA, 1995.
CHAZELLE, B. “Lower Bounds for Orthogonal Range Searching: I. The Reporting Case,” Journal of the ACM, Vol. 37, April 1990, pp. 200–212.
CHAZELLE, B. “Lower Bounds for Orthogonal Range Searching: II. The Arithmetic Model,” Journal of the ACM, Vol. 37, June 1990, pp. 439–463.
LUEKER, G.S. “A Data Structure for Orthogonal Range Queries,” Proceedings of the 19th Annual IEEE Symposium on Foundations of Computer Sciences, 1978, pp. 28–34.
SAMAAN, M.A., MORTARI, D., and JUNKINS, J. L. “Nondimensional Star Identification for Uncalibrated Star Cameras,” The Journal of the Astronautical Sciences, Vol. 54, January–March 2006, pp. 95–111.