Hostname: page-component-586b7cd67f-2plfb Total loading time: 0 Render date: 2024-11-23T03:12:29.580Z Has data issue: false hasContentIssue false
  • English
  • Français

Separation of two monotone polygons in linear time

Published online by Cambridge University Press:  09 March 2009

Godfried T. Toussaint  and
Hossam A. El Gindy
Godfried T. Toussaint
Affiliation:
School of Computer Science, McGill University, 805 Sherbrooke Street West, Montreal, Quebec (Canada) H3A 2K6
Hossam A. El Gindy
Affiliation:
School of Computer Science, McGill University, 805 Sherbrooke Street West, Montreal, Quebec (Canada) H3A 2K6
Get access Rights & Permissions [Opens in a new window]

Abstract

SUMMARY

Let P= (p1, p2, …, pn) and Q= (q1, q2, …, qm) be two simple polygons monotonic in directions θs and φ respectively. It is shown that P and Q are separable with a single translation in at least one of the directions: ,. Furthermore, a direction for carrying out such a translation can be determined in O(m + n) time. This procedure is of use in solving the FIND-PATH problem in robotics.

Type
Article
Information
Robotica , Volume 2 , Issue 4 , October 1984 , pp. 215 - 220
Copyright
Copyright © Cambridge University Press 1984

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Guibas, L.J. and Yao, F.F., “On translating a set of rectangles,” Proc. Twelfth Annual ACM Symposium on Theory of Computing 154–160 (1980).Google Scholar
Ottman, T. and Widmayer, P., “On translating a set of line segments” Computer Vision, Graphics and Image Processing 24, 382–389 (1983).CrossRefGoogle Scholar
Toussaint, G.T., “The complexity of movement” IEEE International Symposium on Information Theory, St Jovite, Canada (09, 1983).Google Scholar
Sack, J.-R. and Toussaint, G.T., “Movability of objects” IEEE International Symposium on Information Theory, St. Jovite, Canada (09, 1983).Google Scholar
Toussaint, G.T. and Sack, J-.R., “Some new results on moving polygons in the plane” Proc. Robotic Intelligence and Productivity Conference” Detroit, Michigan158–163, (11 18–19, 1983),.Google Scholar
Chazelle, B. et al. , “The complexity and decidability of SEPARATION” Technical Report CS-83–34, University of Waterloo (11, 1983).Google Scholar
Toussaint, G.T., “On translating a set of Polyhedra” Conference on Polyhedra, Smith College, Northampton, Mass. (04 6–8, 1984).Google Scholar
Dawson, R., “On removing a ball without disturbing the others” Mathematics Magazine 57, No. 1, 27–30 (01, 1984).CrossRefGoogle Scholar
Post, K., “Six interlocking cylinders with respect to all directions” internal manuscript, University of Eindhoven (12, 1983).Google Scholar
Moser, W., Research Problems in Discrete Geometry (Department of Mathematics, McGill University, 1981).Google Scholar
Toussaint, G.T., “On translating a set of spheres” Technical Report SOCS-84.4, School of Computer Science, McGill University (03, 1984).Google Scholar
Van-Duc, Nguyen, “The Find-Path Problem in the Plane” A.I. Memo No. 160, Artificial Intelligence Laboratory, M.I.T. (02, 1984).Google Scholar
Bruce, R. Donald, “Hypothesizing Channels Through Free-Space In Solving the Findpath Problem” A.I. Memo No. 736, Artificial Intelligence Laboratory, M.I.T. (06, 1983).Google Scholar
David, Marr and Lucia, Vaina, “Representation and Recognition of the Movement of Shapes” A.I. Memo No. 597, Artificial Intelligence Laboratory, M.I.T. (10, 1980).Google Scholar
Preparata, F.P. and Supowit, K., “Testing a simple polygon for monotonicity” Information Processing Letters 12, 161–164 (1981).Google Scholar
ElGindy, H. and Avis, D., “A linear algorithm for computing the visibility polygon from a point” J. Algorithms 2, 186–197 (1981).CrossRefGoogle Scholar
Lee, D.T., Visibility of a simple polygon Computer Vision, Graphics and Image Processing 22, 207–221 (1983).CrossRefGoogle Scholar
Shamos, M.I. and Hoey, D., “Geometric intersections problems” Seventeenth Annual IEEE Symposium on Foundations of Computer Science 208–215 (10, 1976).Google Scholar
Guibas, L.J. and Stolfi, J., Notes on Computational Geometry (XEROX PARK and Stanford University, 1982).Google Scholar
Toussaint, G.T., “Pattern recognition and geometrical complexity” Proc. Fifth International Conference on Pattern Recognition Miami Beach1324–1347 (12, 1980).Google Scholar