Welcome to MathOverflow

Question

1

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

edited Jul 25 at 0:10

Igor Rivin
31.1k●3●37●71

asked Jul 24 at 22:11

Alex Milowski
11●2

There are algorithms that go under the name of 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/… . – Joseph O'Rourke Jul 24 at 23:56

1

This might be a naive question, but why not just do a a linear scan over the cells to check whether the diameter is bounded by your bound, and if not, just throw in a few random points ("a few" depends on how big the diameter actually is, but in the most primitive version, just throw in one per large cell, then recompute (the real question is: how much do extra points cost -- this determines the tradeoff of whether you add a lot or a few points per pass). – Igor Rivin Jul 25 at 0:09

I have considered adding extra points but I was curious if there was existing research or algorithms I should consider first. Given the small size of each quadrangle dataset and the relatively static nature of their locations, it would probably be reasonable to inspect every cell and add points in a systematic fashion to get the desired results. The placement of those points will affect the size of neighboring cells but I don't think the implementation I'm using will give me the neighboring cells to make wise choices. – Alex Milowski Jul 25 at 2:36

With regards to Delaunay mesh refinement, that's an interesting idea. The sharp angles aren't really a good thing either. It might be better in the long run to remove them and use some kind of averaging process to produce fabricated data for an added cell. That adds more ideas to the stack. Thanks. – Alex Milowski Jul 25 at 2:40

1

If you have the Voronoi diagram then farthest point sampling (Delaunay refinement) seems like the obvious choice. The farthest point from a station will always be a Voronoi vertex, (or a point where a Voronoi edge intersects your quadrilateral boundary, or a corner of your boundary). Insert a new "station" at that point, and continue until the farthest point is close enough to a station. – Ramsay Jul 25 at 7:53

Techniques for refining or constraining a Voronoi diagram?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.