Proceedings of the 34th IEEE Symposium on Foundations of Computer Science, 528-536, 1993.
Abstract:
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}.