Simonson, Lucanus J wrote:
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.
I have pleasure to get familiar to some extent with Jonathan Shewchuck's work together with Martin Isenburg for LiDAR data processing and such, and it is a solid piece of complex matter indeed.
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 w ould 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.
I think this kind of clear specification of requirements from a project and mentor is in fact what candidates would eventually appreciate. Best regards, -- Mateusz Loskot, http://mateusz.loskot.net Charter Member of OSGeo, http://osgeo.org