Better lower bounds on detecting affine and spherical degeneracies
- 30 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 528-536
- https://doi.org/10.1109/sfcs.1993.366834
Abstract
We show that in the worst case, /spl Omega/(n/sup d/) sidedness queries are required to determine whether a set of n points in R/sup 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 /spl Omega/(n/sup 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 /spl Omega/(n/sup d/) lower bound on the number of sidedness queries required to determine the order type of a set of n points in R/sup d/. Using similar techniques, we also show that /spl Omega/(n/sup d+1/) in-sphere queries are required to decide the existence of spherical degeneracies in a set of n points in R/sup d/.Keywords
This publication has 9 references indexed in Scilit:
- On the Zone Theorem for Hyperplane ArrangementsSIAM Journal on Computing, 1993
- Allowable Sequences and Order Types in Discrete and Computational GeometryPublished by Springer Nature ,1993
- Lower bounds for sorting of sumsTheoretical Computer Science, 1989
- Topologically sweeping an arrangementJournal of Computer and System Sciences, 1989
- Constructing Arrangements of Lines and Hyperplanes with ApplicationsSIAM Journal on Computing, 1986
- The power of geometric dualityBIT Numerical Mathematics, 1985
- Multidimensional SortingSIAM Journal on Computing, 1983
- Lower bounds for algebraic computation treesPublished by Association for Computing Machinery (ACM) ,1983
- Lower bounds for algebraic decision treesJournal of Algorithms, 1982