Instructor: Joshua A. Levine
Office: 754 GouldSimpson
Meets: M/W 2:003:15pm, 222 Social Sciences
Office Hours: M 3:304:30pm, T 4:305:30pm (GS 754), or by appointment
TA: Alex Koltz, akoltz@email.arizona.edu
TA Office Hours: M 1:002:00pm (GS 938)
TA: Justin Crum, jcrum@math.arizona.edu
TA Office Hours: F 10:00am11:00am (GS 938)
Course Syllabus
D2L (for 437)
D2L (for 537)
Piazza
Course Calendar
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, 13pm, 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
Lecture 02  2D Convex Hulls
Date: January 14, 2019
Required Reading:
Optional Reading:
 Mount, Lectures 1,3 (pg. 26,1116)
 Jarvis, R. A. (1973). On the identification of the convex hull of a finite set of points in the plane. Information processing letters, 2, 1821.
 Graham, R. L. (1972). An efficient algorithm for determining the convex hull of a finite planar set. Info. Pro. Lett., 1, 132133.
 Chan, T. M. (1996). Optimal outputsensitive convex hull algorithms in two and three dimensions. Discrete & Computational Geometry, 16(4), 361368.
 Many variants referenced in BCKO, Section 1.5
Lecture 03  Line Segment Intersection
Date: January 16, 2019
Required Reading:
Optional Reading:
Lecture 04  Overlay of Subdivisions
Date: January 23, 2019
Required Reading:
Optional Reading:
 Mount, Lecture 23 (pg. 134137)
 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), 217236.
 Wingededge data structure: Baumgart, B. G. (1975, May). A polyhedron representation for computer vision. In Proceedings of the May 1922, 1975, national computer conference and exposition (pp. 589596). ACM.
Lecture 05  Polygon Triangulation
Date: January 28, 2019
Required Reading:
Optional Reading:
 Mount, Lecture 6 (pg. 3238)
 Garey, M. R., Johnson, D. S., Preparata, F. P., & Tarjan, R. E. (1978). Triangulating a simple polygon. Inform. Process. Lett., 7, 175179.
 Lee, D. T., & Preparata, F. P. (1977). Location of a point in a planar subdivision and its applications. SIAM Journal on computing, 6(3), 594606.
 A particularly famous solution: Chazelle, B. (1991). Triangulating a simple polygon in linear time. Discrete & Computational Geometry, 6(3), 485524.
Lecture 06  lowD Incremental LP
Date: January 30, 2019
Required Reading:
Optional Reading:
Lecture 07  lowD Randomized LP
Date: February 04, 2019
Required Reading:
Optional Reading:
Lecture 08  Range Trees
Date: February 06, 2019
Required Reading:
Optional Reading:
 Mount, Lectures 31,32 (pg. 163174)
 Bentley, J. L. (1975). Multidimensional binary search trees used for associative searching. Communications of the ACM, 18(9), 509517.
 Chazelle, B., & Guibas, L. J. (1986). Fractional cascading: I. A data structuring technique. Algorithmica, 1(14), 133162.
 Chazelle, B., & Guibas, L. J. (1986). Fractional cascading: II. applications. Algorithmica, 1(14), 163191.
Lecture 09  Trapezoidal Maps
Date: February 11, 2019
Required Reading:
Optional Reading:
Lecture 10  Point Location
Date: February 13, 2019
Required Reading:
Optional Reading:
Lecture 11  Voronoi Diagrams
Date: February 18, 2019
Required Reading:
Optional Reading:
Lecture 12  Variations on Voronoi
Date: February 20, 2019
Required Reading:
Optional Reading:
 Mount, Lecture 30 (pg. 160163)
 Chew, L. Paul. (1990). Building Voronoi diagrams for convex polygons in linear expected time. Technical Report PCSTR90147, Dept. Math. Comput. Sci., Dartmouth College, Hanover, NH.
 Aggarwal, A., Guibas, L. J., Saxe, J., & Shor, P. W. (1989). A lineartime algorithm for computing the Voronoi diagram of a convex polygon. Discrete & Computational Geometry, 4(6), 591604.
Lecture 13  PointLine Duality
Date: February 25, 2019
Required Reading:
Optional Reading:
Lecture 15  Line Arrangements
Date: March 11, 2019
Required Reading:
Optional Reading:
 Mount, Lecture 14 (pg. 8083)
 Edelsbrunner, H., Seidel, R., & Sharir, M. (1993). On the zone theorem for hyperplane arrangements. SIAM Journal on Computing, 22(2), 418429.
 BCKO, 8.1,8.4
 Mount, Lecture 15 (pg. 8390)
 Edelsbrunner, H., & Guibas, L. J. (1989). Topologically sweeping an arrangement. Journal of Computer and system sciences, 38(1), 165194.
Lecture 16  Delaunay Triangulations
Date: March 13, 2019
Required Reading:
Optional Reading:
Lecture 17  Delaunay, Part 2
Date: March 18, 2019
Required Reading:
Optional Reading:
Lecture 18  Alpha Hulls
Date: March 20, 2019
Required Reading:
Optional Reading:
 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). Threedimensional alpha shapes. ACM Transactions on Graphics (TOG), 13(1), 4372.
 Bernardini, F. & Bajaj, C. (1997). Sampling and reconstructing manifolds using alphashapes. Technical Report CSDTR97013, Dept. Comput. Sci., Purdue Univ., West Lafayette, IN.
