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.

I'm currently using Fortune's algorithm to generate the diagram.

What I'd like to know is what are the standard techniques for:

- limiting the diameter of a cell,
- adding points to reduce cell size?

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).

Delaunay mesh refinement, but there the goal is to remove sharp angles in the triangulation, which is not your goal. See, e.g., iss.ices.utexas.edu/?p=projects/galois/benchmarks/… . $\endgroup$ – Joseph O'Rourke Jul 24 '12 at 23:56