Coordinate representation of order types requires exponential storage

ABSTRACT

We give doubly exponential upper and lower bounds on the size of the smallest grid on which we can embed every planar configuration of n points in general position up to order type. The lower bound is achieved by the construction of a widely dispersed “rigid” configuration which is then modified to one in general position by recent techniques of Sturmfels and White, while the upper bound uses recent results of Grigor'ev and Vorobjou on the solution of simultaneous inequalities. This provides a sharp answer to a question first posed by Chazelle.

REFERENCES

• 1: L. J. Billera and B. S. Munson, Triangulations of oriented matroids and convez polytopes, SIAM J. Alg. Disc. Meth. 5 (1984), 515-525.
• 2: B. Chazelle, Problem 3-6, Third Computational Geometry Day, Courant Institute, Jan. 16, 1987.
• 3: George E. Collins, Hauptvortrag: Quantifier elimination for real closed fields by cylindrical algebraic decomposition, Proceedings of the 2nd GI Conference on Automata Theory and Formal Languages, p.134-183, May 20-23, 1975
• 4: D. P. Dobkin , D. Silver, Recipes for geometry and numerical analysis - Part I: an empirical study, Proceedings of the fourth annual symposium on Computational geometry, p.93-105, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73404]
• 5: H. Edelsbrunner , E. P. Mücke, Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms, Proceedings of the fourth annual symposium on Computational geometry, p.118-133, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73406]
• 6: J. E. Goodman and R. Pollack, Multidimensional sorting, SIAM J. Comput. 12 (1983), 484-507.
• 7: J. E. Goodman and It. Pollack, Upper bounds for configurations and polytopes in Ra, Discrete Comput. Geom. I (1986), 219- 227.
• 8: D. H. Greene and F. F. Yao, Finite-resolution computational geometry, in "2?th Annum IEEE Syrup. on the Foundations of Computer Science," 1986, pp. 143-152.
• 9: D. Yu. Grigor'ev , N. N. Vorobjov, Solving systems of polynomial inequalities in subexponential time, Journal of Symbolic Computation, v.5 n.1-2, p.37-64, February/April 1988 [doi>10.1016/S0747-7171(88)80005-1]
• 10: B. Griinbaum, "Arrangements and Spreads," Amer. Math. Soc., Providence, RI, 1972.
• 11: D. Hilbert, "The Foundations of Geometry,'' translated by E. J. Townsend, 3rd edition, Open Court, La SaUe, IL, 1938.
• 12: C. M. Hoffmann , J. E. Hopcroft , M. S. Karasick, Towards implementing robust geometric computations, Proceedings of the fourth annual symposium on Computational geometry, p.106-117, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73405]
• 13: Victor J. Milenkovic, Verifiable implementation of geometric algorithms using finite precision arithmetic, Artificial Intelligence, v.37 n.1-3, p.377-401, Dec. 1988 [doi>10.1016/0004-3702(88)90061-6]
• 14: D. Salesin , J Stolfi , L. Guibas, Epsilon geometry: building robust algorithms from imprecise computations, Proceedings of the fifth annual symposium on Computational geometry, p.208-217, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73857]
• 15: B. Sturmfels and N. White, Constructing uniform oriented matroids without the isotopy property, # 432, IMA Preprint Series, University of Minnesota.
• 16: C. K. Yap, A geometric consistency theorem for a symbolic perturbation scheme, Proceedings of the fourth annual symposium on Computational geometry, p.134-142, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73407]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Theory