How can I make this change the voronoi chart grid?

Question

I have a problem that reminds me of Voron, but I hope that my variation will allow me to avoid using the Voronoi algorithm and write something faster.

Here is a terrible image I made in Paint to illustrate my problem:

Say I have a map area. Each dot represents a store. Each square represents a neighborhood. The voronoi chart shows the areas closest to each store.

If one of these areas dominates the square, then this entire area belongs to this store.

Is it possible to determine which squares belong to that store without having to calculate an intermediate raven chart? It seems that since this looks like a very rough approximation of the voronoi diagram, there must be a super fast shortcut to create it.

Answer 1

Maybe I don’t understand, but can you just find the peak that is closest to the centroid of each square?

@ user2615897 indicates that this is not entirely correct (see comment). However, I think this would be a good approximation for a grid that looks like your example (in particular: approximately the same cells with distances comparable to square dimensions).

My intuition is that without an explicit charting, any approach would only be an approximation ... but I'm not sure.

This (segment) configuration shows the point: The red peak is closest to the center of the central square, and the green peak belongs to the square itself.