Optimal-Cost Construction of Shallow Cuttings for 3-D Dominance Ranges in the I/O-Model

Yakov Nekrich, Saladi Rahul

Shallow cuttings are a fundamental tool in computational geometry and spatial databases for solving offline and online range searching problems. For a set $P$ of $N$ points in 3-D,…