𝗧𝗵𝗲 𝟯𝟬-𝗦𝗲𝗰𝗼𝗻𝗱 𝗠𝗶𝘀𝘁𝗮𝗸𝗲

I made a spatial search 10x faster. The map still took nearly thirty seconds to render.

At Xerox Research, I was working on a geographic information system that took about thirty seconds to draw a map. To find what belonged on screen, it checked the axis-aligned bounding box of every polyvector shape in the database against the current view.

The engineer who wrote it was brilliant and insisted this was optimal. I didn't believe him, and once he said it, I wanted to prove him wrong. It didn't hurt that this was an interesting problem.

I spent months of my own time working on it. This was before the web, and finding the right paper for an established approach was a problem in itself. The closest I found was a small example of range searching in the first edition of Sedgewick's algorithms book. It dealt with points; I needed to search regions.

My officemate and I spent many late nights at the whiteboard, working through an intuition I had: if binary search could tame a one-dimensional space by repeatedly dividing it in half, why couldn’t a similar approach work in two dimensions? The catch was that a point falls on one side of a dividing line or the other. A box can straddle it. I eventually settled on splitting the space in two, with a third branch for shapes straddling the line. If a node’s bounds couldn’t reach the view, we could skip everything beneath it.

I left Xerox Research to work on an OS/2 project at IBM, but I couldn't put the problem down. I licensed a similar dataset and finished my algorithm about a year later.

In my tests, the search ran roughly 10x faster. I had proved my point, but when I measured the whole thing, searching accounted for only about 10% of the wait. Most of the time went into drawing vectors to video memory.

I had made three seconds of work take a fraction of a second. The other twenty-seven seconds were unchanged.

I'd spent months on a difficult problem, and paid out of pocket for a dataset so I could finish it after I'd left Xerox. Somewhere along the way, making the map render faster had become proving that a better search was possible.

I shelved the work, embarrassed.

A few years later I came across a magazine article about quadtrees. A slightly different structure, but I recognized the idea behind it. I'd reasoned my way to something similar on my own.

I'm proud of that. But the person waiting for a map would barely have noticed.

I still like difficult problems, and I'm still susceptible to an elegant solution. So I try to remember to ask one question before I let a problem absorb me:

𝗜𝗳 𝗜 𝘀𝗼𝗹𝘃𝗲 𝘁𝗵𝗶𝘀, 𝗵𝗼𝘄 𝗺𝘂𝗰𝗵 𝗯𝗲𝘁𝘁𝗲𝗿 𝗱𝗼𝗲𝘀 𝘁𝗵𝗲 𝗽𝗿𝗼𝗱𝘂𝗰𝘁 𝗮𝗰𝘁𝘂𝗮𝗹𝗹𝘆 𝗴𝗲𝘁?