Constructing the vd for random (non-crossing) line-segments is a reasonable stress-test for my vd-algorithm. When you've fixed one bug, just increase the number of line-segments by a factor of two and you will most likely uncover another! It now runs OK up to 2048 line-segments (yes, that does imply I get a segfault at 4096!).
There's some slowdown from 5us*n*log(n) in september 2011 (for just point-sites), to this code which runs in about 15 to 20us*n*log(n) when inserting the point-sites. Line-sites take longer, about 200us*m*log(m) for m line-sites.