Update3: version 11.10-148 now goes to 16k line-sites without errors or warnings:
Update2: This diagram with 8k vertices clearly has errors:
Update: Version 11.10-141 now copes with 4k random segments. But I don't know of any smart way to check the diagram for correctness..
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.
One thought on “Random line-segment voronoi diagram”