Techniques for refining or constraining a Voronoi diagram? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T08:37:25Z http://mathoverflow.net/feeds/question/103053 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/103053/techniques-for-refining-or-constraining-a-voronoi-diagram Techniques for refining or constraining a Voronoi diagram? Alex Milowski 2012-07-24T22:11:48Z 2012-07-25T00:10:27Z <p>I have a dataset coming from weather stations where each vertex used to generate the Voronoi diagram is the lat/long of the station. As such, each cell represents the area whose weather is being reported by the station. I'd like to limit the diameter of each cell to a reasonable distance and generate additional cells for areas with limited coverage. Essentially, for sparsely covered areas I want cells I can associate with either no data or estimated values.</p> <p>I'm currently using Fortune's algorithm to generate the diagram.</p> <p>What I'd like to know is what are the standard techniques for:</p> <ol> <li>limiting the diameter of a cell,</li> <li>adding points to reduce cell size?</li> </ol> <p>It seems to me that this is a refinement process of either the Voronoi diagram its dual, Delaunay triangulation. The refinement doesn't have to be ideal/optimal, just sufficiently within certain bounds (e.g. within a certain radius of the station's location).</p>