A geometric algorithm for winding number computation with complexity analysis

作者：Garcia Zapata Juan Luis; Diaz Martin Juan Carlos

来源：Journal of Complexity, 2012, 28(3): 320-345.

DOI：10.1016/j.jco.2012.02.001

• Winding number
• Contour integration
• Argument principle
• Root finding

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 we propose another method, which are not based on numerical integration, but on discrete geometry. We give conditions that ensure its correct behavior, and a complexity bound based on the distance of the curve to singular cases. Besides, we 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.

• 出版日期2012-6