We develop a new algorithm for factoring a bivariate polynomial $F\in \mathbb{ K}[x,y]$ which takes fully advantage of the geometry of the Newton polygon of $F$. Under a non degeneracy hypothesis, the complexity is $\tilde{ \mathcal{ O}}(Vr_0^{ \omega-1} )$ where $V$ is the volume of the polygon and $r_0$ is its minimal lower lattice length. This improves the complexity $\tilde{ \mathcal{ O}}(d^{ \omega+1})$ of the classical algorithms which consider the total degree $d$ of $F$ as the main complexity indicator. The integer $r_0\le d$ reflects some combinatorial constraints imposed by the Newton polygon, giving a reasonable and easy-to-compute upper bound for the number of its indecomposable Minkovski summands of positive volume. The proof is based on a new fast factorization algorithm in $\mathbb{ K}[[x]][y]$ with respect to a slope valuation, a result which has its own interest.
Categories: math.AC