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.
展开▼
机译：本文提出了一种新的算法，用于快速舍入平面中线段的排列 A 。捕捉舍入定义了一组热像素，它们是以最靠近 A 顶点的整数网格点为中心的单位正方形。捕捉舍入功能通过用分段线性曲线替换每个输入段来简化 A ，该分段线性曲线连接了该段相交的热点像素的中心。令 H 为所有热像素的集合，对于每个 A ∈ H ，令（h）为在 h 内具有交点或端点的线段数。如果 A 包含 n 个输入段，则第一个新算法的运行时间为 O （Εh∈H< / SUB>是（h）日志 n ）。在最坏的情况下，这将以前的输入和输出敏感算法提高了Θ（n）。第二种算法具有更好的运行时间 O （E h∈H ed（h） log n ）;这里的 ed（h）是 h 中交叉图案的描述复杂度，可能远小于 is（h），并且从不更大。
展开▼
