Syllabus
This is an introductory course on computational geometry and its applications. We will discuss techniques needed in designing and analyzing efficient algorithms and data structures for computational problems in discrete geometry, such as convex hulls, geometric intersections, geometric structures such as Voronoi diagrams and Delaunay triangulations, arrangements of lines and hyperplanes, and range searching.
Prerequisites
CMSC451 (Algorithms) and CMSC420 (Advanced Data Structures) or permission of instructor.
- Knowledge of basic algorithm design techniques, such as divide-and-conquer, greedy algorithms, dynamic programming.
- Knowledge of basic analysis techniques such as asymptotic notation, solving summations and recurrences, basic probability theory.
- Knowledge of basic data structures (e.g. balanced binary trees, heaps, and hashing).
If you are unsure whether you satisfy the course prerequisites, please check with me.
Course Work
Course grades will be based on written homeworks (roughly 4 of them), a midterm exam, and a comprehensive final exam. (There will be no programming assignments.) Tentative weights: Homeworks: 35%, Midterm: 25%, Final: 40%.
Attendance will be required for the midterm exam and the final exam. The midterm is tentatively scheduled to take place in class on Thu, Oct 19. The final exam is scheduled for Thu, Dec 14, 8am - 10am.
Normally, late homeworks will not be accepted (because solutions will be discussed in class). If you feel that you have a legitimate excuse for handing in a homework late, contact me at least 48 hours before the due date. All homework assignments are to be done individually, but discussion with classmates regarding general solution strategies is allowed.
Piazza
We will be using Piazza for class discussions and important class announcements. Rather than sending email to the instructor or TA, you are encouraged to post your questions to Piazza, which will allow everyone (instructor, TA, and classmates) to view and respond to your question and the answers posted. (If you have a question of a more private nature, you can send email directly to us.) We will be sending out invitations to the class to join Piazza, but feel free to enroll in the class at any time by going to this Piazza sign-up link.
Topics
The following list is tentative, and the order of topics may be changed.
- Preliminaries: Basic Euclidean geometry
- Hulls: Convex hull algorithms (Graham's algorithm, Jarvis's algorithm, Chan's algorithm)
- Linear Programming: Half-plane intersection, point-line duality, randomized LP, backwards analysis, applications of low-dimensional LP
- Intersections and Triangulation: Plane-sweep line segment intersection, triangulation of monotone subdivisions, plane-sweep triangulation of simple polygons
- Point Location: Trapezoidal decompositions and analysis, history DAGs
- Voronoi Diagrams: Basic definitions and properties, Fortune's algorithm
- Delaunay Triangulations: Point set triangulations, basic definition and properties, randomize incremental construction and analysis
- Arrangements and Duality: incremental construction of arrangements and the zone-theorem, applications
- Geometric Data Structures: kd-trees, range trees and range searching, segment trees
- Geometric Approximation: Dudley's theorem and applications, well-separated pair decompositions and geometric spanners, VC dimension, epsilon-nets and epsilon-approximations
- Computational Topology: Simplicial complexes, continuous maps and homeomorphisms, review of algebra and homology, nerves, filtrations, applications to shape analysis
Text and Resources
There is no required text. The books below are suggested reference material. Of course, there is lots of information on the Web.
- Computational Geometry: Algorithms and Applications (3rd Edition), M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars, Springer-Verlag, 2008.
- Geometric Approximation Algorithms, S. Har-Peled, American Mathematical Society, 2010.
- Lectures on Discrete Geometry, J. Matousek, Springer, 2002.
- Foundations of Multidimensional and Metric Data Structures, H. Samet, Morgan-Kaufman, 2006.
Lecture Videos
Screen and audio-capture of every lecture will made available via Panopto on the class ELMS page. Videos should be released within 24 hours of each lecture. If a video does not appear, please let me know.
Excused Absences
Any student who needs to be excused for an absence from a single lecture or lab due to illness shall:
- Make a reasonable attempt to inform the instructor of his/her illness prior to the class.
- Upon returning to the class, present their instructor with a self-signed note attesting to the date of their illness. Each note must contain an acknowledgment by the student that the information provided is true and correct. Providing false information to University officials is prohibited under Part 9(h) of the Code of Student Conduct (V-1.00(B) University of Maryland Code of Student Conduct) and may result in disciplinary action.
Missing an exam for reasons such as illness, religious observance, participation in required university activities, or family or personal emergency (such as a serious automobile accident or close relative's funeral) will be excused so long as the absence is requested in writing at least 2 days in advance of the exam date and the student includes documentation that shows the absence qualifies as excused. A self-signed note is not sufficient, as exams are major scheduled grading events.
For medical absences, you must furnish documentation from the health care professional who treated you. This documentation must verify dates of treatment and indicate the time-frame that the student was unable to meet academic responsibilities. In addition, it must contain the name and phone number of the medical service provider to be used if verification is needed. No diagnostic information will ever be requested. Note that simply being seen by a health care professional does not constitute an excused absence; it must be clear that you were unable to perform your academic duties.
It is the University's policy to provide accommodations for students with religious observances conflicting with exams, but it is the your responsibility to inform the instructor in advance of intended religious observances. If you have a conflict with one of the planned exams, you must inform the instructor prior to the end of the first two weeks of the class.
For missed exams due to excused absences, the instructor will arrange a makeup exam. If you might miss an exam for any other reason other than those above, you must contact the instructor in advance to discuss the circumstances. We are not obligated to offer a substitute assignment or to provide a makeup exam unless the failure to perform was due to an excused absence.
The policies for excused absences do not apply to project assignments. Projects will be assigned with sufficient time to be completed by students who have a reasonable understanding of the necessary material and begin promptly. In cases of extremely serious documented illness of lengthy duration or other protracted, severe emergency situations, the instructor may consider extensions on project assignments, depending upon the specific circumstances.
Besides the policies in this syllabus, the University's policies apply during the semester. Various policies that may be relevant appear in the Undergraduate Catalog.
If you experience difficulty during the semester keeping up with the academic demands of your courses, you may consider contacting the Learning Assistance Service. Their educational counselors can help with time management issues, reading, note-taking, and exam preparation skills.
Students with Disabilities
Students with disabilities who have been certified by University's Accessibility & Disability Service as needing any type of special accommodations should see the instructor as soon as possible during the schedule adjustment period (the first two weeks of class). Please provide ADS's letter of accommodation to the instructor at that time.
All arrangements for exam accommodations as a result of disability must be made and arranged with the instructor at least three business days prior to the exam date; later requests (including retroactive ones) will be refused.
UMD Policies for Undergraduate Students
Please refer to the University's guide on Course Related Policies, which provides you with resources and information relevant to your participation in a UMD course.
Academic Integrity
The Campus Senate has adopted a policy asking students to include the following statement on each examination or assignment in every course: "I pledge on my honor that I have not given or received any unauthorized assistance on this examination (or assignment)." Consequently, you will be requested to include this pledge on each exam and assignment. Please also carefully read the Office of Information Technology's policy regarding acceptable use of computer accounts.
Assignments and projects are to be completed individually. Therefore, cooperation with others or use of unauthorized materials or services (including both human and chatbots, such as ChatGPT) on assignment or projects is a violation of the University's Code of Academic Integrity. Both the person receiving assistance and the person providing assistance are in violation of the honor code. Any evidence of this, or of unacceptable use of computer accounts, use of unauthorized materials or cooperation on exams or quizzes, or other possible violations of the Honor Code, will be submitted to the Student Honor Council, which could result in an XF for the course, suspension, or expulsion.
- For learning the course concepts, students are welcome to study together or to receive help from anyone else. You may discuss with others the assignment or project requirements, the features of the programming languages used, what was discussed in class and in the class web forum, and general syntax errors.
- When it comes to actually writing an assignment, other than help from the instructional staff, assignments must solely and entirely be your own work. Working with another student or individual, or using anyone else's work in any way except as noted in this paragraph, is a violation of the code of academic integrity and will be reported to the Honor Council. You may not discuss design of any part of an assignment with anyone except the instructor and teaching assistants. You may not use any disallowed source of information in creating either the design or code. When writing assignment you are free to use ideas or short fragments of code from published textbooks or publicly available information, but the specific source must be cited in a comment in the relevant section of the program.
Violations of the Code of Academic Integrity may include, but are not limited to:
- Failing to do all or any of the work on a project by yourself, other than assistance from the instructional staff.
- Using any ideas or any part of another person's project, or copying any other individual's work in any way.
- Giving any parts or ideas from your project, including test data, to another student.
- Allowing any other students access to your program on any computer system.
- Posting solutions to your projects to publicly-accessible sites, e.g., on github.
- Transferring any part of an assignment or project to or from another student or individual by any means, electronic or otherwise.
If you have any question about a particular situation or source then consult with the instructors in advance. Should you have difficulty with a programming assignment you should see the instructional staff in office hours, and not solicit help from anyone else in violation of these rules.
It is the responsibility, under the honor policy, of anyone who suspects an incident of academic dishonesty has occurred to report it to their instructor, or directly to the Honor Council.
Every semester the department has discovered a number of students attempting to cheat on assignments, in violation of academic integrity requirements. Students' academic careers have been significantly affected by a decision to cheat. Think about whether you want to join them before contemplating cheating, or before helping a friend to cheat.
You may not share, discuss, or compare assignment solutions even after they have been graded since later assignments may build upon earlier solutions.
Right to Change Information
Although every effort has been made to be complete and accurate, unforeseen circumstances arising during the semester could require the adjustment of any material given here. Consequently, given due notice to students, the instructors reserve the right to change any information on this syllabus or in other course materials. Such changes will be announced and prominently displayed at the top of the syllabus.