10 Mar
2010
10 Mar
'10
2:32 p.m.
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. Andrew Sutton andrew.n.sutton@gmail.com