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

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)
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

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

See http://www.registrar.arizona.edu/personal-information/family-educational-rights-and-privacy-act-1974-ferpa?topic=ferpa

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.