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 (25)

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

This page was built for publication: Triangles in space or building (and analyzing) castles in the air