TL;DR: What's the minimum distance one has to travel to visit each node in a square matrix in which the nodes are D distance apart?
I ask because I'm working on a fun feature on how long it takes Santa to reach every child in the country, using a Travelling Salesman algorithm to map his route through the counties. But I need to estimate how long he needs to spend in each county.
For each county, we know:
The approximate number of children he needs to reach (Those age 9 and under, times the 92 percent of Americans who celebrate Christmas.)
The square mileage of the county
Given that this is mostly an exercise in TSP, I don't need a deeply precise value here. (We don't know how many children live in the same household or the specific population density of each county.) So I'm assuming the children are roughly evenly distributed across 50% of the county's land mass.
The question is: How do I approximate the time it takes to reach each node in an arbitrary amount of space, assuming those nodes are neatly positioned? (After all, we can't run a TSP for each of the 3,000+ counties as well, even if we had everyone's address!)
My best guess is to imagine the N nodes arranged in a square matrix. Then, the distance between two nodes is
sqrt(area * 0.5) / sqrt(N)--I think. Then you imagine that you (Santa) has to travel to each node. I think this is just N steps since it's a neat square martix, unless I'm deeply miscalculating the number of edges in a square matrix. Thus, I came up with:
sqrt(area * 0.5) / sqrt(N) * N
Unfortunately, it's difficult to fact-check this sort of calculation since it's imaginary!