How can I make this grid variation of the voronoi diagram?

Question

I have a problem that reminds me of Voronoi, but I'm hoping that my variation will allow me to avoid using the Voronoi algorithm, and write something quicker.

Here's a horrible image I made in Paint to illustrate my problem:

Say I have an area of a map. Each dot represents a shop. Each square represents a neighbourhood. The voronoi diagram shows the areas closest to each shop.

If one of those areas dominates a square, then that whole square belongs to that shop.

Is it possible to determine which squares belong to which shop, without having to calculate an intermediate voronoi diagram? It seems as though, since this is like a very rough approximation of a voronoi diagram, there should be a super fast shortcut to generating it.

Answer 1

Perhaps I'm misunderstanding, but can't you just find the vertex which is closest to the centroid of each square?

@user2615897 points out that this isn't generally correct (see comment). None-the-less, I think it would be a good approximation for a grid which looks like your example (specifically: roughly equal-area cells, with spacings comparable to the square-sizes).

My intuition is that without explicitly constructing the diagram, any approach will only be an approximation... but I'm not sure.

This (segment) of a configuration illustrates the point: The red vertex is nearest the center of the central square, while the green-vertex owns the most area.