Castles in the air revisited

DOI10.1007/BF02574371zbMath0805.52005OpenAlexW2028491962MaRDI QIDQ1334929

Boris Aronov, Micha Sharir

Publication date: 26 September 1994

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

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

zbMATH Keywords

complexitymotion planningAckermann functioncellscombinatorial properties\(k\)-facesarrangements of simplicescastles in the airtranslative

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35)

Related Items (18)

On stabbing lines for convex polyhedra in 3D ⋮ Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications ⋮ Excess in arrangements of segments ⋮ Almost tight upper bounds for the single cell and zone problems in the three dimensions ⋮ Bounds on the size of tetrahedralizations ⋮ Vertical decompositions for triangles in 3-space ⋮ 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 ⋮ Union of Hypercubes and 3D Minkowski Sums with Random Sizes. ⋮ Counting facets and incidences ⋮ Improved combinatorial bounds and efficient techniques for certain motion planning problems with three degrees of freedom ⋮ Strategies for polyhedral surface decomposition: an experimental study. ⋮ On the zone of a surface in a hyperplane arrangement ⋮ Union of hypercubes and 3D Minkowski sums with random sizes ⋮ A new technique for analyzing substructures in arrangements of piecewise linear surfaces ⋮ Smoothed analysis of probabilistic roadmaps ⋮ Robot motion planning and the single cell problem in arrangements ⋮ On the sum of squares of cell complexities in hyperplane arrangements

Cites Work

• The complexity and construction of many faces in arrangements of lines and of segments
• The complexity of many cells in arrangements of planes and related problems
• On the Piano Movers problem. II: General techniques for computing topological properties of real algebraic manifolds
• The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis
• Arrangements of curves in the plane --- topology, combinatorics, and algorithms
• Counting facets and incidences
• The upper envelope of Voronoi surfaces and its applications
• On the zone of a surface in a hyperplane arrangement
• On the general motion-planning problem with two degrees of freedom
• On the sum of squares of cell complexities in hyperplane arrangements
• Applications of random sampling in computational geometry. II
• 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

This page was built for publication: Castles in the air revisited