The N Squared Pizza Problem

An inefficient algorithm in a 3D scan-matching pipeline caused a significant memory management problem due to its N-squared complexity, similar to how a pizza's area grows with the square of its radius. This issue arose when calculating the variance between all pairs of surface normals, creating a massive memory spike for large, similar surfaces and forcing costly over-provisioning of resources. The problem was identified using high-frequency memory sampling that attributed consumption to specific jobs and stages. Four solutions were evaluated to manage the quadratic memory growth: shrinking the input, shrinking the sample, bounding the allocation, and changing the data structure. Ultimately, a block-walking approach was chosen because it guaranteed an exact result without changing the final score, prioritizing correctness over the slightly better performance of other approximation methods.