Separation of two monotone polygons in linear time
- 1 October 1984
- journal article
- research article
- Published by Cambridge University Press (CUP) in Robotica
- Vol. 2 (4) , 215-220
- https://doi.org/10.1017/s0263574700008924
Abstract
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.Keywords
This publication has 7 references indexed in Scilit:
- On Removing a Ball Without Disturbing the OthersMathematics Magazine, 1984
- On translating a set of line segmentsComputer Vision, Graphics, and Image Processing, 1983
- Visibility of a simple polygonComputer Vision, Graphics, and Image Processing, 1983
- Testing a simple polygon for monotonicityInformation Processing Letters, 1981
- A linear algorithm for computing the visibility polygon from a pointJournal of Algorithms, 1981
- On translating a set of rectanglesPublished by Association for Computing Machinery (ACM) ,1980
- Geometric intersection problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1976