On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
Tóm tắt
Let γ1,..., γ
m
bem simple Jordan curves in the plane, and letK
1,...,K
m
be their respective interior regions. It is shown that if each pair of curves γ
i
, γ
j
,i ≠j, intersect one another in at most two points, then the boundary ofK=∩
=1
K
i
contains at most max(2,6m − 12) intersection points of the curvesγ
1, and this bound cannot be improved. As a corollary, we obtain a similar upper bound for the number of points of local nonconvexity in the union ofm Minkowski sums of planar convex sets. Following a basic approach suggested by Lozano Perez and Wesley, this can be applied to planning a collision-free translational motion of a convex polygonB amidst several (convex) polygonal obstaclesA
1,...,A
m
. Assuming that the number of corners ofB is fixed, the algorithm presented here runs in timeO (n log2
n), wheren is the total number of corners of theA
i
's.
Tài liệu tham khảo
T. Asano, T. Asano, L. Guibas, J. Hershberger, and H. Imai, Visibility polygon search and Euclidean shortest paths, Proc. 26th IEEE Symp. on Foundations of Computer Science, 1985, pp. 155–164.
R. V. Benson, Euclidean Geometry and Convexity, McGraw-Hill, 1966, pp. 97–113.
J. L. Bentley and A. Ottmann, Algorithms for reporting and counting geometric intersections, IEEE Trans. on Computers, Vol. C-28 (1979), pp. 643–647.
P. Erdős and B. Grünbaum, Osculation vertices in arrangements of curves, Geometriae Dedicata 1 (1973) 322–333.
B. Grünbaum, Arrangements and Spreads, Regional Conference Series in Mathematics, Vol. 10, Conference Board of the Mathematical Sciences, American Mathematical Society, Providence R.I. 1972.
M. D. Guay and D. C. Kay, On sets having finitely many points of local nonconvexity, Israel J. Math. 8 (1970), 39–52.
L. Guibas, L. Ramshaw, and J. Stolfi, A kinetic approach to computational geometry, Proc. 24th IEEE Symp. on Foundations of Computer Science, 1983, 100–111.
H. Imai, M. Iri, and K. Murota, Voronoi diagram in the Laguerre geometry and its applications, Tech. Rept. RMI 83-02, Dept. of Mathematical Engineering and Instrumentation Physics, University of Tokyo.
D. G. Kirkpatrick, Optimal search in planar subdivisions, SIAM J. Computing 12 (1983), 28–35.
D. Leven and M. Sharir, An efficient and simple motion planning algorithm for a ladder moving in two-dimensional space amidst polygonal barriers, Tech. Rept. 84-014, The Eskenasy Institute of Computer Science, Tel Aviv University, November 1984.
T. Lozano-Perez and M. Wesley, An algorithm for planning collision-free paths among polyhedral obstacles, Comm. ACM 22 (1979), 560–570.
E. E. Moise, Geometric Topology in Dimension 2 and 3, Springer-Verlag, New York, 1977.
J. Nievergelt and F. P. Preparata, Plane sweeping algorithms for intersecting geometric figures, Comm. ACM 25 (1982), 739–747.
C. Ó'Dúnlaing, M. Sharir, and C. Yap, Generalized Voronoi diagrams for a ladder: I. Topological analysis, Tech. Rept. 139, Computer Science Dept., Courant Institute, November 1984.
C. Ó'Dúnlaing, M. Sharir, and C. Yap, Generalized Voronoi diagrams for a ladder: II. Efficient construction of the diagram, Tech. Rept. 140, Computer Science Dept., Courant Institute, November 1984.
C. Ó'Dúnlaing and C. K. Yap, A ‘retraction’ method for planning the motion of a disc, J. of Algorithms 6 (1985) 104–111.
T. Ottmann, P. Widmeyer, and D. Wood, A fast algorithm for boolean mask operations, Inst. f. Angewandte Mathematik und Formale Beschreibungsverfahren, D-7500 Karlsruhe, Rept. No. 112, 1982.
J. T. Schwartz and M. Sharir, On the “Piano Movers” problem: I. The case of a two dimensional rigid polygonal body moving amidst polygonal barriers, Comm. Pure and Appl. Math. 36 (1983), 345–398.
M. Sharir, Intersection and closest-pair problems for a set of planar discs, SIAM J. Computing 14 (1985), 448–468.
S. Sifrony and M. Sharir, A new efficient motion planning algorithm for a rod in two-dimensional polygonal space, Tech. Rept. 40/85, The Eskenasy Institute of Computer Sciences, Tel Aviv University, August 1985.
G. T. Toussaint, On translating a set of spheres, Tech. Rept. SOCS-84.4, School of Computer Science, McGill University, March 1984.
E. Welzl, Constructing the visibility graph forn line segments inO(n 2) time, Inf. Proc. Letters 20 (1985), 167–172.
F. Aurenhammer, Power diagrams: properties, algorithms, and applications, Tech. Rept. F120, IIG, Tech. Univ. of Graz, Austria, 1983.