congyu711 / k-level Goto Github PK

The output of k-level algorithm is an ordered sequence of breakpoints which the k-level meets from -1e10 to 1e10.
Tested with millions of instances

The sequence of lines that appears on the k-level is correct. But in rare cases the x_coord of some breakpoints is slightly wrong.

test.zip

-1e+10
-1242.69
-1104.51
-795.628
-444.492
-438.347
-504.167
-390.544
-373.945
-233.431
-218.397

see line 7 -504.167 is smaller than the x_coord of the previous breakpoint. This is supposed to be a nondecreasing sequence.

I guess this is caused by a late update of kineticPriorityQueue::t while updating the datastructure.

The k-level algorithm maintains two kinetic heap consisting of the top k and the rest lines. The implementation of kinetic heap in kpq.cc can not be empty. So the upper and lower envelope( 1-level and n-level if there are n lines) need to computed separately.
However finding upper or lower envelope is equivalent to computing the convex hull. maybe fix later