Improved combinatorial bounds and efficient techniques for certain motion planning problems with three degrees of freedom

DOI10.1016/0925-7721(92)90008-GMaRDI QIDQ1194309zbMATH OpenOpenAlexFDO

Authors Dan Halperin, Micha Sharir

Publication date 27 September 1992

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0925-7721(92)90008-g

zbMATH Keywords

3-dimensional spacearrangementscellscombinatorial boundscombinatorial complexitydegrees of freedommotion planning problemsobstaclessurface patchsurfacestime complexitytwo-dimensional arrangements

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• On the complexity of a single cell in certain arrangements of surfaces related to motion planning
• Approximate motion planning and the complexity of the boundary of the union of simple geometric figures
• On the general motion-planning problem with two degrees of freedom
• Almost tight upper bounds for the single cell and zone problems in the three dimensions
• On the Piano Movers' problem: IV. Various decomposable two-dimensional motion-planning problems

Cites work

• -nets and simplex range queries
• A new efficient motion-planning algorithm for a rod in two-dimensional polygonal space
• An efficient and simple motion planning algorithm for a ladder amidst polygonal barriers
• An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space
• Applications of random sampling in computational geometry. II
• Castles in the air revisited
• Combinatorial complexity bounds for arrangements of curves and spheres
• Efficient Motion Planning for an L-Shaped Object
• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• scientific article; zbMATH DE number 4060713 (Why is no real title available?)
• scientific article; zbMATH DE number 3073200 (Why is no real title available?)
• On extremal problems of graphs and generalized graphs
• On the general motion-planning problem with two degrees of freedom
• The complexity and construction of many faces in arrangements of lines and of segments
• The number of edges of many faces in a line segment arrangement
• Triangles in space or building (and analyzing) castles in the air

Cited in

(7)

• Approximate motion planning and the complexity of the boundary of the union of simple geometric figures
• On the general motion-planning problem with two degrees of freedom
• On arrangements of Jordan arcs with three intersections per pair
• On the complexity of a single cell in certain arrangements of surfaces related to motion planning
• Models and motion planning
• Robot motion planning and the single cell problem in arrangements
• scientific article; zbMATH DE number 1984329 (Why is no real title available?)

This page was built for publication: Improved combinatorial bounds and efficient techniques for certain motion planning problems with three degrees of freedom

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1194309)