Almost tight upper bounds for the single cell and zone problems in the three dimensions

DOI10.1007/BF02570714zbMath0839.93056OpenAlexW1994720529MaRDI QIDQ1906044

Dan Halperin, Micha Sharir

Publication date: 23 June 1996

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

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

zbMATH Keywords

motion planningrobot systemsalgebraic surface patchescombinatorial complexity of a cell

Mathematics Subject Classification ID

Geometric methods (93B27) Automated systems (robots, etc.) in control theory (93C85)

Related Items (7)

Computing the Betti numbers of arrangements via spectral sequences ⋮ 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 ⋮ On the union of cylinders in three dimensions ⋮ Robot motion planning ⋮ Extremal problems on triangle areas in two and three dimensions ⋮ Polyhedral Assembly Partitioning Using Maximally Covered Cells in Arrangements of Convex Polytopes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis
• Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences
• Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
• On \(k\)-sets in arrangements of curves and surfaces
• Arrangements of curves in the plane --- topology, combinatorics, and algorithms
• On the zone of a surface in a hyperplane arrangement
• On the general motion-planning problem with two degrees of freedom
• On the complexity of a single cell in certain arrangements of surfaces related to motion planning
• On the sum of squares of cell complexities in hyperplane arrangements
• Castles in the air revisited
• New bounds for lower envelopes in three dimensions, with applications to visibility in terrains
• Almost tight upper bounds for lower envelopes in higher dimensions
• Applications of random sampling in computational geometry. II
• Vertical decompositions for triangles in 3-space
• On the two-dimensional Davenport-Schinzel problem
• Triangles in space or building (and analyzing) castles in the air
• On the Zone Theorem for Hyperplane Arrangements
• Differential Topology
• Computing a Face in an Arrangement of Line Segments and Related Problems
• The maximum numbers of faces of a convex polytope

This page was built for publication: Almost tight upper bounds for the single cell and zone problems in the three dimensions