Lecture 28
Grad Presentations
Presentations
-
Becca Faust: Bentley-Ottman Line Segment Intersection
-
Craig Thompson: Euclidean Minimum Spanning Trees
-
Xueheng Wan: Visualizing Convex Hull Algorithms
Optional Reading
-
Becca: Bentley, J. L., & Ottmann, T. A. (1979). Algorithms for reporting and counting geometric intersections. IEEE Transactions on computers, (9), 643-647.
-
Becca: Boissonnat, J. D., & Preparata, F. P. (2000). Robust plane sweep for intersecting segments. SIAM Journal on Computing, 29(5), 1401-1421.
-
Craig: Graham, R. L., & Hell, P. (1985). On the history of the minimum spanning tree problem. Annals of the History of Computing, 7(1), 43-57.
Notes: Really only need to read the introduction, and to maybe read the Algorithm 1 section for a bit of flavor. -
Xueheng: Shneerson, M., & Tal, A. (1997, October). Visualization of geometric algorithms in an electronic classroom. In Proceedings of Visualization (pp. 455-458). IEEE.
-
Xueheng: Barber, C. B., Dobkin, D. P., Dobkin, D. P., & Huhdanpaa, H. (1996). The quickhull algorithm for convex hulls. ACM Transactions on Mathematical Software (TOMS), 22(4), 469-483.