# What is a really good problem to get your hands dirty in computational-geometry?

Computational geometry is an area I find pretty interesting, and I'd like to devote about a month or two to a project that will introduce me to this and help me learn key concepts.

What is a good way to approach this and what are the key concepts I should be sure I'm introduced too?

• (tongue firmly in cheek): Read the Geomblog !! (geomblog.blogspot.com) – Suresh Venkat Oct 5 '10 at 19:16
• Are you looking for a programming project, a theoretical project, or a mixture of the two? – James King Oct 6 '10 at 13:48

To mix Suresh V.'s and Dave C.'s suggestions, it might be fun to try to gain experimental evidence on an unsolved problem by implementing the necessary algorithms. For example, it is now known that the Delaunay triangulation is not a ($\pi$/2)-spanner [Prosenjit Bose, Luc Devroye, Maarten Löffler, Jack Snoeyink, Vishal Verma: "The spanning ratio of the Delaunay triangulation is greater than $\pi$/2." CCCG 2009: 165-167.] You could implement a Delaunay triangulation algorithm, and shortest paths, and try to determine experimentally what the true spanning ratio might be. Or, more challenging, try to compute the combinatorial complexity of the Voronoi diagram of lines in $\mathbb{R}^3$, another unsolved problem (and in the list that Suresh mentions as Problem 3.)

• That last suggestion is MEAN! – Jeffε Oct 6 '10 at 4:24
• Yes, "more challenging" is an understatement! Caveat emptor! – Joseph O'Rourke Oct 6 '10 at 10:57

While this might be too daunting to jump into before you do as Dave suggests, there's a nice collection of open problems in computational geometry maintained by Joe O'Rourke, Erik Demaine and Joe Mitchell. These provide a good snapshot of core questions in the theoretical realm.

Get the book research problems in discrete geometry. Read through it, see which problems you find interesting, read the literature, solve, and publish.

Warnning: The problems in this book are hard. However, it is an excellent introduction to open problems in the field, and a good way to learn about the field.

Victor Klee in 1973 posed a problem about guarding simple polygons (sensors to protect an art gallery placed at its vertices) that has blossomed into hundreds of papers dealing with what has come to be known as the Art Gallery Problem. Many of the basic ideas in computational geometry come into play when studying the Art Gallery Problem (things such as triangulation, decomposing polygons into pieces with special properties, visibility graphs, etc.) Joe O'Rourke's wonderfully well written book still serves as a great introduction to the ideas and methods here, and the book is available in part or whole for free at this web site:

http://cs.smith.edu/~orourke/books/ArtGalleryTheorems/art.html

I think this is a great entry point into computational geometry.

• Thanks, Joe! And if I might add, there remain unsolved problems here which could fit in with my suggestion to direct your energy toward an open problem. That makes it more exciting. :-) – Joseph O'Rourke Oct 6 '10 at 18:45

Jeff Erickson "JeffE" has also a nice set of pointers on the topic: http://compgeom.cs.uiuc.edu/~jeffe/compgeom/. Since he visits TCS SE frequently, he can help you much better.

• Careful! I haven't updated that set of web pages in more than a decade!! – Jeffε Oct 6 '10 at 4:05

Buy a book such as this one, implement the algorithms, and find out some example or small project to work on from the exercise section. Here and here are lists of many project ideas. Google ought to reveal many others. Pick one that sounds fun and go for it.