On the number of critical free contacts of a convex polygonal object moving in two-dimensional polygonal space

DOI10.1007/BF02187883zbMath0616.52009OpenAlexW2089567570MaRDI QIDQ1821354

Daniel Leven, Micha Sharir

Publication date: 1987

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131022

zbMATH Keywords

convex polygoncomputational geometrygeometric complexitymotion-planningcritical free contact

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Other problems of combinatorial convexity (52A37) Discrete mathematics in relation to computer science (68R99) Polytopes and polyhedra (52Bxx)

Related Items (18)

Extremal polygon containment problems ⋮ Planar realizations of nonlinear Davenport-Schinzel sequences by segments ⋮ On the two-dimensional Davenport-Schinzel problem ⋮ Separating two simple polygons by a sequence of translations ⋮ Improved lower bounds on the length of Davenport-Schinzel sequences ⋮ A survey of motion planning and related geometric algorithms ⋮ A near-quadratic algorithm for planning the motion of a polygon in a polygonal environment ⋮ Combinatorial complexity of translating a box in polyhedral 3-space ⋮ Enumerating Davenport-Schinzel sequences ⋮ Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences ⋮ Stabbing Convex Polygons with a Segment or a Polygon ⋮ Polygon placement under translation and rotation ⋮ On critical orientations in the Kedem-Sharir motion planning algorithm ⋮ A convex polygon among polygonal obstacle: Placement and high-clearance motion ⋮ An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space ⋮ A near-linear algorithm for the planar segment-center problem ⋮ The union of moving polygonal pseudodiscs -- combinatorial bounds and applications ⋮ The complexity of the free space for a robot moving amidst fat obstacles

Cites Work

• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
• Planning a purely translational motion of a convex object in two- dimensional space using generalized Voronoi diagrams
• Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
• Improved lower bounds on the length of Davenport-Schinzel sequences
• An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space
• On the “piano movers'” problem I. The case of a two-dimensional rigid polygonal body moving amidst polygonal barriers
• On a problem of Davenport and Schinzel

This page was built for publication: On the number of critical free contacts of a convex polygonal object moving in two-dimensional polygonal space