Lower Bounds for Simplex Emptiness and Related Problems

Abstract

We establish new lower bounds for simplex emptiness queries in the partition graph model. Given a set $S$ of $n$ points in $\RR^d$, a data structure for simplex emptiness can report whether a query simplex contains any point in $S$. Our lower bounds are based on the lower bounds for online hyperplane emptiness problem due to Jeff Erickson in the partition graph model, and are within a polylogarithmic factor of the optimal in the plane. Previously known lower bounds for simplex emptiness were based on the rather weak lower bounds for halfspace emptiness due to Erickson in the partition graph model (only trivial lower bounds were known for $2\leq d \leq 4$). Our lower bounds automatically imply lower bounds for simplex range reporting, where a data structure has to report all $r$ points contained in the query simplex. Chazelle and Rosenberg had previously established stronger lower bounds for simplex range reporting in the more powerful pointer machine model, but unfortunately their lower bounds only hold when $r$ is sufficiently large. Simplex emptiness is a fundamental problem, and hence our new lower bounds imply lower bounds for a host of other problems in computational geometry, such as point-inclusion in union of slabs, line-nearest neighbor, segment intersection searching, implicit point location, segment dragging, halfplane proximity and convex hull queries.