CSC 437/537 - Geometric Algorithms (Spring 2019)
M/W 2:00-3:15pm, 222 Social Sciences
Course Syllabus
- Description of Course
- Course Content
- Course Policies
- Department and University Policies
- Department of Computer Science Code of Conduct
- Classroom Behavior Policy
- Threatening Behavior Policy
- Content Warning
- Accessibility and Accommodations
- Code of Academic Integrity
- UA Nondiscrimination and Anti-harassment Policy
- Additional Resources for Students
- Confidentiality of Student Records
- Subject to Change Statement
Description of Course
The study of algorithms for geometric objects, using a computational geometry approach, with an emphasis on applications for graphics, VLSI, GIS, robotics, and sensor networks. Topics may include the representation and overlaying of maps, finding nearest neighbors, solving linear programming problems, and searching geometric databases.
Course Prerequisites or Co-requisites
CSC 345 or equivalent. In particular, you should know and understand basic algorithm analysis techniques, recurrence relations, induction, sorting algorithms, hierarchical data structures (such as balanced binary search trees), graphs (and related algorithms such as Dijkstra’s algorithm), and hash tables.
Additionally, some basic knowledge in probability and statistics will be used.
Finally, you should have and expect to improve your skills at writing mathematical proofs. Consider working your way through Bruce Ikenaga’s notes and Larry Cusick’s notes and exercises for a review.
CSC 445, while recommended, is not a prerequisite. It may be taken simultaneously with this course.
Instructor and Contact Information
- Instructor: Joshua A. Levine
- Office: 754 Gould-Simpson
- Phone: +1-520-621-3153
- Email (preferred mode of communication): [username]@arizona.edu, my username is josh.
- TAs: Alex Koltz; Justin Crum
- TAs’ Email: akoltz@email.arizona.edu; jcrum@math.arizona.edu
- Office Hours: M 3:30-4:30pm, T 4:30-5:30pm (GS 754), or by appointment
- Otherwise, we can schedule an appointment (via email or private message on Piazza) to meet in my office
- Open Door Policy: if my office door is open, please feel free to stop by and inquire if I have available time. If my door is completely closed, it typically indicates I am in an (uninterruptible, except for emergencies) meeting or phone call. Please use your best discretion.
- TA Office Hours (primarily for issues with grading): Alex Koltz: M 1:00-2:00pm (GS 938); Justin Crum: F 10:00am-11:00am (GS 938)
- Otherwise, we can schedule an appointment (via email or private message on Piazza) to meet in my office
- Course Page: https://jalevine.bitbucket.io/csc437-537/
- Instructor Homepage: http://www.cs.arizona.edu/~josh
- D2L (437): https://d2l.arizona.edu/d2l/home/759216
- D2L (537): https://d2l.arizona.edu/d2l/home/759219
- Piazza: https://piazza.com/arizona/spring2019/csc437537/home
Course Format and Teaching Methods
We will employ a hybrid method that combines lectures and inquiry-based learning. The in-class experience will split time between review of required reading, group-based problem solving, and introduction of new concepts. Out-of-class activities include readings in relevant textbooks and research papers, homework exercises, and online discussions.
Course Objectives
This course will cover an overview of topics in geometric algorithms, including:
- Concepts in combinatorial geometry: polygons, polytopes, triangulations and simplicial complexes, planar and spatial subdivisions, convex hulls, intersections of half-spaces, Voronoi diagrams, Delaunay triangulations, geometric duality, arrangements of lines and hyperplanes, and Minkowski sums.
- Algorithms and analysis techniques: Sweep algorithms, incremental construction, divide-and-conquer algorithms, randomized algorithms, and backward analysis.
- Numerical predicates, constructors, degeneracies, and geometric robustness.
- Geometric data structures: doubly-connected edge lists, trapezoidal maps, conflict graphs, history DAGs, spatial search trees (a.k.a. range search), segment trees, binary space partitions, quadtrees and octrees, visibility graphs.
- Applications of geometric algorithms such as line segment intersection and overlay of subdivisions for cartography and solid modeling; triangulation for graphics, interpolation, and terrain modeling; nearest neighbor search; small-dimensional linear programming; database queries; point location queries; windowing queries; discrepancy and sampling in ray tracing; curve reconstruction and surface reconstruction; and robot motion planning.
These topics provide a broad coverage of exist research in geometric algorithms.
Expected Learning Outcomes
Students who successfully complete this course will be expected to:
- Be able to describe algorithms that provide solutions to problems involving geometric objects
- Provide proofs for the correctness of such algorithms, as well as describe both input assumptions and output characteristics.
- Provide arguments and analyses that characterize the runtime of such algorithms
- Understand the connections between real-world applications of geometric algorithms and provide abstractions that offer simplifying assumptions the translate from motivating examples to feasible approaches
- Be familiar with recent research in the area of geometric algorithms, both theoretical and applied.
Course Content
Location
- Lecture meeting time: M/W 2:00-3:15pm
- Lecture meeting location: 222 Social Sciences
Lecture Topics
Week | Date | Monday | Date | Wednesday |
1 | Jan 07 | -- No Class -- | Jan 09 | Introduction |
2 | Jan 14 | 2D Convex Hulls | Jan 16 | Line Segment Intersection |
3 | Jan 21 | -- MLK Day -- | Jan 23 | Overlay of Subdivisions |
4 | Jan 28 | Polygon Triangulation | Jan 30 | low-D Incremental LP |
5 | Feb 04 | low-D Randomized LP | Feb 06 | Range Trees |
6 | Feb 11 | Trapezoidal Maps | Feb 13 | Point Location |
7 | Feb 18 | Voronoi Diagrams | Feb 20 | Variations on Voronoi |
8 | Feb 25 | Point-Line Duality | Feb 27 | Midterm Exam |
9 | Mar 04 | -- Spring Break -- | Mar 06 | -- Spring Break -- |
10 | Mar 11 | Line Arrangements | Mar 13 | Delaunay Triangulations |
11 | Mar 18 | Delaunay, Part 2 | Mar 20 | Alpha Hulls |
12 | Mar 25 | Segment Trees | Mar 27 | 3D Convex Hulls |
13 | Apr 01 | Binary Space Partitions | Apr 03 | Motion Planning |
14 | Apr 08 | Quadtrees | Apr 10 | Visibility Graphs |
15 | Apr 15 | Surface Reconstruction | Apr 17 | Grad Presentations |
16 | Apr 22 | Grad Presentations | Apr 24 | Grad Presentations |
17 | Apr 29 | Grad Presentations | May 01 | Final Exam Review |
Required Texts and Readings
- de Berg, Cheong, van Kreveld, and Overmars Computational Geometry: Algorithms and Applications, 3rd Edition, 2008, ISBN 978-3540779735. (Note: the textbook is available electronically though the UA library). We will refer to this book as “BCKO”.
- Other handouts, research papers, and materials linked to on the course webpage
ALL REQUIRED READING SHOULD BE COMPLETED PRIOR TO THE LECTURE
Assignments and Examinations
Homework Assignments
This course will include 6 written homework assignments, typically spanning the material covered in the past 2-3 weeks of lecture. The grades for the five highest will be retained. Unless otherwise stated, these assignments should be completed individually, without the consultation or assistance from anyone but the instructor. Do not seek or obtain help from your classmates and do not offer your assistance to your classmates.
Do not read any homework solutions or seek out assistance from any external sources, answer keys, the internet, or material other than the textbook and course notes. Students suspected of violating this policy will be reported to academic integrity.
A calendar for the assignments is:
Name | Topic | Post Date | Due Date | Graded Date |
Homework 1 | Chs. 1-2 | Jan 23 | Feb 06 | Feb 13 |
Homework 2 | Chs. 3-5 | Feb 06 | Feb 20 | Feb 27 |
Homework 3 | Chs. 6-7 | Feb 20 | Mar 13 | Mar 30 |
Homework 4 | Chs. 7-9 | Mar 13 | Mar 27 | Apr 03 |
Homework 5 | Chs. 9-11 | Mar 27 | Apr 10 | Apr 17 |
Homework 6 | Chs. 12-15 | Apr 10 | Apr 24 | May 01 |
In-class Assignments
Each lecture will include a group-based problem solving session conducted using a think-pair-share model. The problem(s) considered will not be announced in advance, but will be related to the day’s reading.
After completion of the lecture, students will have 48 hours to individually write up a correct answer for the problem(s) solved in class. You must report the group that worked with in class, but your write-up should be individual work based on notes that you took and your memory.
Class Participation
This class participation grade is the instructor’s subjective judgement of the student’s contribution to a lively classroom atmosphere. He will consider mainly active, informed participation in classroom discussions and presentations. Obviously, students not attending class are not contributing in this way.
Research Project (537 only)
Students in 537 must complete a research project of their choosing. Projects will be proposed by the student and agreed upon with discussion from the instructor. Projects may come in two forms, either a term paper that summarizes (and optionally implements) the results of an existing research paper or a new research manuscript that summarizes (and optionally implements) a new technique, algorithm, or approach. For students who are electing to complete a term paper, they may choose any of the optional reading papers provided during the lecture or papers from a list provided by the instructor.
Both forms must include a 25 minute presentation that describes the research results and explains it to the class. The presentation should be in the style of a conference talk.
A project proposal is due by the end of the sixth week of class (Feb. 13).
Midterm Examination
A midterm exam will be held in class on Wed., Feb. 27, 2-3:15pm, and it will cover all material discussed in class prior to the date of the examination.
Final Examination
The final examination will be comprehensive. A review will be conducted on the final lecture.
Exam Date/Time/Location: Fri., May 3, 1-3pm, 222 Social Sciences
See also,
- UA Final Exam Regulations: https://www.registrar.arizona.edu/courses/final-examination-regulations-and-information, and
- UA Final Exam Schedule: http://www.registrar.arizona.edu/schedules/finals.htm.
Submission, Lateness, and Revision Policy
All assignments have a fixed due date. Revisions and resubmissions after grading will not be accepted.
Submission for assignments (both in-class and homework) will be due on 1:59:59PM, immediately before class begins on the due date. A late submission will not be accepted for grading without prior approval.
Course Policies
Absence and Class Participation Policy
The UA’s policy concerning Class Attendance, Participation, and Administrative Drops is available at http://catalog.arizona.edu/policy/class-attendance-participation-and-administrative-drop
The UA policy regarding absences for any sincerely held religious belief, observance or practice will be accommodated where reasonable: http://policy.arizona.edu/human-resources/religious-accommodation-policy.
Absences pre-approved by the UA Dean of Students (or dean’s designee) will be honored. See https://deanofstudents.arizona.edu/absences.
Participating in the course and attending lectures and other course events are vital to the learning process. That said, attendance is not required for lectures. To request a disability-related accommodation to this attendance policy, please contact the Disability Resource Center at (520) 621-3268 or drc-info@email.arizona.edu. If you are experiencing unexpected barriers to your success in your courses, the Dean of Students Office is a central support resource for all students and may be helpful. The Dean of Students Office is located in the Robert L. Nugent Building, room 100, or call 520-621-7057.
Nevertheless, absences may affect a student’s final course grade. Class participation is an important part of your grade in this course, and it is impossible for a student to participate and the instructor to gauge participation if a student does not attend.
Late Instructor
Your instructor will make every effort to be in class on time, or to inform you of any delay or cancellation. In the unusual event that he should not arrive in class or send word by 15 minutes from the class start time, the class is officially cancelled.
Makeup Policy for Students Who Register Late
Students who register after the first class meeting may make up missed assignments at a deadline set in consultation with the instructor.
Course Communications
We will use official UA email and Piazza as the primary mode of contact. D2L will be used only for the instructor to securely distribute grades to students.
Grading Scale and Grading Policies
Grades will be assigned based on the following scale:
- A >= 90%
- 80% <= B < 90%
- 70% <= C < 80%
- 60% <= D < 70%
- E < 60%
Grading will be based on performance on the set of homework assignments, in-class assignments, the midterm exam, the final exam, and class participation. For 437 students, this includes:
- Homework Assignments: 50%
- In-class Assignments: 15%
- Midterm Exam: 12%
- Final Exam: 18%
- Class Participation: 5%
For 537 students:
- Homework Assignments: 40%
- In-class Assignments: 15%
- Research Project: 10%
- Midterm Exam: 12%
- Final Exam: 18%
- Class Participation: 5%
Each homework assignment description will include a specific rubric for how it is graded. For 437 students, each assignment is worth 10%, and the lowest grade will be dropped. For 537 students, each assignment is worth 8% and the lowest grade will be dropped. Note that homework assignments for 437 and 537 students will include different problem sets.
In-class assignments will be graded based on submission and formatting, simply out of a score of 0, 1 or 2. There will be at most 22 in-class assignments (one per each lecture where a new topic is covered, minus exams and presentation days. Your grade will be calculated based on the 15 highest.
537 students will also complete a research project, worth 10% of your grade. This project can be selected by the student, and must, at a minimum, include both a submitted manuscript (by Apr. 29, 2019) (worth 5%) and a presentation of the project (worth 5%). Any additional artifacts or implementations will also be taking into account for the grade.
Department of Computer Science Grading Policy
- Instructors will explicitly promise when every assignment and exam will be graded and returned to students. These promised dates will appear in the syllabus, associated with the corresponding due dates and exam dates.
- Graded homework will be returned before the next homework is due.
- Exams will be returned “promptly”, as defined by the instructor (and as promised in the syllabus).
- Grading delays beyond promised return-by dates will be announced as soon as possible with an explanation for the delay.
Requests for incomplete (I) or withdrawal (W)
Request must be made in accordance with University policies, which are available at http://catalog.arizona.edu/policy/grades-and-grading-system#incomplete and http://catalog.arizona.edu/policy/grades-and-grading-system#Withdrawal, respectively.
Dispute of Grade Policy
After receiving any grade for any submission, a student has 24 hours to respond to the instructor with any disputes in an email with the subject “Grade Dispute”. Such a response must enumerate a specific set of disputed items for the submission and provide evidence that each item was improperly graded. The instructor will then completely regrade the entire submission, including both the disputed items as well as non-disputed items, with the potential for all aspects of the grade to change.
Department and University Policies
Department of Computer Science Code of Conduct
The Department of Computer Science is committed to providing and maintaining a supportive educational environment for all. We strive to be welcoming and inclusive, respect privacy and confidentiality, behave respectfully and courteously, and practice intellectual honesty. Disruptive behaviors (such as physical or emotional harassment, dismissive attitudes, and abuse of department resources) will not be tolerated. The complete Code of Conduct is available on our department web site. We expect that you will adhere to this code, as well as the UA Student Code of Conduct, while you are a member of this class.
Classroom Behavior Policy
To foster a positive learning environment, students and instructors have a shared responsibility. We want a safe, welcoming, and inclusive environment where all of us feel comfortable with each other and where we can challenge ourselves to succeed. To that end, our focus is on the tasks at hand and not on extraneous activities (e.g., texting, chatting, reading a newspaper, making phone calls, web surfing, etc.).
Students are asked to refrain from disruptive conversations with people sitting around them during lecture.
Some learning styles are best served by using personal electronics, such as laptops and iPads. Nevertheless, these devices can be distracting to other learners. While all students are welcome to use personal electronics in class, they must be used in a way that does not disrupt either the instructor or other students’ experience.
Students observed engaging in disruptive activity will be asked to cease this behavior. Those who continue to disrupt the class will be asked to leave lecture or discussion and may be reported to the Dean of Students.
Threatening Behavior Policy
The UA Threatening Behavior by Students Policy prohibits threats of physical harm to any member of the University community, including to oneself. See http://policy.arizona.edu/education-and-student-affairs/threatening-behavior-students.
Content Warning
While the instructor does not intend to include topics and/or course material includes content that are explicit or offensive in any way. The instructor will make every effort to provide advance notice when such materials may potentially be or potentially violate this intent. Please contact the instructor to discuss any content-related concerns, as alternative materials may be available.
Accessibility and Accommodations
The Disability Resources Offices provides guidelines regarding accessibility and accommodations: http://drc.arizona.edu/instructors/syllabus-statement.
Code of Academic Integrity
Students are encouraged to share intellectual views and discuss freely the principles and applications of course materials. However, graded work/exercises must be the product of independent effort unless otherwise instructed. Students are expected to adhere to the UA Code of Academic Integrity as described in the UA General Catalog. See http://deanofstudents.arizona.edu/academic-integrity/students/academic-integrity.
The University Libraries have some excellent tips for avoiding plagiarism, available at http://new.library.arizona.edu/research/citing/plagiarism. Publicly available sources for code or other material, in small amounts, may be freely used if appropriately attributed. A good rule of thumb: when in doubt about whether the use of small snippets of code not your own in a programming assignment is allowed, first ask the instructor.
Selling class notes and/or other course materials to other students or to a third party for resale is not permitted without the instructor’s express written consent. Violations to this and other course rules are subject to the Code of Academic Integrity and may result in course sanctions. Additionally, students who use D2L or UA e-mail to sell or buy these copyrighted materials are subject to Code of Conduct Violations for misuse of student e-mail addresses. This conduct may also constitute copyright infringement.
UA Nondiscrimination and Anti-harassment Policy
The University is committed to creating and maintaining an environment free of discrimination; see http://policy.arizona.edu/human-resources/nondiscrimination-and-anti-harassment-policy
Our classroom is a place where everyone is encouraged to express well-formed opinions and their reasons for those opinions. We also want to create a tolerant and open environment where such opinions can be expressed without resorting to bullying or discrimination of others.
Additional Resources for Students
UA Academic policies and procedures are available at http://catalog.arizona.edu/policies
Student Assistance and Advocacy information is available at http://deanofstudents.arizona.edu/student-assistance/students/student-assistance
Confidentiality of Student Records
Subject to Change Statement
Information contained in the course syllabus, other than the grade and absence policy, may be subject to change with advance notice, as deemed appropriate by the instructor.