# The ICICS/CS Reading Room

## UBC CS TR-2009-04 Summary

- Efficient Snap Rounding in Square and Hexagonal Grids using Integer Arithmetic, February 12, 2009 Boaz Ben-Moshe, Binay K. Bhattacharya and Jeff Sember, 20 pages
In this paper we present two efficient algorithms for snap rounding
a set of segments to both square and hexagonal grids. The first
algorithm takes n line segments as input and generates the set
of snapped segments in O((n + k) log n + |I| + |I*|) time, where
k is never more than the number of hot pixels (and may be
substantially less), |I| is the complexity of the unrounded
arrangement I, and |I*| is the multiset of snapped segment fragments.
The second algorithm generates the rounded arrangement of segments
in O(|I| + ( |I*| + Sigma_c is(c)) log n) time, where |I*| is the
complexity of the rounded arrangement I* and is(c) is the number of
segments that have an intersection or endpoint in pixel row or column
c. Both use simple integer arithmetic to compute the rounded
arrangement by sweeping a strip of unit width through the
arrangement, are robust, and are practical to implement. They
improve upon existing algorithms, since existing running times
either include an |I| log n term, or depend upon the number of
segments interacting within a particular hot pixel h (is(h) and
ed(h), or |h|), whereas ours depend on |I| without the log n factor
and are either independent of the number of segments interacting
within a hot pixel (algorithm 1) or depend upon the number of
segments interacting in an entire hot row or column (is(c)), which
is a much coarser partition of the plane (algorithm 2).

If you have any questions or comments regarding this page please send mail to
help@cs.ubc.ca.