Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Về việc xây dựng đồ thị hàng xóm tương đối trong không gian Euclid K-dimension
Tóm tắt
Trong bài báo này, một thuật toán mới để xây dựng đồ thị hàng xóm tương đối (RNG) của một tập hợp n điểm trong không gian Euclid k chiều được trình bày, với k cố định ≥ 3. Thời gian chạy tệ nhất của thuật toán là O(n^{2−a(k)}(log n)^{1−a(k)}) cho a(k) = 2 − (k + 1), trong điều kiện không có ba điểm đầu vào nào tạo thành một tam giác cân. Các thuật toán trước đây cần O(n^{2}) thời gian. Thuật toán của chúng tôi được thực hiện trong hai giai đoạn. Đầu tiên, một siêu đồ thị của RNG với O(n) cạnh được xây dựng và sau đó các cạnh không thuộc về RNG sẽ bị loại bỏ.
Từ khóa
#đồ thị hàng xóm tương đối #thuật toán #không gian Euclid #độ phức tạp thuật toánTài liệu tham khảo
Brown, K. Q.: Geometric transforms for fast geometric algorithms. Ph.D. Thesis, Department of Computer Science, Carnegie Mellon University, Dec. 1979.
Chazelle, B.: How to search in history. Information and Control65, 77–99 (1985).
Dobkin, D., Lipton, R. J.: Multidimensional search problems. SIAM Journal on Computing5, 181–186 (1976).
Dodge, C. W.: Euclidean geometry and transformations. Addison-Wesley 1972.
Edelsbrunner, H.: Algorithms in combinatorial geometry. Heidelberg: Springer 1987.
Gabow, H. N., Bentley, J. L., Tarjan, R. E.: Scaling and related techniques for geometry problems. Proceedings of 16th Annual ACM Symposium on Theory of Computing, 1984, pp. 134–143.
Jaromczyk, J. W., Kowaluk, M.: A note on relative neighborhood graphs. Proceedings of 3th ACM Symposium on Computational Geometry, 1987, pp. 233–241.
Jaromczyk, J. W., Kowaluk, M.: Constructing the relative neighborhood graphs in 3-dimensional Euclidean space, 1989, unpublished manuscript.
Katajainen, K.: The region approach for computing relative neighbourhood graphs in theL p metric. Computing40, 147–161 (1988).
Katajainen, J., Nevalainen, O.: Computing relative neighbourhood graphs in the planes. Pattern Recognition19, 221–228 (1986).
Katajainen, J., Nevalainen, O., Teuhola, J.: A linear expected-time algorithm for computing planar relative neighbourhood graphs. Information Processing Letters25, 77–86 (1987).
Lee, D. T., Schacter, B. J.: Two algorithms for constructing a Delaunay triangulation. International Journal of Computer and Information Sciences9, 219–227 (1980).
Matula, D. M., Sokal, R. R.: Properties of variation research and the clustering of points in the plane. Geographical Analysis12, 205–222 (1980).
Shamos, M. I.: Computational geometry. Ph.D. Theses, Department of Computer Science, Yale University, 1978.
Supowit, K. J.: The relative neighborhood graph with an application to minimum spanning trees. Journal of Association for Computing Machinery30, 428–448 (1983).
Toussaint, G. T.: The relative neighbourhood graph of a finite planar set. Pattern Recognition12, 261–268 (1980).
Yao, A. C.: On constructing minimum spanning trees ink-dimensional spaces and related problems. SIAM Journal on Computing11, 721–736 (1982).