Fall 2017

Instructor: Greg Aloupis

office: Halligan 210

gmail : comp163greg [please do not message me at my Tufts email]

- What I really care about:
- To succeed in this class, the student will need to already understand, or
quickly learn, the following:
big-O
notation; basic data structures such as linked lists, arrays, stacks,
balanced binary search trees; recursion, divide and conquer; proof by
induction/contradiction; basic properties and algorithms for graphs.

See the Reading page for more details on what prerequisites are needed for each topic to be covered in this class.

Programming is not required, besides a project that typically involves some implementation, although theory projects are accepted.

- To succeed in this class, the student will need to already understand, or
quickly learn, the following:
big-O
notation; basic data structures such as linked lists, arrays, stacks,
balanced binary search trees; recursion, divide and conquer; proof by
induction/contradiction; basic properties and algorithms for graphs.
- Official prerequisite
- COMP 160. Exceptions can be made; see below.
- Students may contact me requesting special permission to take COMP 163, especially if they will not have the opportunity to take it in a following year. In this case, they must have done well in COMP 15 and 61, or demonstrate suitable mathematical maturity.

Examples of topics covered (see the Reading page for more details)

- 2D convex hulls
- (the shortest path surrounding a point set or polygon)

- triangulations
- (subdividing a polygon into triangles),

- art gallery problems
- (placing cameras to guard a museum)

- farthest/closest pair
- (what two points are nearest neighbors?)

- minimum enclosing objects
- (e.g., bounding boxes)

- range searching
- (finding how many data points fall inside a given query box)

- intersection problems
- (e.g., counting intersections among rectangles)

- point location
- (determining where you are on a map)

- Voronoi diagrams
- (finding which customer regions belong to a set of vendors)

- combinatorial geometry
- (exploring patterns and properties of point sets and lines)

- data depth
- (defining and computing the center of a data set; where to place a hospital)

- the ham-sandwich theorem
- (how to fairly divide a 2-topping pizza, or a ham-and-cheese sandwich, with a single cut)

- the Borsuk-Ulam theorem
- (there are always two points on opposite sides of the planet, with equal temperature and equal pressure)

This course will help to prepare students for applications such as VLSI design, computer graphics, robotics, computer-aided design, visualization, pattern recognition, and statistics.

- Two exams; one in mid / end of October in class, and the other on the last day or during the final exam period. Each of these will be worth 20%.
- One project, involving description, visualization, and/or implementation of a research problem in computational geometry. Worth 30%. Possibility to substitute with a presentation.
- Homework assignments, worth 25%. (Note: the hw workload will be far less than in comp160)
- Participation, worth 5%.

- Copies of lecture notes and online links will be provided. The following books are not required, but might be helpful.
- Computational Geometry: Algorithms and Applications, by
de Berg, van Kreveld, Overmars, Schwarzkopf.

This is the most commonly used textbook for intro to Comp.Geom. - Computational Geometry in C, by Joseph O'Rourke