Abstract
We show that in the worst case, Ω(n d) sidedness queries are required to determine whether a set ofn points in ℝd is affinely degenerate, i.e., whether it containsd+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 ofn 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 ofn points in ℝd.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
M. Ben-Or. Lower bounds for algebraic computation trees.Proc. 15th Ann. ACM Symp. on Theory of Computing, pages 80–86, 1983.
B. Chazelle, L. J. Guibas, and D. T. Lee. The power of geometric duality.BIT, 25:76–90, 1985.
M. Dietzfelbinger. Lower bounds for sorting of sums.Theoret. Comput. Sci., 66:137–155, 1989.
H. Edelsbrunner.Algorithms in Combinatorial Geometry. EATCS Monographs on Theoretical Computer Science, vol. 10, Springer-Verlag, Heidelberg, 1987.
H. Edelsbrunner and L. J. Guibas. Topologically sweeping an arrangement.J. Comput. System Sci., 38:165–194, 1989. Corrigendum in 42:249–251, 1991.
H. Edelsbrunner, J. O'Rourke, and R. Seidel. Constructing arrangements of lines and hyperplanes with applications.SIAM J. Comput., 15:341–363, 1986.
H. Edelsbrunner, R. Seidel, and M. Sharir. On the zone theorem for hyperplane arrangements.SIAM J. Comput., 22(2):418–429, 1993.
J. Erickson and R. Seidel. Better lower bounds on detecting affine and spherical degeneracies.Proc. 34th Ann. IEEE Symp. on Foundations of Computer Science, pages 528–536, 1993.
M. L. Fredman. How good is the information theory bound in sorting?Theoret. Comput. Sci., 1:355–361, 1976.
A. Gajentaan and M. H. Overmars.n 2-hard problems in computational geometry. Report RUU-CS-93-15, Department of Computer Science, Utrecht University, Utrecht, April 1993.
J. E. Goodman and R. Pollack. Multidimensional sorting.SIAM J. Comput., 12:484–507, 1983.
J. E. Goodman and R. Pollack. Allowable sequences and order types in discrete and computational geometry. In J. Pach, editor,New Trends in Discrete and Computational Geometry, pages 103–134, Algorithms and Combinatorics, vol. 10. Springer-Verlag, New York, 1993.
J. E. Goodman, R. Pollack, and B. Sturmfels. The intrinsic spread of a configuration in ℝd.J. Amer. Math. Soc., 3:639–651, 1990.
J. M. Steele and A. C. Yao. Lower bounds for algebraic decision trees.J. Algorithms, 3:1–8, 1982.
J. van Leeuwen. Problem P20.Bull. EATCS, 19:150, 1983.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Erickson, J., Seidel, R. Better lower bounds on detecting affine and spherical degeneracies. Discrete Comput Geom 13, 41–57 (1995). https://doi.org/10.1007/BF02574027
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02574027