×

Approximate motion planning and the complexity of the boundary of the union of simple geometric figures. (English) Zbl 0760.68082

It is proposed to estimate time complexity of motion planning algorithms in terms of both the problem size and the tightness parameter; the latter is intuitively the amount of scaling of the movable object which turns the problem from solvable to unsolvable or conversely.
An algorithm for motion planning of the rectangle in the plane amidst polygonal obstacles with the complexity \(O(((a/b)(1/t)+1)n\log^ 2 n)\) is proposed, where \(t\) is for tightness. For “non-tight” problems, this significantly improves the known \(\Omega(n^ 2)\) upper bounds. As a technical contribution, the complexities of boundaries of unions of some simple figures are presented. This leads to \(O((1/a)n\log^ 2 n)\) motion planning for a rectangle which may be rotated by angles less than \(a\).

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] L. P. Chew and K. Kedem, High-Clearance Motion Planning for a Convex Polygon among Polygonal Obstacles, Technical Report No. 184/90, Tel Aviv University (1990).
[2] Edelsbrunner, H.; Guibas, L.; Stolfi, J., Optimal Point Location in a Monotone Subdivision, SIAM J. Comput., 15, 317-340 (1986) · Zbl 0602.68102 · doi:10.1137/0215023
[3] Guibas, L.; Sharir, M.; Sifrony, S., On the General Motion Planning Problem with Two Degrees of Freedom, Discrete Comput. Geom., 4, 491-521 (1988) · Zbl 0685.68049 · doi:10.1007/BF02187744
[4] Kedem, K.; Livne, R.; Pach, J.; Sharir, M., On the Union of Jordan Regions and Collision-free Motion Amidst Polygonal Obstacles, Discrete Comput. Geom., 1, 59-71 (1986) · Zbl 0594.52004 · doi:10.1007/BF02187683
[5] K. Kedem and M. Sharir, An Efficient Algorithm for Planning Collision-free Translational Motion of a Convex Polygonal Object in 2-dimensional Space Amidst Polygonal Obstacles,Proc. First ACM Symp. on Computational Geometry, 1985, pp. 75-80.
[6] Kedem, K.; Sharir, M., An Efficient Motion-Planning Algorithm for a Convex Polygonal Object in Two-Dimensional Polygonal Space, Discrete Comput. Geom., 5, 43-75 (1990) · Zbl 0688.68039 · doi:10.1007/BF02187779
[7] Leven, D.; Sharir, M., Planning a Purely Translational Motion for a Convex Object in Two-Dimensional Space Using Generalized Voronoi Diagrams, Discrete Comput. Geom., 2, 9-31 (1987) · Zbl 0606.52002 · doi:10.1007/BF02187867
[8] Livne, R.; Sharir, M., On Intersection of Planar Jordan Curves (1985), New York: Courant Institute, New York
[9] Lozano-Perez, T.; Wesley, M., An Algorithm for Planning Collision-free Paths Among Polyhedral Obstacles, Comm. Assoc. Comput. Mach., 22, 560-570 (1979)
[10] Sharir, M.; Earnshaw, R. A., Davenport-Schinzel Sequences and Their Geometric Applications, Theoretical Foundations of Computer Graphics and CAD, 253-272 (1988), Berlin: Springer-Verlag, Berlin
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.