The complexity of minimizing the stabbing number or crossing number in a triangulation remains open. Furthermore, it remains open whether any of these problems have constant-factor approximations. See [FLM04] for some ideas.
In the worst case, any set of n points in the plane has a spanning tree of stabbing number O() [Aga92,Cha88,Wel93] and this bound is tight. An O()-approximation follows from this result.
There has been an advance on approximations [HP09]: Har-Peled designed an algorithm that computes a spanning tree of n points P in ^{d} whose crossing number is O(min(t log n, n^{1-1/d})), where t the minimum crossing number of any spanning tree of P.