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

Subject: Re: [boost] [SoC] Summer of Code Project Ideas -- Polygon
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2010-03-10 14:07:40

Andrew Sutton wrote:
>> 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. 
> 
> 
> I posted this much as a project idea on the wiki. I hope that a good
> proposal would address the issues regarding floating point problems.
> Plus, I would think that somebody would find your on the problem
> comments and integrate them into their proposal.

I think that paragraph on its own is good enough to communicate the problem statement.  I know if I were a student I'd just at that.

I really want to underscore the difficulty in implementing (for exmaple) medial axis that is robust to floating point numerical issues.  Fernando's contribution to the CGAL project was exactly that and I think he can attest to the fact that it is not a summer project.  If we think back to Triangle and Shewchuk's use of Priest's expansions to implement Delaunay triangulation it was more than a summer project and there are very few students like Shewchuck out there.  Even my proposal for robust integer coordinate algorithms is an extremely challenging project that would require a solid three months of effort from a student who is a very strong programmer with quite a bit of coaching from me and code reuse from Boost.Polygon.  It is likely that students would propose to implement a floating point implementation that is not robust and allow the user to parameterize the coordinate type to allow infinite precision floating point coordinates to be used to achieve robustness.  That would be a good student project, but not what I would like to see in boost, and I think Fernando would agree.  It does not constitute a solution to numerical robustness to rely heavily on infinite precision floating point because the runtime implications are easy two orders of magnitude.

This is a conversation I'll have to have with any students who submit proposals for implementing these algorithms.  There is a danger that the student will not be able to gauge difficulty or time required to implement their proposal and we would need to negotiate and compromise on a set of objectives and schedule for the project that is realistic but also worthwhile.  

Regards,
Luke