Snap rounding line segments efficiently in two and three dimensions
Michael T. Goodrich, Leonidas Guibas, John E. Hershberger, Paul J. Tanenbaum · 1997
We study the problem of robustly rounding a set S of n line segments in R2 using the snap rounding paradigm.In this paradigm each pixel containing an endpoint or intersection point is called "hot," and all segments intersecting a hot pixel are re-routed to pass through its center.We show that a snap-rounded approximation to the arrangement defined by S can be built in an output-sensitive fashion, and that this can be done without first determining all the intersecting pairs of segments in S. Specifically, we give a deterministic plan~sweep algorithm running in time O(n bgn -F &H Ihl10g ~), where ~is the set of hot pixela and \hl is the number of segments intersecting a hot pixel h E H. We alsogive a simple randomized incremental construction whose expected running time matches that of our deterministic algorithm.The complexity of these algorithms is optimal up to polylogarithmic factors.