Improved output-sensitive snap rounding
John E. Hershberger · 2006
This paper presents new algorithms for snap rounding an arrangement A of line segments in the plane. Snap rounding defines a set of hot pixels, which are unit squares centered on the integer grid points closest to the vertices of A. Snap rounding simplifies A by replacing every input segment by a piecewise linear curve connecting the centers of the hot pixels the segment intersects. Let H be the set of all hot pixels, and for each A∈H let (h) be the number of segments with an intersection or endpoint inside h. If A contains n input segments, the running time of the first new algorithm is O(Εh∈H is (h) log n). This improves previous input- and output-sensitive algorithms by a factor of Θ(n) in the worst case. The second algorithm has an even better running time of O(Εh∈H ed (h) log n); here ed(h) is the description complexity of the crossing pattern in h, which may be substantially less than is(h) and is never greater.