An intersection-sensitive algorithm for snap rounding

Snap rounding is a method for converting arbitrary-precision arrangements of segments into fixed-precision representation. We present an algorithm for snap rounding with running time O((n+I)logn), where I is the number of intersections between the input segments. In the worst case, our algorithm is an order of magnitude more efficient than the best previously known algorithms. We also propose a variant of the traditional snap-rounding scheme. The new method has all the desirable properties of traditional snap rounding and, in addition, guarantees that the rounded arrangement does not have degree-2 vertices in the interior of edges. This simplified rounded arrangement can also be computed in O((n+I)logn) time.