Рет қаралды 304
the merge part (except for finding the base lines) is the Guibas-Stolfi way of merging each subproblem (i.e. "Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams."). it's clearly not entirely Guibas-Stolfi, since it splits its subproblems by selecting two random points in the set, and assigning points to a set based on which chosen point is closer. i'm still unaware of whether this is sufficient to guarantee expected O(E log V) runtime -- elongated regions are often cut along their widths, so maybe -- but either way, it looks prettier than simply splitting across grid lines or parallel lines.
i didn't include how i find the baselines -- basically, starting at the two chosen points A and B each from different subtriangulations, i find the neighbor of B farthest to the left from line AB, and set that point as the new B, and repeat until i can't find any more points which go left of line AB. (if there are ties among collinear points, i choose the point closest to A.) then i swap A and B and repeat the whole process over again, and i keep repeating the whole process until one such repeat doesn't yield any improvement in leftward travel -- that's the base line. i'm sure there's some way for me to put an upper bound on how long this takes -- it acts an awful lot like it's O(E) on average, but again, i haven't entirely bounded it yet. maybe i'll change it eventually.