Re: [boost] [SoC] Summer of Code Project Ideas -- Polygon

Subject: Re: [boost] [SoC] Summer of Code Project Ideas -- Polygon
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2010-03-09 19:46:55

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_at_[hidden]