Better lower bounds on detecting affine and spherical degeneracies

We show that in the worst case, Ω(n^d) sidedness queries are required to determine whether a set of n points in IR^d is affinely degenerate, i.e., whether it contains d+1 points on a common hyperplane. This matches known upper bounds. We give a straightforward adversary argument, based on the explicit construction of a point set containing Ω(n^d) `collapsible' simplices, any one of which can be made degenerate without changing the orientation of any other simplex. As an immediate corollary, we have an Ω(n^d) lower bound on the number of sidedness queries required to determine the order type of a set of n points in IR^d. Using similar techniques, we also show that Ω(n^d+1) in-sphere queries are required to decide the existence of spherical degeneracies in a set of n points in IR^d.