Better lower bounds on detecting affine and spherical degeneracies

We show that in the worst case, Omega(n^d) sidedness queries are required to determine whether a set of n points in R^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 Omega(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 Omega(n^d) lower bound on the number of sidedness queries required to determine the order type of a set of n points in R^d. Using similar techniques, we also show that Omega(n^d+1) insphere queries are required to decide the existence of spherical degeneracies in a set of n points in R^d.