COMP 263: Advanced Computational Geometry, Spring 2023
Instructor:
Diane L. Souvaine
Department of Computer Science
JCC 340E
diane.souvaine "at" tufts.edu.
Office Hours: By appointment.
Prerequisites:
Comp/Math 163 or consent.
Schedule:
CS Dept Colloquia:
Thursdays, 3:00-4:15, JCC 270
Comp 263 classes:
Mondays, 3:00-4:45, JCC 402
Brief description:
This course is intended for those students who have completed a course in
computational geometry and are interested in advancing their knowledge in
this area and engaging in a research project and/or independent study.
Individuals will select a topic by studying new conference proceedings,
selecting interesting papers, reading related papers, and write up a
survey paper of the area, to include open problems as well as suggested
techniques of approaching them, or else implement algorithmic results
from the original paper and write up an analysis of its experimental
performance.
In the first half of the semester, the instructor will present
topics and results not covered in CS 163 in the fall in such areas as
geometric complexity, probabilistic algorithms, visibility and ray
shooting, immobilization, geometric data depth, range searching, k-sets,
fixed-orientation geometry, and higher-dimensional geometry.
In the
second half of the course, each student will select, in conjunction with
the instructor, a noteworthy paper from a recent conference, will research
the surrounding area and related papers, and present the topic to the rest of the class.
Then, each student will write up a survey paper of the area, to include
open problems as well as suggested techniques of approaching them, or
implement algorithmic results from the original paper and write up an
analysis of its experimental performance.
Sources:
Handouts.
Jacob Goodman and Joseph O'Rourke, Handbook of Discrete and Computational Geometry, Second
Edition, CRC Press, 2004.
Articles from journals and conference proceedings such as:
Discrete and Computational Geometry;
Computational Geometry: Theory and Applications;
Proc. of the ACM Symposium on Computational Geometry (SOCG);
Proc. of the Canadian Conference on Computational Geometry (CCCG); and
Proc of the ACM-SIAM Symposium on Discrete Algorithms (SODA).
Expected work:
Keep a journal, tracking the reading, thinking, and investigating conducted as part of this course;
Attend and participate in each class period;
Complete background reading assigned for each presentation;
Master a collection of related research papers and then implement (or test some implementation) related to these papers,
and/or investigate one or more related open problems;
Give technical presentation(s) to the class and distribute preparatory materials in advance;
Submit a final report.