On the complexity of a single cell in certain arrangements of surfaces related to motion planning

DOI10.1007/BF02573992zbMath0791.68162OpenAlexW2122272881MaRDI QIDQ1314439

Dan Halperin

Publication date: 28 July 1994

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

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

zbMATH Keywords

arrangementscombinatorial complexitymotion-planning problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35)

Related Items

Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications, Almost tight upper bounds for the single cell and zone problems in the three dimensions, On the union of cylinders in three dimensions, Robot motion planning and the single cell problem in arrangements

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity and construction of many faces in arrangements of lines and of segments
• The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
• Planar realizations of nonlinear Davenport-Schinzel sequences by segments
• A new efficient motion-planning algorithm for a rod in two-dimensional polygonal space
• Separating two simple polygons by a sequence of translations
• Counting facets and incidences
• Improved combinatorial bounds and efficient techniques for certain motion planning problems with three degrees of freedom
• On the general motion-planning problem with two degrees of freedom
• An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space
• Triangles in space or building (and analyzing) castles in the air
• An efficient and simple motion planning algorithm for a ladder amidst polygonal barriers
• Efficient Motion Planning for an L-Shaped Object
• Power Diagrams: Properties, Algorithms and Applications