Finding the number of roots of a polynomial in a plane region using the winding number

We describe a method that computes the number of roots of a polynomial ff inside a region bounded by the curve ΓΓ, with an analysis of its computational cost. It is based on the number of roots being the same as the winding number of f(Γ)f(Γ). While the usual methods for computing the winding number involve numerical integration, in this paper we use a geometrical construction. We show its correctness without referring to global information about ff (like its Lipschitz constant on ΓΓ). The analysis of its cost is based on the distance from the roots to ΓΓ, expressed using a condition number suitably defined. The method can be used in a divide-and-conquer root-finding algorithm.