A singly-exponential stratification scheme for real semi-algebraic varieties and its applications

1. Agarwal, P., Sharir, M., Shor, P. Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences, to appear in J. Combinatorial Theory, Series A.

   Google Scholar 

2. Arnon, D.S. Algorithms for the geometry of semi-algebraic sets, Tech. Rep. 436, Computer Science Dept., University of Wisconsin, Madison, 1981.

   Google Scholar 

3. Arnon, D.S., Collins, G.E., McCallum, S. Cylindrical algebraic decomposition II: an adjacency algorithm for the plane, SIAM J. Comput. 13 (1984), 878–889.

   Article  Google Scholar 

4. Aronov, B., Sharir, M. Triangles in space, or building and analyzing castles in the air, Proc. 4th Ann. ACM Sympos. Comput. Geom. (1988), 381–391.

   Google Scholar 

5. Atallah, M.J. Dynamic computational geometry, Comput. Math. with Applications, 11 (1985), 1171–1181.

   Article  Google Scholar 

6. Bennedetti, R., Risler, J.J. On the number of connected components of a real algebraic set Tech. Rept. LMENS-88-11, Ecole Normale Supérieure, Sept. 1988.

   Google Scholar 

7. Bochnak, J., Coste, M., Roy, M.F. Géométrie Algébrique Réelle, Ergebnisse der Mathematik, Springer verlag, Berlin 1987.

   Google Scholar 

8. Brown, W., Traub, J.F. On Euclid's algorithm and the theory of subresultants, J. ACM, 18 (1971), 505–514.

   Article  Google Scholar 

9. Caniglia, L., Galligo, A. and Heintz, J. Some new effectivity bounds in computational geometry, Proc. 6th Internat. Conf. on Applied Algebra, Algorithmic and Error Correcting Codes, Rome, July 1988.

   Google Scholar 

10. Canny, J.F. A new algebraic methods for motion planning and real geometry, Proc. 28th Ann. IEEE Symp. on Foundat. of Computer Science (1987), 39–48.

    Google Scholar 

11. Canny, J.F. Some algebraic and geometric computations in PSPACE, Proc. 20th Ann. ACM Symp. on Theory of Comput. (1988), 460–467.

    Google Scholar 

12. Chazelle, B. Convex partitions of polyhedra: a lower bound and worst-case optimal algorithm, SIAM J. Comput. 13 (1984), 488–507.

    Article  Google Scholar 

13. Chazelle, B., Friedman, J. A deterministic view of random sampling and its use in geometry, Proc. 29th Ann. IEEE Symp. on Foundat. of Computer Science (1988), 539–549. To appear in Combinatorica.

    Google Scholar 

14. Chazelle, B., Palios, L. Triangulating a nonconvex polytope, Proc. 5th Ann. ACM Sympos. Comput. Geom. (1989), to appear.

    Google Scholar 

15. Chazelle, B., Sharir, M. An algorithm for generalized point location and its applications, J. of Symbolic Comput., to appear.

    Google Scholar 

16. Clarkson, K.L. A randomized algorithm for closest-point queries, SIAM J. Comput. 17 (1988), 830–847.

    Article  Google Scholar 

17. Clarkson, K.L. New applications of random sampling in computational geometry, Disc. Comp. Geom. 2 (1987), 195–222.

    Article  Google Scholar 

18. Clarkson, K.L. Applications of random sampling in computational geometry, II, Proc. 4th Ann. ACM Sympos. Comput. Geom. (1988), 1–11.

    Google Scholar 

19. Clarkson, K.L., Edelsbrunner, H., Guibas, L.J., Sharir, M. Welzl, E. Combinatorial complexity bounds for arrangements of curves and surfaces, Proc. 29th Ann. IEEE Symp. on Foundat. of Computer Science (1988), 568–579.

    Google Scholar 

20. Cole, R. Searching and storing similar lists, J. Algorithms, 7 (1986), 111–119.

    Article  Google Scholar 

21. Collins, G.E. Quantifier elimination for real closed fields by cylindric algebraic decomposition, Proc. 2nd GI Conf. on Automata Theory and Formal Languages, Springer-Verlag, LNCS 33, Berlin (1975), 134–183.

    Google Scholar 

22. Collins, G.E., Loos, R. Polynomial real root isolation by differentiation, Proc. ACM Symp. on Symbolic and Algebraic Computations, Yorktown Heights, NY (1976), 15–25.

    Google Scholar 

23. Coste, M. and Roy, M.F. Thom's lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets, J. Symbolic Comput. 5 (1988), 121–129.

    Google Scholar 

