This program running for several hours was something that really amazed me. As such, I decided to take a look at your source code and see how you did this. Though I don't really know ruby, I was able to make up a lot out of what I saw. I hope you don't mind me taking a moment to post my findings here.
First off, let me say that the way you reduced the problem to collision detection of bounding boxes. It is a very sound strategy and is likely to generate rather good results.
The first thing that stood out in my opinion was the fact that you are lazily generating the bounding boxes, even though you know up front that you are going to need them for each and every territory. Though this does work, just calculating the bounding boxes first removes a point where you can make mistakes (the laziness). I should add that my lack of knowledge when it comes to ruby made sure that I didn't really understand how you were doing the laziness, but I got the intention.
The other part is the actual collision detection. It is a very simplistic algorithm running in O(n^2). Because collision detection is so important in things like games, there are lots of efficient algorithms for this, including some that are still rather simple and can be implemented easily (especially when you can make some assumptions about the input, like you can with warlight maps). However, it is not entirely clear if making a more efficient solution here is actually going to improve your solution (especially since n < 3500). However, with the change suggested above, where you make the determining of the bounding boxes static instead of dynamic, it will be possible to have a progress bar for each of the two, which will make it easy to test which of the two is your bottle neck in real world examples.
I hope you can do something with my comments, but I won't be offended if you don't. I just thought I would share my findings with you.