Comment Comment by modalduality Another particular interesting representation is Guibas and Stolfi's "quadedge" data structure from their 1985 paper at "Primitives for the manipulation of general subdivisions and the computation of Voronoi," source http://dl.acm.org/citation.cfm?doid=282918.282923 and pdf at http://www.sccg.sk/~samuelcik/dgs/quad_edge.pdf.It really is an elegant use of some basic topology with impressive results, a full Voronoi/Delaunay linear-log time algorithm in less than a page of easily implementable pseudocode (once the data structure is written). parent modalduality 9 years ago
It really is an elegant use of some basic topology with impressive results, a full Voronoi/Delaunay linear-log time algorithm in less than a page of easily implementable pseudocode (once the data structure is written).