Counting and representing intersections among triangles in three dimensions
Tài liệu tham khảo
Agarwal, 1990, Partitioning arrangements of lines, part II: applications, Discrete Comput. Geom., 5, 533, 10.1007/BF02187809
Agarwal, 1991
Agarwal, 2002, Reporting intersecting pairs of polytopes in two and three dimensions, Computational Geometry, 23, 195, 10.1016/S0925-7721(02)00049-4
Agarwal, 1994, On range searching with semialgebraic sets, Discrete Comput. Geom., 11, 393, 10.1007/BF02574015
Agarwal, 1993, Counting circular arc intersections, SIAM J. Comput., 22, 778, 10.1137/0222050
Agarwal, 1990, Red-blue intersection detection algorithms, with applications to motion planning and collision detection, SIAM J. Comput., 19, 297, 10.1137/0219020
Agarwal, 2000, Efficient algorithms for approximating polygonal chains, Discrete Comput. Geom., 23, 273, 10.1007/PL00009500
Alon, 2000
Bentley, 1979, Algorithms for reporting and counting geometric intersections, IEEE Trans. Comput., 28, 643, 10.1109/TC.1979.1675432
Brönnimann, 1998, Optimal slope selection via cuttings, Computational Geometry, 10, 23, 10.1016/S0925-7721(97)00025-4
Chazelle, 1986, Reporting and counting segment intersections, J. Comput. System Science, 32, 156, 10.1016/0022-0000(86)90025-5
Chazelle, 1992, An optimal algorithm for intersecting line segments in the plane, J. ACM, 39, 1, 10.1145/147508.147511
Chazelle, 1990, A deterministic view of random sampling and its use in geometry, Combinatorica, 10, 229, 10.1007/BF02122778
Clarkson, 1987, New applications of random sampling in computational geometry, Discrete Comput. Geom., 2, 195, 10.1007/BF02187879
Clarkson, 1989, Applications of random sampling in computational geometry, II, Discrete Comput. Geom., 4, 387, 10.1007/BF02187740
Cole, 1989, An optimal time algorithm for slope selection, SIAM J. Comput., 18, 792, 10.1137/0218055
Dillencourt, 1992, A randomized algorithm for slope selection, Internat. J. Comput. Geom. Appl., 2, 1, 10.1142/S0218195992000020
Dobkin, 1983, Fast detection of polyhedral intersection, Theoret. Comput. Science, 27, 241, 10.1016/0304-3975(82)90120-7
de Berg, 1996, Vertical decompositions for triangles in 3-space, Discrete Comput. Geom., 15, 35, 10.1007/BF02716578
Erickson, 1999, New lower bounds for convex hull problems in odd dimensions, SIAM J. Comput., 28, 1198, 10.1137/S0097539797315410
E. Ezra, M. Sharir, Output-sensitive construction of the union of triangles, in: Proc. 15th Annu. ACM-SIAM Sympos. Discr. Alg. (SODA'04), 2004, pp. 413–422. A revised version in SIAM J. Comput., in press
Gajentaan, 1995, On a class of O(n2) problems in computational geometry, Computational Geometry, 5, 165, 10.1016/0925-7721(95)00022-2
L.J. Guibas, M. Overmars, M. Sharir, Counting and reporting intersections in arrangements of line segments, Technical Report 434, Dept. Computer Science, New York University, March 1989
Haussler, 1987, ɛ-nets and simplex range queries, Discrete Comput. Geom., 2, 127, 10.1007/BF02187876
Katz, 1993, Optimal slope selection via expanders, Inform. Process. Lett., 47, 115, 10.1016/0020-0190(93)90234-Z
Koltun, 2005, Curve-sensitive cuttings, SIAM J. Comput., 34, 863, 10.1137/S0097539703435686
Matoušek, 1991, Cutting hyperplane arrangements, Discrete Comput. Geom., 6, 385, 10.1007/BF02574697
Matoušek, 1991, Randomized optimal algorithm for slope selection, Inform. Process. Lett., 39, 183, 10.1016/0020-0190(91)90177-J
Matoušek, 2002
Mulmuley, 1994
Pellegrini, 1997, On counting pairs of intersecting segments and off-line triangle range searching, Algorithmica, 17, 380, 10.1007/BF02523679
Sharir, 1995