La complexité de la factorisation d'un polynôme bivarié se calcule habituellement en fonction du degré total ou du bidegré. Les algorithmes dits "convexe-denses" s'attachent à tenir compte du polygone de Newton. Je propose ici un algorithme qui tient compte à la fois du volume du polygone et des contraintes combinatoires induites par le théorème d'Ostrowski (le polygone du produit est la somme de Minkowski des polygones). La complexité améliore celle des différents algorithmes convexe-denses actuels, ce que j'illustrerai sur quelques exemples significatifs. Un point clé est un algorithme de factorisation w-adique rapide où w est une valuation augmentée remplaçant la valuation de Gauss usuelle, ce résultat pouvant avoir d'autres applications intéressantes.