Several of these sections describe efficient low-level operations. Spending energy on simple problems may seem a waste of time, so why do I do it?

I like to do geometry as simply as possible. It is a joy to make a program simultaneously smaller, faster, and more robust. All implementations are tested on the largest datasets available.

As simple as possible (but no simpler) is a theme of these data structures and algorithms. Some of these techniques, such as the uniform grid, appear almost trivially simple (tho efficient implementation is more intricate than may be apparent). They are fast only for "expected data" and are totally uninteresting to the theoreticians since the worst case performance is abysmal. The only reasons for considering them are these.

1. The set of "expected data" is large, including every real data set that I've ever tried.
2. On such data, the constant factor for the time is quite small.
3. Being so simple, they are easy to implement, correctly, and optimize. This contrasts to some asymptotically efficient algorithms that are so complicated that they have not been implemented yet.
4. Being so simple, they are also parallelizable, should parallel machines become widely used again.
5. These heuristic methods occasionally solve problems that do not have worst-case efficient methods. One example is this. Consider a set of N red line segments and N blue ones. Assume that there are probably theta(N²) red-red intersections and also theta(N²) blue-blue intersections, but you do not know them. Assume that there are probably theta(1) red-blue intersections. The problem is to find these, in theta(N) time. The closest theoretical algorithm requires knowing the red-red intersections. However, this is easy with a uniform grid, w/o knowing the red-red intersections.
6. Nevertheless, there are interesting theoretical questions in analyzing when these heuristic methods succeed and fail.