Lecture 19  Segment Trees
Date: March 25, 2019
Required Reading:
Optional Reading:
Lecture 20  3D Convex Hulls
Date: March 27, 2019
Required Reading:
Optional Reading:
Lecture 21  Binary Space Partitions
Date: April 01, 2019
Required Reading:
Optional Reading:
 Mount, Lecture 31 (pg. 163169)
 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), 891923.
 The BSP FAQ (Originally from ftp://ftp.sgi.com/other/bspfaq/)
Lecture 22  Motion Planning
Date: April 03, 2019
Required Reading:
Optional Reading:
Lecture 24  Visibility Graphs
Date: April 10, 2019
Required Reading:
Optional Reading:
Lecture 25  Surface Reconstruction
Date: April 15, 2019
Required Reading:
 Dey, T. K., & Kumar, P. (1999). A simple provable algorithm for curve reconstruction. In Proc. 10th ACMSIAM Sympos. Discrete Algorithms. (pp. 893894).
 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), 125141.
Optional Reading:
 Amenta, N., Bern, M., & Eppstein, D. (1998). The crust and the βskeleton: Combinatorial curve reconstruction. Graphical models and image processing, 60(2), 125135.
 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. 285292). ACM.
Lecture 26  Grad Presentations
Date: April 17, 2019
Presentations:
 Brian Bell: Simplicial Depth
 Kairong Jiang: Range Assignment
 Brandon Neth: Grey Linear Programming
Optional Reading:
 Brian: Cheng, A. Y., & Ouyang, M. (2001). On algorithms for simplicial depth. In CCCG (pp. 5356).
 Brian: Liu, R. Y. (1990). On a notion of data depth based on random simplices. The Annals of Statistics, 18(1), 405414.
 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 2independent set on interval graphs. Information Processing Letters, 43(5), 229235.
 Brandon: Huang, G., & Dan Moore, R. (1993). Grey linear programming, its solving approach, and its application. International journal of systems science, 24(1), 159172.
 Brandon: Huang, G. H., Baetz, B. W., & Patry, G. G. (1994). Grey dynamic programming for wastemanagement planning under uncertainty. Journal of Urban Planning and Development, 120(3), 132156.
Lecture 27  Grad Presentations
Date: April 22, 2019
Presentations:
 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
Optional Reading:
 Ripan: Kirkpatrick, D. G., & Seidel, R. (1986). The ultimate planar convex hull algorithm?. SIAM journal on computing, 15(1), 287299.
 Ripan: Chan, T. M. (1996). Optimal outputsensitive convex hull algorithms in two and three dimensions. Discrete & Computational Geometry, 16(4), 361368.
 Jackson: Basch, J., Guibas, L. J., & Hershberger, J. (1999). Data structures for mobile data. Journal of Algorithms, 31(1), 128.
 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), 361366.
 Dwight: McQueen, M. M., & Toussaint, G. T. (1985). On the ultimate convex hull algorithm in practice. Pattern Recognition Letters, 3(1), 2934.
Lecture 28  Grad Presentations
Date: April 24, 2019
Presentations:
 Becca Faust: BentleyOttman 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), 643647.
 Becca: Boissonnat, J. D., & Preparata, F. P. (2000). Robust plane sweep for intersecting segments. SIAM Journal on Computing, 29(5), 14011421.
 Craig: Graham, R. L., & Hell, P. (1985). On the history of the minimum spanning tree problem. Annals of the History of Computing, 7(1), 4357.
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. 455458). 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), 469483.
Lecture 29  Grad Presentations
Date: April 29, 2019
Presentations:
 Carlos Carbajal: Implementing Convex Hulls
 Spencer Krieger: Sweep Line Algorithms
 Renee Zhang: Weighted Voronoi Diagrams
Optional Reading:
 Carlos:
 Spencer: Vati, B. R. (1992). A generic solution to polygon clipping. Communications of the ACM, 35(7), 5664.
 Spencer: Edelsbrunner, H., & Guibas, L. J. (1989). Topologically sweeping an arrangement. Journal of Computer and System Sciences, 38(1), 165194.
 Renee: Aurenhammer, F., & Edelsbrunner, H. (1984). An optimal algorithm for constructing the weighted Voronoi diagram in the plane. Pattern Recognition, 17(2), 251257.
 Renee: Aurenhammer, F. (1987). Power diagrams: properties, algorithms and applications. SIAM Journal on Computing, 16(1), 7896.

Final project info for 537
students
Proposals Due: Feb 22
Homework 1
 Chs. 12
Assigned: Jan 23
Due: Feb 06 01:59:59 PM
Graded: Feb 13
Homework 2
 Chs. 35
Assigned: Feb 06
Due: Feb 20 01:59:59 PM
Graded: Feb 27
Homework 3
 Chs. 67
Assigned: Feb 20
Due: Mar 13 01:59:59 PM
Graded: Mar 30
Homework 4
 Chs. 79
Assigned: Mar 13
Due: Mar 27 01:59:59 PM
Graded: Apr 03
Homework 5
 Chs. 911
Assigned: Mar 27
Due: Apr 10 01:59:59 PM
Graded: Apr 17
Homework 6
 Chs. 1215
Assigned: Apr 10
Due: Apr 24 01:59:59 PM
Graded: May 01
