Spring 2019
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, akoltz@email.arizona.edu
TA Office Hours: M 1:00-2:00pm (GS 938)
TA: Justin Crum, jcrum@math.arizona.edu
TA Office Hours: F 10:00am-11: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, 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
Lecture 02 - 2D Convex Hulls
Date: January 14, 2019
Required Reading:
Optional Reading:
- 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
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. 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.
Lecture 05 - Polygon Triangulation
Date: January 28, 2019
Required Reading:
Optional Reading:
- 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.
Lecture 06 - low-D Incremental LP
Date: January 30, 2019
Required Reading:
Optional Reading:
Lecture 07 - low-D 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. 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.
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. 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.
Lecture 13 - Point-Line 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. 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.
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). 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.
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. 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/)
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 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.
Optional Reading:
- 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.
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. 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.
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), 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.
Lecture 28 - Grad Presentations
Date: April 24, 2019
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.
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), 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
for 537
students
Proposals Due: Feb 22
Homework 1
- Chs. 1-2
Assigned: Jan 23
Due: Feb 06 01:59:59 PM
Graded: Feb 13
Homework 2
- Chs. 3-5
Assigned: Feb 06
Due: Feb 20 01:59:59 PM
Graded: Feb 27
Homework 3
- Chs. 6-7
Assigned: Feb 20
Due: Mar 13 01:59:59 PM
Graded: Mar 30
Homework 4
- Chs. 7-9
Assigned: Mar 13
Due: Mar 27 01:59:59 PM
Graded: Apr 03
Homework 5
- Chs. 9-11
Assigned: Mar 27
Due: Apr 10 01:59:59 PM
Graded: Apr 17
Homework 6
- Chs. 12-15
Assigned: Apr 10
Due: Apr 24 01:59:59 PM
Graded: May 01
|