Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)



The intrinsic spread of a configuration in $ {\bf R}\sp d$

Authors: Jacob E. Goodman, Richard Pollack and Bernd Sturmfels
Journal: J. Amer. Math. Soc. 3 (1990), 639-651
MSC: Primary 52B35; Secondary 05B25, 52B55
MathSciNet review: 1046181
Full-text PDF

References | Similar Articles | Additional Information

References [Enhancements On Off] (What's this?)

  • [1] D. Bienstock, Some provably hard crossing number problems, Discrete Comput. Geom. (to appear). MR 1115102 (92i:05081)
  • [2] R. Bland and M. Las Vergnas, Orientability of matroids, J. Combin. Theory Ser. B 24 (1978), 94-123. MR 0485461 (58:5294)
  • [3] J. Bokowski and B. Sturmfels, Computational synthetic geometry, Lecture Notes in Math., vol. 1355, Springer-Verlag, Berlin, 1989. MR 1009366 (90i:52001)
  • [4] B. Chazelle, Problem 3-6, Third Computational Geometry Day, Courant Institute, Jan. 16, 1987. MR 707591 (85m:68032)
  • [5] D. Dobkin and D. Silver, Recipes for geometry and numerical analysis, Part 1: an empirical study, Proc. Fourth Annual ACM Sympos. on Computational Geometry, 1988, pp. 93-105.
  • [6] H. Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag, Berlin, 1987. MR 904271 (89a:68205)
  • [7] J. Folkman and J. Lawrence, Oriented matroids, J. Combin. Theory Ser. B 25 (1978), 199-263. MR 511992 (81g:05045)
  • [8] J. E. Goodman and R. Pollack, Multidimensional sorting, SIAM J. Comput. 12 (1983), 484-507. MR 707408 (85c:68082)
  • [9] -, Upper bounds for configurations and polytopes in $ {{\mathbf{R}}^d}$, Discrete Comput. Geom. 1 (1986), 219-227. MR 861891 (87k:52016)
  • [10] J. E. Goodman, R. Pollack, and B. Sturmfels, Coordinate representation of order types requires exponential storage, Proc. 21st Annual ACM Sympos. on Theory of Computing, 1989, pp. 405-410.
  • [11] D. H. Greene and F. F. Yao, Finite-resolution computational geometry, Proc. 27th Annual IEEE Sympos. on the Foundations of Computer Science, 1986, pp. 143-152.
  • [12] D. Yu. Grigorā€²ev and N. N. Vorobjov, Jr., Solving systems of polynomial inequalities in subexponential time, J. Symbolic Comput. 5 (1988), 37-64. MR 949112 (89h:13001)
  • [13] B. Grünbaum, Arrangements and spreads, Amer. Math. Soc., Providence, RI, 1972.
  • [14] C. Hoffmann and J. Hopcroft, Towards implementing robust geometric computations, Proc. Fourth Annual ACM Sympos. on Computational Geometry, 1988, pp. 106-117.
  • [15] B. Jaggi, P. Mani-Levitska, B. Sturmfels, and N. White, Uniform oriented matroids without the isotopy property, Discrete Comput. Geom. 4 (1989), 97-100. MR 973539 (89j:05028)
  • [16] J. Komlós, J. Pintz, and E. Szemerédi, A lower bound for Heilbronn's problem, J. London Math. Soc. 25 (1982), 13-24. MR 645860 (83i:10042)
  • [17] M. Las Vergnas, Order properties of lines in the plane and a conjecture of G. Ringel, J. Combin. Theory Ser. B 41 (1986), 246-249. MR 859315 (87k:52027)
  • [18] V. J. Milenkovic, Verifiable implementations of geometric algorithms using finite precision arithmetic, Proc. 1986 Oxford Workshop on Geometric Reasoning, AI Journal (to appear).
  • [19] K. F. Roth, Developments in Heilbronn's triangle problem, Adv. in Math. 22 (1976), 364-385. MR 0429761 (55:2771)
  • [20] D. Salesin, J. Stolfi, and L. Guibas, Epsilon geometry: building robust algorithms from imprecise computations, Proc. Fifth Annual ACM Sympos. on Computational Geometry, 1989, pp. 208-217.
  • [21] B. Sturmfels, Some applications of affine Gale diagrams to polytopes with few vertices, SIAM J. Discrete Math. 1 (1988), 121-133. MR 936614 (89d:52016)
  • [22] Peter Ungar, personal communication.

Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC: 52B35, 05B25, 52B55

Retrieve articles in all journals with MSC: 52B35, 05B25, 52B55

Additional Information

Article copyright: © Copyright 1990 American Mathematical Society

American Mathematical Society