Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Độ phức tạp của nhiều tế bào trong các cấu hình mặt phẳng và các vấn đề liên quan
Tóm tắt
Chúng tôi xem xét một số vấn đề liên quan đến các điểm và mặt phẳng trong không gian ba chiều. Kết quả chính của chúng tôi là: (i) Số mặt tối đa bao quanh m tế bào khác nhau trong một cấu trúc của n mặt phẳng là O(m^{2/3}n ext{log}n + n^{2}); chúng tôi có thể tính toán m tế bào như vậy được xác định bởi một điểm trong mỗi tế bào, trong thời gian tồi tệ nhất là O(m^{2/3}n ext{log}^{3}n + n^{2} ext{log}n). (ii) Số lần chạm tối đa giữa n mặt phẳng và m đỉnh của cấu trúc của chúng là O(m^{2/3}n ext{log}n + n^{2}), nhưng số này chỉ là O(m^{3/5-δ}n^{4/5+2δ} + m + n ext{log}m), cho bất kỳ δ > 0, với bất kỳ tập hợp điểm nào mà không có ba điểm nào nằm trên một đường thẳng. (iii) Đối với một tập hợp tùy ý gồm m điểm, chúng tôi có thể tính số lần chạm giữa chúng và n mặt phẳng bằng một thuật toán ngẫu nhiên mà độ phức tạp thời gian mong muốn là O((m^{3/4-δ}n^{3/4+3δ} + m) ext{log}^{2}n + n ext{log}n ext{log}m) đối với bất kỳ δ > 0. (iv) Với m điểm và n mặt phẳng, chúng tôi có thể tìm mặt phẳng nằm ngay bên dưới mỗi điểm trong thời gian mong đợi ngẫu nhiên là O([m^{3/4-δ}n^{3/4+3δ} + m] ext{log}^{2}n + n ext{log}n ext{log}m) cho bất kỳ δ > 0. (v) Số facette tối đa (tức là, các mặt (d−1)-chiều) bao quanh m tế bào khác nhau trong một cấu trúc của n mặt phẳng trong d chiều, với d > 3, là O(m^{2/3}n^{d/3} ext{log}n + n^{d-1}). Đây cũng là một giới hạn trên cho số lần chạm giữa n mặt phẳng trong d chiều và m đỉnh của cấu trúc của chúng. Các giới hạn tổ hợp trong (i) và (v) cũng như giới hạn tổng quát trong (ii) là gần như chặt chẽ.
Từ khóa
#độ phức tạp #mặt phẳng #tế bào #cấu trúc #thời gian tồi tệ nhấtTài liệu tham khảo
P. K. Agarwal, Intersection and decomposition algorithms for arrangements of curves in the plane, Ph.D. Dissertation, Computer Science Department, New York University, June 1989.
B. Aronov and M. Sharir, Triangles in space, or: Building and analyzing castles in the air,Proc. 4th ACM Symp. on Computational Geometry, 1988, pp. 381–391.
R. J. Canham, A theorem on arrangements of lines in the plane,Israel J. Math. 7 (1969), 393–397.
B. Chazelle, How to search in history,Inform. and Control 64 (1985), 77–99.
K. Clarkson, A probabilistic algorithm for the post office problem,Proc. 17th ACM Symp. on Theory of Computing, 1985, pp. 75–84.
K. Clarkson, New applications of random sampling in computational geometry,Discrete Comput. Geom. 2 (1987) 195–222.
K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, and E. Welzl, Combinatorial complexity bounds for arrangements of curves and surfaces,Proc. 29th IEEE Symp. on Foundations of Computer Science, 1988, pp. 568–579. (Also,Discrete Comput. Geom., this issue, 99–160.)
D. Dobkin and D. Kirkpatrick, Fast detection of polyhedral intersections,Theoret. Comput. Sci. 27 (1983), 241–253.
H. Edelsbrunner,Algorithms in Combinatorial Geometry, Springer-Verlag, Heidelberg, 1987.
H. Edelsbrunner, The upper envelope of piecewise linear functions: Tight bounds on the number of faces,Discrete Comput. Geom. 4 (1989), 337–343.
H. Edelsbrunner, L. Guibas, J. Hershberger, R. Seidel, M. Sharir, J. Snoeyink, and E. Welzl, Implicitly representing arrangements of lines or segments,Proc. 4th ACM Symp. on Computational Geometry, 1988, pp. 56–69. (Also,Discrete Comput. Geom. 4, (1989), 433–466.)
H. Edelsbrunner, L. Guibas, and M. Sharir, The complexity of many faces in arrangements of lines or segments,Proc. 4th ACM Symp. on Computational Geometry, 1988, pp. 44–55. (Also,Discrete Comput. Geom., this issue, 161–196.)
H. Edelsbrunner and D. Haussler, The complexity of cells in three-dimensional arrangements,Discrete Math. 60 (1986), 139–146.
H. Edelsbrunner, J. O'Rourke, and R. Seidel, Constructing arrangements of lines and hyperplanes with applications,SIAM J. Comput. 15 (1986), 341–363.
H. Edelsbrunner and E. Welzl, On the maximal number of edges of many faces in an arrangement,J. Combin. Theory Ser. A 41 (1986), 159–166.
D. Haussler and E. Welzl, Epsilon-nets and simplex range queries,Discrete Comput. Geom. 2 (1987), 127–151.
F. P. Preparata and D. E. Muller, Finding the intersection ofn half space in timeO(n logn),Theoret. Comput. Sci. 8 (1979), 44–55.
G. Purdy and P. Erdős, Some extremal problems in combinatorial geomery, manuscript, 1987.
E. Szemerédi and W. T. Trotter, Extremal problems in discrete geometry,Combinatorica 3 (1983), 381–392.