Academic Commons


An Optimal Complexity Algorithm for Computing Topological Degree in Two Dimensions

Boult, Terrance E.; Sikorski, Krzysztof

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.



More About This Work

Academic Units
Computer Science
Department of Computer Science, Columbia University
Columbia University Computer Science Technical Reports, CUCS-187-85
Published Here
July 10, 2013