In this talk, we propose a novel implementation of Newton's method for solving semi-discrete optimal transport problems for cost functions which is a positive combination of $p$-norms, $1<p<\infty$. It is well understood that the problem reduces to finding a subdivision of a bounded region in Laguerre cells, and we prove that the Laguerre cells are star-shaped with respect to the target points. By exploiting the geometry of the Laguerre cells, we obtain an efficient and reliable implementation of Newton's method to find the sought network structure. We give some implementation details and numerical results. Joint work with Daniyar Omarov, Georgia Tech.