Instructor: Joshua A. Levine
Office: 754 Gould-Simpson
Meets: M/W 2:00-3:15pm, 222 Social Sciences
Office Hours: M 3:30-4:30pm, T 4:30-5:30pm (GS 754), or by appointment
TA: Alex Koltz, firstname.lastname@example.org
TA Office Hours: M 1:00-2:00pm (GS 938)
TA: Justin Crum, email@example.com
TA Office Hours: F 10:00am-11:00am (GS 938)
D2L (for 437)
D2L (for 537)
All topics on this page are tentative and subject to change!
All required readings are intended to be read before class begins
Final Exam: Fri., May 3, 1-3pm, 222 Social Sciences
Highlighted dates have a homework assignment due immediately before class begins on that day.
Boxed dates correspond to the day before the deadlines for the dropping (without a W) and the withdraw deadlines for this semester.
See Spring 2019 Undergraduate Dates and Deadlines and
Spring 2019 Graduate Dates and Deadlines.
Link to Google drive folder with all lecture slides
- 2D Convex Hulls
Date: January 14, 2019
- Mount, Lectures 1,3 (pg. 2-6,11-16)
- Jarvis, R. A. (1973). On the identification of the convex hull of a finite set of points in the plane. Information processing letters, 2, 18-21.
- Graham, R. L. (1972). An efficient algorithm for determining the convex hull of a finite planar set. Info. Pro. Lett., 1, 132-133.
- Chan, T. M. (1996). Optimal output-sensitive convex hull algorithms in two and three dimensions. Discrete & Computational Geometry, 16(4), 361-368.
- Many variants referenced in BCKO, Section 1.5
- Line Segment Intersection
Date: January 16, 2019
- Overlay of Subdivisions
Date: January 23, 2019
- Mount, Lecture 23 (pg. 134-137)
- Paper that first suggested the DCEL: Muller, D. E., & Preparata, F. P. (1978). Finding the intersection of two convex polyhedra. Theoretical Computer Science, 7(2), 217-236.
- Winged-edge data structure: Baumgart, B. G. (1975, May). A polyhedron representation for computer vision. In Proceedings of the May 19-22, 1975, national computer conference and exposition (pp. 589-596). ACM.
- Polygon Triangulation
Date: January 28, 2019
- Mount, Lecture 6 (pg. 32-38)
- Garey, M. R., Johnson, D. S., Preparata, F. P., & Tarjan, R. E. (1978). Triangulating a simple polygon. Inform. Process. Lett., 7, 175-179.
- Lee, D. T., & Preparata, F. P. (1977). Location of a point in a planar subdivision and its applications. SIAM Journal on computing, 6(3), 594-606.
- A particularly famous solution: Chazelle, B. (1991). Triangulating a simple polygon in linear time. Discrete & Computational Geometry, 6(3), 485-524.
- low-D Incremental LP
Date: January 30, 2019
- low-D Randomized LP
Date: February 04, 2019
- Range Trees
Date: February 06, 2019
- Mount, Lectures 31,32 (pg. 163-174)
- Bentley, J. L. (1975). Multidimensional binary search trees used for associative searching. Communications of the ACM, 18(9), 509-517.
- Chazelle, B., & Guibas, L. J. (1986). Fractional cascading: I. A data structuring technique. Algorithmica, 1(1-4), 133-162.
- Chazelle, B., & Guibas, L. J. (1986). Fractional cascading: II. applications. Algorithmica, 1(1-4), 163-191.
- Trapezoidal Maps
Date: February 11, 2019
- Point Location
Date: February 13, 2019
- Voronoi Diagrams
Date: February 18, 2019
- Variations on Voronoi
Date: February 20, 2019
- Mount, Lecture 30 (pg. 160-163)
- Chew, L. Paul. (1990). Building Voronoi diagrams for convex polygons in linear expected time. Technical Report PCS-TR90-147, Dept. Math. Comput. Sci., Dartmouth College, Hanover, NH.
- Aggarwal, A., Guibas, L. J., Saxe, J., & Shor, P. W. (1989). A linear-time algorithm for computing the Voronoi diagram of a convex polygon. Discrete & Computational Geometry, 4(6), 591-604.
- Point-Line Duality
Date: February 25, 2019
- Line Arrangements
Date: March 11, 2019
- Mount, Lecture 14 (pg. 80-83)
- Edelsbrunner, H., Seidel, R., & Sharir, M. (1993). On the zone theorem for hyperplane arrangements. SIAM Journal on Computing, 22(2), 418-429.
- BCKO, 8.1,8.4
- Mount, Lecture 15 (pg. 83-90)
- Edelsbrunner, H., & Guibas, L. J. (1989). Topologically sweeping an arrangement. Journal of Computer and system sciences, 38(1), 165-194.
- Delaunay Triangulations
Date: March 13, 2019
- Delaunay, Part 2
Date: March 18, 2019
- Alpha Hulls
Date: March 20, 2019
- Tao Ju, CSE546 from Washington University in St. Louis, Fall 2017 Alpha Hull (Slides)
- Kaspar Fischer, Introduction to Alpha Shapes
- Edelsbrunner, H., & Mücke, E. P. (1994). Three-dimensional alpha shapes. ACM Transactions on Graphics (TOG), 13(1), 43-72.
- Bernardini, F. & Bajaj, C. (1997). Sampling and reconstructing manifolds using alpha-shapes. Technical Report CSD-TR-97-013, Dept. Comput. Sci., Purdue Univ., West Lafayette, IN.
- Segment Trees
Date: March 25, 2019
- 3D Convex Hulls
Date: March 27, 2019
- Binary Space Partitions
Date: April 01, 2019
- Mount, Lecture 31 (pg. 163-169)
- Arya, S., Mount, D. M., Netanyahu, N. S., Silverman, R., & Wu, A. Y. (1998). An optimal algorithm for approximate nearest neighbor searching fixed dimensions. Journal of the ACM (JACM), 45(6), 891-923.
- The BSP FAQ (Originally from ftp://ftp.sgi.com/other/bspfaq/)
- Motion Planning
Date: April 03, 2019
- Visibility Graphs
Date: April 10, 2019
- Surface Reconstruction
Date: April 15, 2019
- Dey, T. K., & Kumar, P. (1999). A simple provable algorithm for curve reconstruction. In Proc. 10th ACM-SIAM Sympos. Discrete Algorithms. (pp. 893-894).
- Amenta, N., Choi, S., Dey, T. K., & Leekha, N. (2002). A simple algorithm for homeomorphic surface reconstruction. International Journal of Computational Geometry & Applications, 12(01n02), 125-141.
- Amenta, N., Bern, M., & Eppstein, D. (1998). The crust and the β-skeleton: Combinatorial curve reconstruction. Graphical models and image processing, 60(2), 125-135.
- Tamal Dey - Surface Reconstruction Software and Textbook
- Edelsbrunner, H., & Shah, N. R. (1994, June). Triangulating topological spaces. In Proceedings of the tenth annual symposium on Computational geometry (pp. 285-292). ACM.
- Grad Presentations
Date: April 17, 2019
- Brian Bell: Simplicial Depth
- Kairong Jiang: Range Assignment
- Brandon Neth: Grey Linear Programming
- Brian: Cheng, A. Y., & Ouyang, M. (2001). On algorithms for simplicial depth. In CCCG (pp. 53-56).
- Brian: Liu, R. Y. (1990). On a notion of data depth based on random simplices. The Annals of Statistics, 18(1), 405-414.
- Kairong: Biniaz, A., Bose, P., Carmi, P., Maheshwari, A., Munro, J. I., & Smid, M. (2018). Faster algorithms for some optimization problems on collinear points. arXiv preprint arXiv:1802.09505.
- Kairong: Hsiao, J. Y., Tang, C. Y., & Chang, R. S. (1992). An efficient algorithm for finding a maximum weight 2-independent set on interval graphs. Information Processing Letters, 43(5), 229-235.
- Brandon: Huang, G., & Dan Moore, R. (1993). Grey linear programming, its solving approach, and its application. International journal of systems science, 24(1), 159-172.
- Brandon: Huang, G. H., Baetz, B. W., & Patry, G. G. (1994). Grey dynamic programming for waste-management planning under uncertainty. Journal of Urban Planning and Development, 120(3), 132-156.
- Grad Presentations
Date: April 22, 2019
- Ripan Chowdhury: A thorough overview of Convex Hulls
- Jackson Lindsay: Kinetic Data Structures
- Dwight Nwaigwe: A Conjectured Expected Linear Time Convex Hull Algorithm for Points Uniformly Distributed on the Unit Square
- Ripan: Kirkpatrick, D. G., & Seidel, R. (1986). The ultimate planar convex hull algorithm?. SIAM journal on computing, 15(1), 287-299.
- Ripan: Chan, T. M. (1996). Optimal output-sensitive convex hull algorithms in two and three dimensions. Discrete & Computational Geometry, 16(4), 361-368.
- Jackson: Basch, J., Guibas, L. J., & Hershberger, J. (1999). Data structures for mobile data. Journal of Algorithms, 31(1), 1-28.
- Jackson: Abam, M. A. (2007). New data structures and algorithms for mobile data Eindhoven: Technische Universiteit Eindhoven DOI: 10.6100/IR630204
See also a related poster by Mohammad Abam
- Dwight: Devroye, L., & Toussaint, G. T. (1981). A note on linear expected time algorithms for finding convex hulls. Computing, 26(4), 361-366.
- Dwight: McQueen, M. M., & Toussaint, G. T. (1985). On the ultimate convex hull algorithm in practice. Pattern Recognition Letters, 3(1), 29-34.
- Grad Presentations
Date: April 24, 2019
- Becca Faust: Bentley-Ottman Line Segment Intersection
- Craig Thompson: Euclidean Minimum Spanning Trees
- Xueheng Wan: Visualizing Convex Hull Algorithms
- 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.
- Grad Presentations
Date: April 29, 2019
- Carlos Carbajal: Implementing Convex Hulls
- Spencer Krieger: Sweep Line Algorithms
- Renee Zhang: Weighted Voronoi Diagrams
- Spencer: Vati, B. R. (1992). A generic solution to polygon clipping. Communications of the ACM, 35(7), 56-64.
- Spencer: Edelsbrunner, H., & Guibas, L. J. (1989). Topologically sweeping an arrangement. Journal of Computer and System Sciences, 38(1), 165-194.
- Renee: Aurenhammer, F., & Edelsbrunner, H. (1984). An optimal algorithm for constructing the weighted Voronoi diagram in the plane. Pattern Recognition, 17(2), 251-257.
- Renee: Aurenhammer, F. (1987). Power diagrams: properties, algorithms and applications. SIAM Journal on Computing, 16(1), 78-96.
Final project info
Proposals Due: Feb 22
- Chs. 1-2
Assigned: Jan 23
Due: Feb 06 01:59:59 PM
Graded: Feb 13
- Chs. 3-5
Assigned: Feb 06
Due: Feb 20 01:59:59 PM
Graded: Feb 27
- Chs. 6-7
Assigned: Feb 20
Due: Mar 13 01:59:59 PM
Graded: Mar 30
- Chs. 7-9
Assigned: Mar 13
Due: Mar 27 01:59:59 PM
Graded: Apr 03
- Chs. 9-11
Assigned: Mar 27
Due: Apr 10 01:59:59 PM
Graded: Apr 17
- Chs. 12-15
Assigned: Apr 10
Due: Apr 24 01:59:59 PM
Graded: May 01