An optimal algorithm for the (<= k)-levels, with applications to separation and transversal problems.
Hazel Everett, Jean–Marc Robert, Marc J. van Kreveld · International Journal of Computational Geometry & Applications · 1996
This paper gives an optimal O(n log n + nk) time algorithm for constructing the levels 1,...,k in an arrangement of n lines in the plane. This algorithm is extended to compute these levels in an arrangement of n unbounded x-monotone polygonal convex chains, of which each pair intersects at most a constant number of times.These algorithms can be used to solve the following separation and transversal problems. For a set of n blue points and a set of n red points, find a line that separates the two sets in such a way that the sum, m, of the number of red points above the line and the number of blue points below the line is minimized. Such an optimal line can be found in O(nm log m + n log n) time. For a set of nline segments in the plane, find a line that intersects the maximum number of the line segments. Such an optimal line can be found in O(nm log m + n log n) time for vertical segments and in O((nm log m + n log2n) α(n)) expected time for arbitrary line segments, where m denotes the number of line segments not intersected by the optimal line.