An uninflatable polyhedron

Computational Geometry

CS 598 JE, Spring 2008

WF 12:30-1:45, 1302 Siebel Center
Instructor: Jeff Erickson

· Home · Course Announcement · Schedule · Homeworks · References · Administrivia ·



Please typeset your homework solutions using LaTeX, with each numbered problem starting on a new page. You can submit your solutions either by emailing me a pdf file or by handing me a stapled pile of thinly-shaved, bleached, and slightly dirty dead trees.

Each student must turn in his or her own solutions. However, I strongly encourage you to work together in groups. You may use any resource at your disposal—human, printed, or electronic—but you must not copy anything verbatim, and you must cite every source you use, including the other students you work with. Please cite your sources in enough detail for the reader to find them. In other words, follow the same standards of scholarship you would use for a research paper.

Stars indicate problems that I don't already know how to solve. The problem might be open, or I might just be missing something obvious. I do not really expect anyone to solve these problems, but I've been wrong before. Please make an honest attempt.


Since this is a computational geometry class, your homework solutions (and scribe notes, and project reports) will almost certainly contain lots of figures. I strongly recommend using a vector-graphics program that can export Encapsulated PostScript (.eps) or Portable Document Format (.pdf) documents.

I use both OmniGraffle and Adobe Illustrator on my Mac; your advisor can buy Illustrator for $100 through the CITES Webstore. LineForm looks interesting, but I haven't tried it. InkScape and Ipe are both reasonable open-source programs that run on any platform. I can't recommend anything specifically for Windows (except installing Linux or buying a Mac).

To include .eps or .pdf figures in your latex document, add the line \usepackage{graphicx} (yes, with an X) just after \documentclass{...}. Then the command \includegraphics[height=1.5in]{foo} includes the file "foo.eps" (if you compile with latex) or "foo.pdf" (if you compile with pdflatex), scaled proportionately to a height of 1.5 inch.

If you prefer describing your pictures directly in your latex file instead of drawing and importing them, check out TikZ and PGF.

Submitted Project Problems

Nothing yet. Stay tuned!

About the Projects

Each student will submit an interesting, non-trivial, and preferably open problem related to computational geometry. Submitted problems need not be limited to the topics covered in class, but they must have some geometric content. Experimental problems and problems related to your own primary research area are especially welcome. Above all, it should be a problem who solution you want to know but don't.

Before the end of the semester, teams of up to three students will submit solutions for a small subset of the submitted problems, preferably excluding their own. Students are encouraged to collaborate with anyone in or out of class (with proper credit, of course). Each team will also give a short oral presentation of their results.

The ideal result of the project is something that can be polished into a publishable paper. This ideal is meant to be an attractive goal, not an absolute requirement—not all research is successful! If you do not find a complete solution, your writeup and presentation should describe partial results, promising approaches for solving the problem(s), and ideas that looked promising but weren't (and why).

Hey, wait! How do we find good problems?

Excellent question! Here are a few hopefully useful suggestions. This list is nowhere near exhaustive, nor will every suggestion work equally well (or at all) for everybody. If you have other ideas for finding good research problems, I'd love to hear them!