We're working on a facility location problem in which it is desirable for the facilities to be laid out as close as possible to a grid. In our problem, a lattice is overlaid on the region, and the centers of the resulting cells are potential facility locations.
We want the facilities to be in a regular pattern that resembles a grid. So, it is preferable to have a layout like this:
rather than one like this:
Note that the grid does not have to be the same as the lattice; that is, the following is good too:
Is there a way to evaluate how close a given set of points lies to a grid? (i.e., the "griddiness" of the set of points)
In particular, I'm looking for either a simple calculation (something involving sines and cosines...?) or an efficient algorithm that will give a score indicating how "griddy" a set of points is. Most likely we'll be using this within a heuristic (greedy + swap, metaheuristic, something like that), but bonus points if there's a method that could be incorporated into a linear MIP.
Note that we don't know in advance which "grid" the solution will resemble -- the method should be capable of determining that both the first and the third layouts are good, and the second is bad.