Lower bounds for linear degeneracy testing

ABSTRACT

In the late nineties Erickson proved a remarkable lower bound on the decision tree complexity of one of the central problems of computational geometry: given n numbers, do any r of them add up to 0? His lower bound of Ω(n^⌈r/2⌉), for any fixed r, is optimal if the polynomials at the nodes are linear and at most r-variate. We generalize his bound to s-variate polynomials for s>>r. Erickson's bound decays quickly as r grows and never reaches above pseudo-polynomial: we provide an exponential improvement. Our arguments are based on three ideas: (i) a geometrization of Erickson's proof technique; (ii) the use of error-correcting codes; and (iii) a tensor product construction for permutation matrices.

REFERENCES

• 1: Arkin, E. M., Chiang, Y. -J., Held, M., Mitchell, J. S. B., Sacristan, V., Skiena, S. S., Yang, T. -C. On minimum-area hulls, Algorithmica 21 (1998), 119--136.
• 2: Barequet, G., Har-Peled, S. Polygon containment and translational min-Hausdorff-distance between segment sets are 3SUM-hard, Int. J. Comput. Geom. and App. 11 (2001), 465--474.
• 3: Antonio Hernández Barrera, Finding an o(n2 log n) Algorithm Is Sometimes Hard, Proceedings of the 8th Canadian Conference on Computational Geometry, p.289-294, August 12-15, 1996
• 4: Michael Ben-Or, Lower bounds for algebraic computation trees, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.80-86, December 1983 [doi>10.1145/800061.808735]
• 5: Anders Björner , László Lovász , Andrew C. C. Yao, Linear decision trees: volume estimates and topological bounds, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.170-177, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129730]
• 6: Prosenjit Bose , Marc J. van Kreveld , Godfried T. Toussaint, Filling Polyhedral Molds, Proceedings of the Third Workshop on Algorithms and Data Structures, p.210-221, August 11-13, 1993
• 7: Mark de Berg , Marko M. de Groot , Mark H. Overmars, Perfect binary space partitions, Computational Geometry: Theory and Applications, v.7 n.1-2, p.81-91, Jan. 1997 [doi>10.1016/0925-7721(95)00045-3]
• 8: Martin Dietzfelbinger, Lower bounds for sorting of sums, Theoretical Computer Science, v.66 n.2, p.137-155, 20 Aug. 1989 [doi>10.1016/0304-3975(89)90132-1]
• 9: Dobkin, D. P., Lipton, R. J. On the complexity of computations under varying set of primitives, Journal of Computer and Systems Science 18 (1979), 86--91.
• 10: Erickson J. Lower bounds for linear satisfiability problems, Chicago Journal of Theoretical Computer Science 8, 1999.
• 11: Jeff Erickson, New Lower Bounds for Convex Hull Problems in Odd Dimensions, SIAM Journal on Computing, v.28 n.4, p.1198-1214, Aug. 1999 [doi>10.1137/S0097539797315410]
• 12: Erickson J., Seidel, R. Better lower bounds on detecting affine and spherical degeneracies, Disc. Comput. Geom. 13 (1995) 41--57.
• 13: Fredman, M. L. How good is the information theory bound in sorting, Theoret. Comput. Sci. 1 (1976), 355--361.
• 14: Anka Gajentaan , Mark H. Overmars, On a class of O(n2) problems in computational geometry, Computational Geometry: Theory and Applications, v.5 n.3, p.165-185, Oct. 1995 [doi>10.1016/0925-7721(95)00022-2]
• 15: Dima Grigoriev , Marek Karpinski , Friedhelm Meyer auf der Heide , Roman Smolensky, A lower bound for randomized algebraic decision trees, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.612-619, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.238011]
• 16: Grigoriev, D., Karpinski, M., Vorobjov, N. Lower bound on testing membership to a polyhedron by algebraic decision and computation trees, Discrete Comput. Geom. 17 (1997), 191--215.
• 17: MacWillams, F. J., Sloane, N. J. A. The Theory of Error Correcting Codes, North Holland, 1977.
• 18: Matousek, J. On geometric optimization with few violated constraints, Disc. Comput. Geom. 14 (1995), 365--384.
• 19: Friedhelm Meyer auf der Heide, A Polynomial Linear Search Algorithm for the n-Dimensional Knapsack Problem, Journal of the ACM (JACM), v.31 n.3, p.668-676, July 1984 [doi>10.1145/828.322450]
• 20: Nagura, J. On the interval containing at least one prime number, Proc. Japan Acad. 28 (1952), 177--181.
• 21: Steele, M., Yao, A. C. Lower bounds for algebraic decision trees, Journal of Algorithms 3 (1982), 1--8.
• 22: Andrew Chi-Chih Yao, Decision tree complexity and Betti numbers, Journal of Computer and System Sciences, v.55 n.1, p.36-43, Aug. 1997 [doi>10.1006/jcss.1997.1495]
• 23: Andrew Chi-Chih Yao, Algebraic decision trees and Euler characteristics, Theoretical Computer Science, v.141 n.1-2, p.133-150, April 17, 1995 [doi>10.1016/0304-3975(94)00082-T]
• 24: Yao, A. C. DIMACS Workshop on Intrinsic Complexity of Computation, April 10--13, 2000.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Theory

Keywords:
bounds, computational geometry, linear decision trees, lower