A Greedy Algorithm for Low-Crossing Partitions for General Set Systems

2024-07-18

Simplicial partitions are a fundamental structure in computational geometry. They form the basis of optimal data structures for range searching and several related problems. The known efficient algorithms are built on very specific spatial partitioning tools tailored for certain geometric cases. This severely limits their applicability to general set systems. In this work, we propose a simple greedy heuristic for constructing simplicial partitions of any set system. We present a thorough empirical evaluation of its behavior on a variety of geometric and non-geometric set systems, showing that it performs surprisingly well on most instances. The C++ implementation of these algorithms is available on Gitlab.