Coast to Coast Seminar Series: Live from Halifax, Nova Scotia "Cache-Oblivious Geometric Algorithms"

Abstract

Apart from main memory and disk drives, modern computers are equipped with multiple levels of cache, in order to bridge the gap between the CPU's processing speed and the access latency of main memory. Yet, traditional algorithms are not designed to take advantage of cache memory, making this strategy quite ineffective. The cache-oblivious model elegantly bridges the gap between traditional models of computation and the real world of multilevel memory hierarchies, as it allows us to design algorithms in the traditional way, yet obtain algorithms that optimally use all levels of cache that are present in the computer.

Abstractly, the idea behind cache-oblivious algorithms is to consider the memory to be one big array and to lay out the data in this array so that items that are accessed in short sequence are close to each other in this array. This talk will give a short introduction into techniques to achieve this and then move on to discussing solutions and challenges in designing such algorithms for geometric problems. This talk will focus mostly on constructing data structures for efficient range searching in the plane and, if there is time, also touch briefly on finding intersections between line segments in the plane. For range searching, the problem can be posed very naturally as finding a short sequence with certain locality properties, thereby completely abstracting away the computational process and giving rise to interesting questions in extremal combinatorics.