The Curse of The Dimensionality

Humanity had become a space-faring society when we first made contact with the aliens. We were still limited to our solar system as we still hadn’t figured out how to beat the fundamental limitations of the speed of light. It took months to travel between planets, but there were established outposts on Mars, on a few moons of Jupiter and Saturn, and on a few other asteroids.

We finally knew that we were not alone in the universe. Unfortunately, it took a bit of time to figure out a basic means of communication (they seemed to call themselves — and this is an approximation — ‘vho-gone’) and even more time to develop a cultural frame of reference. By this time, we had succeeded in insulting their Grand PooBah’s entire ancestry. To make things worse, our Ambassador was a political appointee who considered himself a ladies’ man and tried to flirt with the Grand PooBah’s daughter. He came back in pieces. We realized that the aliens did not have any concept of humor and took everything literally. Though the aliens were technologically far superior to us, they did not have any imagination. Zero. Zip. Nada.

The war had been going on for a few years now. After the initial confusion, the negotiations, and the scramble to put together a space-based military force, the advantage had slowly swung to our side. In addition to military losses, the enemy was running out of material, especially anti-matter space mines. They had now started to stretch out their reserves in a particularly ingenious way. We stumbled along this quite by accident….

One of our critical supply lines crossed the Kuiper Belt. The enemy would regularly mine the space routes that connected our production facilities with the front lines, and we faced a constant struggle to clear these mines. Our surveillance detected one of their ships traversing the Belt on a straight line path, laying mines at regular intervals. We sent one of our sweepers to clean these up. The sweeper would usually trigger the mines at a distance, but this time, something strange came up. Most of the mines were duds — and we had wasted valuable time and resources chasing them! Of course, we didn’t know which were dummy mines and which weren’t, and couldn’t risk playing probabilities. This was getting frustrating!

Given that we were dealing with a supremely uncreative species, we started analyzing which mines were armed and which were not. A new group was created for this purpose, called the ‘Figure-Out-Which-Mines-Are-Armed’ Group, to honor the literal-minded nature of our foe. We got to work on the collected data, and without the help of any of our latest quetta-zetta scale supercomputers (designed by Magrathean Corp), realized that there were special ‘marker’ mines, and armed mines were always one of $k$ mines around these. Thus, we could trace the path, identify the markers, find the $k$ nearest mines and the good ship ‘Dimensionality’ would detonate these — we could ignore the rest! Each run would place $n$ mines, and we could get by by only blowing up $k/n$ of these. And given our opponent’s pedestrian thought process, they would not think to vary this approach.

…or so we thought.

Well, actually we were right, in that they did not vary the armed/dud placement scheme. What they did do was send many ships spaced equally apart. We quickly realized that now the armed mine was not one of the $k$ mines around the marker on a single path, but was one of the $k$ mines surrounding the marker across the paths. Okay, not a big deal, we could still handle this. How much more difficult is it to calculate distances on a plane, instead of a line? Not much, not in terms of computational requirements, but we found that these were located much further apart, and it took quite a bit of reactive mass to go after the same $k$ mines. Here’s one way to think about it: Say we have to find and blow up 10% of all mines spaced equally apart on a line. We’re only traversing $k/n = 0.1$ or $10\%$ of the line to get the job done. However, if these mines are on a unit square, the target mines are in a square of side $0.1^\frac{1}{2}$, which is about $30\%$ of the total area!

After seeing that we were still countering their mines, the aliens upped the ante, this time in a completely predictable manner. They sent out a fleet of ships in a ‘square’ formation. These would travel in a straight line, laying a combination of armed and dud mines and markers. As before, the armed mines were always one of $k$ mines around the marker, but now we had to calculate spatial distances, instead of the previous planer and the yet previous linear distances. The computations were still straightforward, but the Dimensionality rose up in protest. they now had to cover nearly half the volume $0.1^\frac{1}{3}$and told us at this rate they might as well eliminate all the mines and be done with it. Because the next step would be extending the mining operation to the space-time continuum, and this would cover even more of the space. Well, of the space-time.

This came to be known as the Curse of The Dimensionality.

Postscript: Since the mines were laid at regular intervals, we just plotted our path between them and went on our merry way.