1984 Reports
Minimal number of function evaluations for computing topological degree in two dimensions
A lower bound n-min roughly equal log-2 (diam(T)/m) is established for the minimal number of function evaluations necessary to compute the topological degree of every function f in a class F. The class F consists of continuous functions f = (f1, f2) defined on a triangle T, f: T → R squared, such that the minimal distance between zeros of f1 and zeros of f2 on the boundary of T is not less than m, m > 0. Information is exhibited which permits the computation of the degree for every f in F with at most 2n-min function evaluations. An algorithm, due to Kearfott, uses this information to compute the degree. These results lead to tight lower and upper complexity bounds for this problem.
Subjects
Files
- cucs-093-84.pdf application/pdf 489 KB Download File
More About This Work
- Academic Units
- Computer Science
- Publisher
- Department of Computer Science, Columbia University
- Series
- Columbia University Computer Science Technical Reports, CUCS-093-84
- Published Here
- October 26, 2011