24. Davenport, J. and Heintz, J. Real quantifier elimination is doubly exponential, J. Symbolic Comput. 5 (1988), 29–35.

    Google Scholar 

25. Edelsbrunner, H. Algorithms in Combinatorial Geometry, Springer-Verlag, Heidelberg, Germany, 1987.

    Google Scholar 

26. Edelsbrunner, H., Guibas, Sharir, M. The complexity of many faces in arrangements of lines and of segments, Proc. 4th Ann. ACM Sympos. Comput. Geom. (1988), 44–55.

    Google Scholar 

27. Edelsbrunner, H., Guibas, L.J., Stolfi, J. Optimal point location in a monotone subdivision, SIAM J. Comput. 15 (1986), 317–340.

    Article  Google Scholar 

28. Gianni, P. and Traverso, C. Shape determination for real curves and surfaces, Ann. Univ. Ferrara, Sez. VII — Sc. Mat. 29 (1983), 87–109.

    Google Scholar 

29. Grigor'ev, D. and Vorobjov, N. Solving systems of polynomial inequalities in subexponential time, J. Symbolic Comput. 5 (1988), 37–64.

    Google Scholar 

30. Hart, S., Sharir, M. Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes, Combinatorica 6 (1986), 151–177.

    Google Scholar 

31. Haussler, D., Welzl, E. Epsilon-nets and simplex range queries, Disc. Comp. Geom. 2 (1987), 127–151.

    Article  Google Scholar 

32. Kozen, D., Yap, C. Algebraic cell decomposition in NC, Proc. 26th Ann. IEEE Symp. on Foundat. of Computer Science (1985), 515–521.

    Google Scholar 

33. Loos, R. Generalized polynomial remainder sequences, in “Computer algebra: symbolic and algebraic computation”, B. Buchberger, G. Collins, R. Loos, R. Albrecht, eds. Springer-Verlag, 1983.

    Google Scholar 

34. Loos, R. Computing in algebraic extensions, in “Computer algebra: symbolic and algebraic computation”, B. Buchberger, G. Collins, R. Loos, R. Albrecht, eds. Springer-Verlag, 1983.

    Google Scholar 

35. Mahler, K. An inequality for the discriminant of a polynomial, Michigan Math. J. 11 (1964), 257–262.

    Article  Google Scholar 

36. McKenna, M. The biggest stick problem, First Computational Geometry Day, New York University, Sept. 1986.

    Google Scholar 

37. Milnor, J. On the Betti numbers of real varieties, Proc. Amer. Math. Soc. 15 (1964).

    Google Scholar 

38. Preparata, F.P., Shamos, M.I. Computational geometry: an introduction, Springer-Verlag, New York, NY, 1985.

    Google Scholar 

39. Prill, D. On approximations and incidence in cylindrical algebraic decompositions, SIAM J. Comput. 15 (1986), 972–993.

    Article  Google Scholar 

40. Reif, J.H., Sen, S. Optimal randomized parallel algorithms for computational geometry, Proc. 16th Internat. Conf. Parallel Processing, St. Charles, IL, 1987. Full version, Duke Univ. Tech. Rept., CS-88-01, 1988.

    Google Scholar 

41. Renegar, J. A faster PSPACE algorithm for deciding the existential theory of the reals, Proc. 29th Ann. IEEE Symp. on Foundat. of Computer Science (1988), 291–295.

    Google Scholar 

42. Roy, M.F. Computation of the topology of a real algebraic curve, to appear in Proc. Congress on Computational topology and geometry, Sevilla, 1987.

    Google Scholar 

43. Sarnak, N., Tarjan, R.E. Planar point location using persistent search trees, Comm. ACM 29 (1986), 669–679.

    Article  MathSciNet  Google Scholar 

44. Schwartz, J.T. Differential geometry and topology, Gordon and Breach (1968).

    Google Scholar 

45. Schwartz, J.T., Sharir, M. On the “piano movers” problem. II: General techniques for computing topological properties of real algebraic manifolds, Adv. in Appl. Math. 4 (1983), 298–351.

    Article  Google Scholar 

46. Spivak, M. A Comprehensive introduction to differential geometry, Vol.1, Publish or Perish, Inc., Boston.

    Google Scholar 

47. van der Waerden, B.L. Modern Algebra, Ungar Publishing Co., New York, 1950.

    Google Scholar 

48. Whitney, H. Elementary structure of real algebraic varieties, Annals of Math. 66 (1957).

    Google Scholar 

Download references