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 ℝ ^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 ℝ ^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 ℝ ^d .