has anyone ever heard of delaunay triangulation ?

if not, neither did i.
i friend who is working on a similar game pointed me in the right direction, so now i can finally generate vias, or starlanes without so much randomness. The algorithm allows me to have a guaranteed connection between all planets without to many and overlapping lanes. it works like a charm, but has pointed out another error i made when i first designed the game. I use an 2 dimensional array for all solarsystems. then i add a random displacement so my galaxy doesn't look like a huge 2 dimensional array. this means i still have overlapping vias, but the situation greatly improved.
The downside is that using this algorithm on 4000 points on a 512 x 512 matrix takes quite a while. I optimised the Galaxy creation quite a bit. so generating 4k solarsystems with ~ 9 planets each and vias takes 21125ms.
If i check how long the vias take, i get an impressive 20478ms. This means everything but the vias take 650ms to generate, then the algorithm eats solid 20 seconds.

I will post additional information later, i have to go now :)

-sascha