CSC 437/537 - Geometric Algorithms (Spring 2019)

M/W 2:00-3:15pm, 222 Social Sciences

Course Syllabus



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

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:

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:



Course Content

Location

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

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,

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:

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:

For 537 students:

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

  1. 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.
  2. Graded homework will be returned before the next homework is due.
  3. Exams will be returned “promptly”, as defined by the instructor (and as promised in the syllabus).
  4. 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.