MPI-I-2007-1-001

The Bentley Ottmann sweep line algorithm is a standard tool to compute the arrangement of algebraic curves in the plane. If degenerate positions are not excluded from the input, variants of this algorithm must, among other things, handle $k \geq 2$ curves intersecting simultaneously in a single intersection point. In that situation, the algorithm knows the order of the curves immediately left of the intersection point and needs to compute the order immediately right of the intersection point. Segments and lines can be reordered efficiently in linear time by simply reversing their order, except for overlapping segments. Algebraic curves can be sorted with $O(k \log k)$ geometric comparisons in their order immediately right of the intersection point. A previous result shows that algebraic curves whose degree is at most $d$ can be reordered in $O(d^2 k)$ time, which is for constant $d$ better than sorting. In this paper, we improve the complexity of the reordering of algebraic curves to $O(k)$ time, i.e., independent of the degree of the algebraic curves. The maybe surprising implication is that algebraic curves, even of unbounded algebraic degree, cannot realize all possible permutations of their vertical order while passing through a common intersection from left to right. We give a short example for an infeasible permutation. Both linear time algorithms require the knowledge of the intersection multiplicities of curves that are neighbors immediately left of the intersection point, i.e., $k-1$ intersection multiplicities.