Improved output-sensitive snap rounding

ABSTRACT

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.

REFERENCES

• 1: J. L. Bentley and T. A. Ottmann. Algorithms for reporting and counting geometric intersections. IEEE Trans. Comput., C-28(9):643--647, September 1979.
• 2: K. Q. Brown. Comments on "Algorithms for reporting and counting geometric intersections". IEEE Trans. Comput., C-30:147--148, 1981.
• 3: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 4: Graham Cormode , S. Muthukrishnan, The string edit distance matching problem with moves, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.667-676, January 06-08, 2002, San Francisco, California
• 5: M. de Berg, D. Halperin, and M. Overmars. An intersection-sensitive algorithm for snap rounding. Manuscript, http://www.cs.tau.ac.il/~danha/papers/issr.pdf.
• 6: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 7: James R. Driscoll , Neil Sarnak , Daniel D. Sleator , Robert E. Tarjan, Making data structures persistent, Journal of Computer and System Sciences, v.38 n.1, p.86-124, February 1989 [doi>10.1016/0022-0000(89)90034-2]
• 8: Vladmir Estivill-Castro , Derick Wood, A survey of adaptive sorting algorithms, ACM Computing Surveys (CSUR), v.24 n.4, p.441-476, Dec. 1992 [doi>10.1145/146370.146381]
• 9: Michael T. Goodrich , Leonidas J. Guibas , John Hershberger , Paul J. Tanenbaum, Snap rounding line segments efficiently in two and three dimensions, Proceedings of the thirteenth annual symposium on Computational geometry, p.284-293, June 04-06, 1997, Nice, France [doi>10.1145/262839.262985]
• 10: D. H. Greene. Integer line segment intersection. Unpublished Manuscript.
• 11: Leonidas J. Guibas , David H. Marimont, Rounding arrangements dynamically, Proceedings of the eleventh annual symposium on Computational geometry, p.190-199, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220300]
• 12: Leo J. Guibas , Edward M. McCreight , Michael F. Plass , Janet R. Roberts, A new representation for linear lists, Proceedings of the ninth annual ACM symposium on Theory of computing, p.49-60, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803395]
• 13: D. Halperin. Problem 1: Output sensitive algorithm for snap rounding, June 2005. Open Problem Session: 21st Annual Symposium on Computational Geometry.
• 14: Dan Halperin , Eli Packer, Iterated snap rounding, Computational Geometry: Theory and Applications, v.23 n.2, p.209-225, September 2002 [doi>10.1016/S0925-7721(01)00064-5 ]
• 15: John D. Hobby, Practical segment intersection with finite precision output, Computational Geometry: Theory and Applications, v.13 n.4, p.199-214, Oct. 1999 [doi>10.1016/S0925-7721(99)00021-8 ]
• 16: S. Huddleston and K. Mehlhorn. A new data structure for representing sorted lists. Acta Inform., 17:157--184, 1982.
• 17: F. K. Hwang and S. Lin. A simple algorithm for merging two disjoint linearly ordered sets. SIAM J. Comput., 1(1):31--39, 1972.
• 18: Eli Packer, Iterated snap rounding with bounded drift, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA [doi>10.1145/1137856.1137910]
• 19: Micha Sharir , Pankaj K. Agarwal, Davenport-Schinzel sequences and their geometric applications, Cambridge University Press, New York, NY, 1996
• 20: Walter F. Tichy, The string-to-string correction problem with block moves, ACM Transactions on Computer Systems (TOCS), v.2 n.4, p.309-321, Nov. 1984 [doi>10.1145/357401.357404]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Theory

Keywords:
robust geometric computation, snap rounding