Triangles in space or building (and analyzing) castles in the air

DOI10.1007/BF02123007zbMath0717.68099OpenAlexW2009564521MaRDI QIDQ2638823

Boris Aronov, Micha Sharir

Publication date: 1990

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02123007

zbMATH Keywords

combinatorial complexitytrianglesnon-convex cells

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

Castles in the air revisited, Exact Minkowksi sums of polyhedra and exact and efficient decomposition of polyhedra into convex pieces, 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, Triangulating a nonconvex polytope, Combinatorial complexity bounds for arrangements of curves and spheres, The upper envelope of piecewise linear functions: Algorithms and applications, Union of Hypercubes and 3D Minkowski Sums with Random Sizes., Arrangements of curves in the plane --- topology, combinatorics, and algorithms, Counting facets and incidences, Improved combinatorial bounds and efficient techniques for certain motion planning problems with three degrees of freedom, The number of edges of many faces in a line segment arrangement, Quasi-optimal upper bounds for simplex range searching and new zone theorems, Strategies for polyhedral surface decomposition: an experimental study., Union of hypercubes and 3D Minkowski sums with random sizes, 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 lazy randomized incremental construction, On the general motion-planning problem with two degrees of freedom, Implicitly representing arrangements of lines or segments, A new technique for analyzing substructures in arrangements of piecewise linear surfaces, Robot motion planning and the single cell problem in arrangements, On the complexity of a single cell in certain arrangements of surfaces related to motion planning

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis
• Combinatorial complexity bounds for arrangements of curves and spheres
• The upper envelope of piecewise linear functions: Algorithms and applications
• On the maximal number of edges of many faces in an arrangement
• \(\epsilon\)-nets and simplex range queries
• Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
• Planar realizations of nonlinear Davenport-Schinzel sequences by segments
• Separating two simple polygons by a sequence of translations
• The number of edges of many faces in a line segment arrangement
• Implicitly representing arrangements of lines or segments
• Coordinated motion planning for two independent robots
• New applications of random sampling in computational geometry
• Constructing Arrangements of Lines and Hyperplanes with Applications
• On Translational Motion Planning of a Convex Polyhedron in 3-Space