A geometric algorithm for winding number computation with complexity analysis (Q423881)

Winding number computation is used in several root-finding algorithms. Many methods to compute the winding number of plane curves have been proposed, often with the aim of counting the number of roots of polynomials (or, more generally, zeros of analytic functions) inside some region by using the principle of argument. In this paper, the authors propose another method, which is not based on numerical integration, but on discrete geometry using discretization of the curve to obtain an array to which the method of twist counting of Henrici can be reliably applied. They give conditions that ensure its correct behavior, and a complexity bound based on the distance of the curve to singular cases. Besides, they provide a modification of the algorithm that detects the proximity to a singular case of the curve. If this proximity is such that the number of operations required grows over certain threshold, set by the user, the modified algorithm returns without winding number computation, but with information about the distance to singular case. When the method is applied to polynomials, this information refers to the localization of the roots placed near the curve.