1985 Reports

# An Optimal Complexity Algorithm for Computing Topological Degree in Two Dimensions

An algorithm is presented to compute the topological degree for any function from a class F. The class F consists of functions defined on a two dimensional unit square C, f, C → ℝ², which satisfy Lipschitz condition with constant K > 0, and whose infinity norm on the boundary of C is at least d > 0. A worst case lower bound, m* = 4[K/4d], is established on the number of function evaluations necessary to compute the topological degree for any function f from the class F. The parallel information used by our algorithm permits the computation of the degree for every f in F with m* function evaluations necessary. The cost of our algorithm is shown to be almost equal to the complexity of the problem.

## Subjects

## Files

- CUCS-187-85.pdf application/pdf 341 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-187-85
- Published Here
- July 10, 2013