Some new effectivity bounds in computational geometry. (English) Zbl 0685.68044

Applied algebra, algebraic algorithms and error-correcting codes, Proc. 6th Int. Conference, AAECC-6, Rome/Italy 1988, Lect. Notes Comput. Sci. 357, 131-151 (1989).
[For the entire collection see Zbl 0671.00023.]
Consequences of Hilber’s Nullstellensatz for algebraically closed fields of any characteristic are applied to estimate the worst case complexity of geometric algorithms. The results are of interest especially for the discussion of parallel (“number of processors”) complexities, and give a geometric interpretation for improvements of Gröbner base computations introduced by B. Buchberger and others.
Reviewer: R.Klette


68Q25 Analysis of algorithms and problem complexity
68R99 Discrete mathematics in relation to computer science
52A37 Other problems of combinatorial convexity


Zbl 0671.00023