Final project ideas - computational geometry

Question

Next semester I am teaching (the programming part) of a course in Computational Geometry. There are 14 weeks of class, two "pure theory/blackboard" hours per week, one "theory/blackboard exercises" hour per week and one "computer lab" hour per week.

My intention for the "computer lab" sessions is that the students work (almost from day one) on a programming project that they can submit at the end of the course. My thoughts for the structure and evaluation of the projects are more or less the same than in this link. To sum up: students can either design a graphical applet that illustrates some algorithm, work on an open problem or develop an application of Computational Geometry to other areas.

However, I am not an expert in Computational Geometry and I would like you to give me some suggestions of interesting topics for the final projects.

Let me give some context for the level of the projects:

• The students are 4th-year (that's last year in Spain) undergraduates in Mathematics. Their programming background is a two-semester course on basic programming in Python and two one-semester courses on Numerical Analysis where they did some programming in Matlab. Some of them have a wider background and a small fraction of them are also last-year Computer Science undergraduates.

• The textbook we are going to follow is: A Short Course in Computational Geometry and Topology by H. Edelsbrunner. (The theory professor chose it).

In previous years this course has been Machine-Learning-oriented, so I might also suggest some projects related with ML.

Answer 1

Although The Open Problems Project has grown a bit out-of-date, we recently moved it to github to improve updating. Because it was "originally aimed to record important open problems of interest to researchers in computational geometry and related fields," it has a slant appropriate for your purposes.

A typical problem is this, proposed by R. Nandakumar:

• Problem 67: Fair Partitioning of Convex Polygons.

     

Figure from: Bárány, Imre, Pavle Blagojević, and András Szűcs. "Equipartitioning by a convex 3-fan." Advances in Mathematics 223, no. 2 (2010): 579-593. DOI.