improved output-sensitive snap rounding
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.
snap rounding robust geometric computation