Combinatorial complexity of translating a box in polyhedral 3-space

We study the space of free translations of a box amidst polyhedral obstacles with <italic>n</italic> features. We show that the combinatorial complexity of this space is <italic>O(n<supscrpt>2</supscrpt>α(n))</italic> where <italic>α(n)</italic> is the inverse Ackermann function. Our bound is within an <italic>α(n)</italic> factor off the lower bound, and it constitutes an improvement of almost an order of magnitude over the best previously known (and naive) bound for this problem, <italic>O(n<supscrpt>3</supscrpt>)</italic>.

• Publication year

  1993

• Venue

  SCG '93

• Publication date

  1993-07-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/160985.160992
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Planning a purely translational motion for a convex object in two-dimensional space using generalized Voronoi diagrams

  2016cited by this paper
• ALGORITHMIC MOTION PLANNING

  2016cited by this paper
• On the general motion-planning problem with two degrees of freedom

  2015cited by this paper
• On critical orientations in the kedem-sharir motion planning algorithm

  1997cited by this paper
• On translational motion planning in 3-space

  1994influential reference
• Almost tight upper bounds for the single cell and zone problems in three dimensions

  1994cited by this paper
• The union of convex polyhedra in three dimensions

  1993cited by this paper
• A Convex Polygon Among Polygonal Obstacles: Placement and High-clearance Motion

  1993cited by this paper
• Algorithmic motion planning via arrangements of curves and of surfaces

  1992cited by this paper
• Castles in the air revisited

  1992influential reference
• Algorithmic motion planning in robotics

  1991cited by this paper
• An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space

  1990cited by this paper
• Rapid Prototyping in Software Development

  1989cited by this paper
• Efficient algorithms for planning purely translational collision-free motion in two and three dimensions

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

  1987influential reference
• Algorithmic and geometric aspects of robotics

  1987cited by this paper
• Nonlinearity of davenport—Schinzel sequences and of generalized path compression schemes

  1986cited by this paper
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles

  1986cited by this paper

• On the complexity of the free space of a translating box in R^3

  2025cites this paper
• On the complexity of the free space of a translating square in R^3

  2025cites this paper
• Fuzzy Motion Planning for Nonholonomic Mobile Robot Navigation in Unknown Indoor Environments

  2018cites this paper
• 50 ALGORITHMIC MOTION PLANNING

  2016cites this paper
• 28 Arrangements

  2016cites this paper
• ALGORITHMIC MOTION PLANNING

  2016cites this paper
• State of the Union (of geometric objects)

  2008cites this paper
• Sampling-based robot motion planning: Towards realistic applications

  2007cites this paper
• State of the Union ( of Geometric Objects ) : A Review ∗

  2007cites this paper
• Combinatorial Geometry with Algorithmic Applications

  2006cites this paper
• Pianos are not flat: rigid motion planning in three dimensions

  2005cites this paper
• The Union of Congruent Cubes in Three Dimensions

  2003cites this paper
• Translating a convex polyhedron over monotone polyhedra

  2002cites this paper
• The union of congruent cubes in three dimensions

  2001cites this paper
• Arrangements and Their Applications

  2000cites this paper
• Recent Developments in the Theory of Arrangements of Surfaces

  1999cites this paper
• The union of moving polygonal pseudodiscs - Combinatorial bounds and applications

  1998cites this paper
• On Translational Motion Planning of a Convex Polyhedron in 3-Space

  1997influential citation
• Arrangements and their applications in robotics: recent developments

  1995influential citation
• Planning, calibration and collision-avoidance for image-guided radiosurgery

  1994cites this paper
• On translational motion planning in 3-space

  1994cites this paper
• Planning for Image-Guided Radiosurgery

  1994cites this paper