Placing the largest similar copy of a convex polygon among polygonal obstacles

ABSTRACT

Given a convex polygon P and an environment consisting of polygonal obstacles, we find the largest similar copy of P that does not intersect any of the obstacles. Allowing translation, rotation, and change-of-size, our method combines a new notion of Delaunay triangulation for points and edges with the well-known functions based on Davenport-Schinzel sequences producing an almost quadratic algorithm for the problem. Namely, if P is a convex k-gon and if Q has n corners and edges then we can find the placement of the largest similar copy of P in the environment Q in time &Ogr;(k4n &lgr;4(kn) log n), where &lgr;4 is one of the almost-linear functions related to Davenport-Schinzel sequences. If the environment consists only of points then we can find the placement of the largest similar copy of P in time &Ogr;(k2n &lgr;3(kn) log n).

REFERENCES

• AB: Francis Avnaim , Jean-Daniel Boissonnat, Polygon Placement Under Translation and Rotation, Proceedings of the 5th Annual Symposium on Theoretical Aspects of Computer Science, p.322-333, February 11-13, 1988
• ASS: P. K. Agarwal , M. Sharir , P. Shor, Sharp upper and lower bounds on the length of general Davenport-Schinzel Sequences, Journal of Combinatorial Theory Series A, v.52 n.2, p.228-274, Nov. 1989 [doi>10.1016/0097-3165(89)90032-0]
• At: M. J. Atallah, Dynamic computational geometry, PFOC. 24th IE:Eld Symp. on Foundations of Computrr Science, 1983, pp. 92-99.
• CD: L. Paul Chew , Robert L. (Scot) Dyrsdale, III, Voronoi diagrams based on convex distance functions, Proceedings of the first annual symposium on Computational geometry, p.235-244, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323264]
• Ch: B. Chazelle, The polygon containment problem, in Advances in Computing Research, Vol. I: Computational Geometry, (F.P. Preparata, Ed.), JAI Press, Greenwich, Conneticut (19831, pp. l-33.
• Che: L.P. Chew, Constrained Delaunay Triangulations, to appear in Algorithmica.
• Fo1: Steven Fortune, A Fast Algorithm for Polygon Containment by Translation (Extended Abstract), Proceedings of the 12th Colloquium on Automata, Languages and Programming, p.189-198, July 15-19, 1985
• Fo2: S. Fortune, A sweepline algorithm for Voronoi diagrams, Algorithmica, 2 (1987), pp. 153-174.
• KS: K. Kedem , M. Sharir, Planning algorithm for a convex polygonal object in two-dimensional polygonal space, Discrete & Computational Geometry, v.5 n.1, p.43-75, Jan. 1990 [doi>10.1007/BF02187779]
• LL: D.T. Lee and A.K. Lin, Generalized Delaunay Triangulation for Planar Graphs, Discrete ad Computational Geometry, 1 (1986), pp, 201-217.
• LS: D. Leven and M. Sharir, Planning a purely translational motion for a convex polygonal object in two dimensional space using Generalized Voronoi diagrams, Discrete and Computational Geometry, 2 (19871, pp. 255-270.
• SCKLPS: M. Sharir, R. Cole, K. Kedem, D. Leven, R. Pollack and S. Sifrony, Geometric applications of Davenport- Schinzel sequences, Proc. 27th IEEE Symp. on Foundations of Computer Science, 1986, pp. 77-86.
• Ya: C.K. Yap, An O(n logn) algorithm for the Voronoi diagram of a set of simple curve segments, Discrete and Computational Geometry, 2 (19871, pp. 365-393.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  G. Mathematics of Computing
  G.m MISCELLANEOUS
      Subjects: Queueing theory**

General Terms:
Algorithms, Theory