The intrinsic spread of a configuration in $\textbf {R}^ d$
HTML articles powered by AMS MathViewer
- by Jacob E. Goodman, Richard Pollack and Bernd Sturmfels
- J. Amer. Math. Soc. 3 (1990), 639-651
- DOI: https://doi.org/10.1090/S0894-0347-1990-1046181-2
- PDF | Request permission
References
- Daniel Bienstock, Some provably hard crossing number problems, Discrete Comput. Geom. 6 (1991), no. 5, 443–459. MR 1115102, DOI 10.1007/BF02574701
- Robert G. Bland and Michel Las Vergnas, Orientability of matroids, J. Combinatorial Theory Ser. B 24 (1978), no. 1, 94–123. MR 485461, DOI 10.1016/0095-8956(78)90080-1
- Jürgen Bokowski and Bernd Sturmfels, Computational synthetic geometry, Lecture Notes in Mathematics, vol. 1355, Springer-Verlag, Berlin, 1989. MR 1009366, DOI 10.1007/BFb0089253
- Bernard Chazelle, An improved algorithm for the fixed-radius neighbor problem, Inform. Process. Lett. 16 (1983), no. 4, 193–198. MR 707591, DOI 10.1016/0020-0190(83)90123-0 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.
- Herbert Edelsbrunner, Algorithms in combinatorial geometry, EATCS Monographs on Theoretical Computer Science, vol. 10, Springer-Verlag, Berlin, 1987. MR 904271, DOI 10.1007/978-3-642-61568-9
- Jon Folkman and Jim Lawrence, Oriented matroids, J. Combin. Theory Ser. B 25 (1978), no. 2, 199–236. MR 511992, DOI 10.1016/0095-8956(78)90039-4
- Jacob E. Goodman and Richard Pollack, Multidimensional sorting, SIAM J. Comput. 12 (1983), no. 3, 484–507. MR 707408, DOI 10.1137/0212032
- Jacob E. Goodman and Richard Pollack, Upper bounds for configurations and polytopes in $\textbf {R}^d$, Discrete Comput. Geom. 1 (1986), no. 3, 219–227. MR 861891, DOI 10.1007/BF02187696 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. 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.
- D. Yu. Grigor′ev and N. N. Vorobjov Jr., Solving systems of polynomial inequalities in subexponential time, J. Symbolic Comput. 5 (1988), no. 1-2, 37–64. MR 949112, DOI 10.1016/S0747-7171(88)80005-1 B. Grünbaum, Arrangements and spreads, Amer. Math. Soc., Providence, RI, 1972. C. Hoffmann and J. Hopcroft, Towards implementing robust geometric computations, Proc. Fourth Annual ACM Sympos. on Computational Geometry, 1988, pp. 106-117.
- Beat Jaggi, Peter Mani-Levitska, Bernd Sturmfels, and Neil White, Uniform oriented matroids without the isotopy property, Discrete Comput. Geom. 4 (1989), no. 2, 97–100. MR 973539, DOI 10.1007/BF02187717
- János Komlós, János Pintz, and Endre Szemerédi, A lower bound for Heilbronn’s problem, J. London Math. Soc. (2) 25 (1982), no. 1, 13–24. MR 645860, DOI 10.1112/jlms/s2-25.1.13
- Michel Las Vergnas, Order properties of lines in the plane and a conjecture of G. Ringel, J. Combin. Theory Ser. B 41 (1986), no. 2, 246–249. MR 859315, DOI 10.1016/0095-8956(86)90048-1 V. J. Milenkovic, Verifiable implementations of geometric algorithms using finite precision arithmetic, Proc. 1986 Oxford Workshop on Geometric Reasoning, AI Journal (to appear).
- K. F. Roth, Developments in Heilbronn’s triangle problem, Advances in Math. 22 (1976), no. 3, 364–385. MR 429761, DOI 10.1016/0001-8708(76)90100-6 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.
- Bernd Sturmfels, Some applications of affine Gale diagrams to polytopes with few vertices, SIAM J. Discrete Math. 1 (1988), no. 1, 121–133. MR 936614, DOI 10.1137/0401014 Peter Ungar, personal communication.
Bibliographic Information
- © Copyright 1990 American Mathematical Society
- Journal: J. Amer. Math. Soc. 3 (1990), 639-651
- MSC: Primary 52B35; Secondary 05B25, 52B55
- DOI: https://doi.org/10.1090/S0894-0347-1990-1046181-2
- MathSciNet review: 1046181