Academic Commons

Reports

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.

Subjects

Files

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
Academic Commons provides global access to research and scholarship produced at Columbia University, Barnard College, Teachers College, Union Theological Seminary and Jewish Theological Seminary. Academic Commons is managed by the Columbia University Libraries.