Luke, I think that sounds like a great project, and we'd be happy to have you as a mentor. Would you be willing to post on the projects page here: https://svn.boost.org/trac/boost/wiki/SoC2010 2D medial axis, veronoi diagrams and delaunay triangulation are three
classical problems in computational geometry. Veronoi diagrams are well known to be the dual graph of delaunay triangulation, so if you solve one you have solved the other. Medial axis is also related to the other two because it can also be solved with sweepline. All three could be solved by a single generic-parameterized implementation of a sweepline algorithm. These problems are difficult to solve primarily due to numerical robustness challenges. If we limit the scope of the problem to inputs with integer coordinates only the numerical robustness challenge is much reduced. I'd be willing to mentor a student to work on solving these classical computational geometry problems as an extension to the features provided by my Boost.Polygon library. This would be a natural extension on the existing functionality provided by Boost.Polygon (it came up during review to ask if I planned on implementing them.) Since my library already provides algorithms that require integer coordinates it is acceptable to me to have extensions with that limitation. I don't believe it is reasonable to expect a student to solve the floating point versions of these problems (with an efficient implementation) in a single summer, but for integer coordinates a strong student could succeed with some expert guidance.
Andrew Sutton andrew.n.sutton@gmail.com