Finding the minimum visible vertex distance between two non-intersecting simple polygons

ABSTRACT

In this paper, we present an &Ogr;(n log n) algorithm for finding the minimum Euclidean visible vertex distance between two nonintersecting simple polygons, where n is the number of vertices in a polygon. The algorithm is based on applying a divide and conquer method to two preprocessed facing boundaries of the polygons. We also derive an &Ogr;(n log n) algorithm for finding a minimum sequence of separating line segments between two nonintersecting polygons.

REFERENCES

• 1: Alok Aggarwal , Heather Booth , Joseph O'Rourke , Subhash Suri , Chee K. Yap, Finding minimal convex nested polygons, Proceedings of the first annual symposium on Computational geometry, p.296-304, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323271]
• 2: Bentley, J., Ottmann, T., (1979), "Algorithms for Reporting and Counting Geometric Intersections," IEEE Trans. on Computers, Vol. c-28, pp. 643-647.
• 3: Bhattacharya, B., El Gindy, H., (1984), "A New Linear Convex Hull Algorithm for Simple Polygon," IEEE Inform. Theory, Vol. c-29, pp 571-573.
• 4: Bernard Chazelle , David P. Dobkin, Detection is easier than computation (Extended Abstract), Proceedings of the twelfth annual ACM symposium on Theory of computing, p.146-153, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804662]
• 5: Chin, F., Wang, C., (1983), "Optimal Algorithms for the Intersection and the Minium Distance Problems between Planar Polygons," IEEE Trans. on Computers, Vol. c-32, pp 1205-1207.
• 6: Chin, F., Wang, C., Sampson, J., (1985), "An Unifying Approach for a Class of Computational Geometry Problem," International Journal on Computer Graphics, to appear.
• 7: H. Edelsbrunner, Computing the extreme distances between two convex polygons, Journal of Algorithms, v.6 n.2, p.213-224, June 1985 [doi>10.1016/0196-6774(85)90039-2]
• 8: A. Fournier , D. Y. Montuno, Triangulating Simple Polygons and Equivalent Problems, ACM Transactions on Graphics (TOG), v.3 n.2, p.153-174, April 1984 [doi>10.1145/357337.357341]
• 9: Garey, M., Johnson, D., Preparata, F., Tarjan, R., (1978), "Triangulating a Simple Polygon, Information Processing Letters, Vol. 7, pp. 175-179.
• 10: Kirkpatrick, D., (1979), "Efficient Computation of Continuous Skeletons," Proceedings of the Twentieth Annual Symposium on the Foundations of Computer Science, pp. 18-27.
• 11: Lee, D., Preparata, F., (1984), "Computational Geometry - A Survey," IEEE Trans. on Computers, Vol. c-33, pp. 1072-1101.
• 12: Lee, D., Drysdale, R., (1981), "General Voronoi Diagram In The Plane," SIAM J. of Computing, Vol. 10, pp. 73-87.
• 13: McKenna, M., Toussaint, G. T., (1983), "Finding The Minimum Vertex Distance Between Two Disjoint Convex Polyygons In Linear Time," Technical Report SOCS-830c, McGill University.
• 14: Suri, S., O'Rourke, J., (1985), "Finding Minimal Nested Polygons," Technical Report, The Johns Hopkins University.
• 15: Toussaint, G. T., (1983), "An Optimal Algorithm for Computing the Minimum Vertex Distance between Two Crossing Convex Polygons," Proceedings of the Twenty-first Allerton Conf-Commun. Control and Comput., pp 457-458.
• 16: Wang, C., (1983), "Intersection and Minimum Distance Problems for Planar Polygons," M.Sc. Thesis, Department of Computing Science, University of Alberta.
• 17: Wang, C., Chan, E.P.F., "Finding the Minimum Vertex Distance Between Two Noninteresting Simple Polygon," Technical Report, Department of Computing Science, University of Alberta, 1986.
• 18: P. Widmayer , Y. F. Wu , C. K. Wong, Distance problems in computational geometry with fixed orientations, Proceedings of the first annual symposium on Computational geometry, p.186-195, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323258]

INDEX TERMS

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

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

General Terms:
Algorithms, Theory, Verification