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

DOI10.1007/BF02123007MaRDI QIDQ2638823zbMATH OpenOpenAlexFDO

Authors 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

trianglescombinatorial complexitynon-convex cells

Mathematics Subject Classification ID

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

Recommendations

• Vertical decompositions for triangles in 3-space
• Ray shooting on triangles in 3-space
• Castles in the air revisited
• A single cell in an arrangement of convex polyhedra in R^3
• On Point Location and Motion Planning among Simplices

Cites work

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

Cited in

(26)

• Arrangements of curves in the plane --- topology, combinatorics, and algorithms
• On lazy randomized incremental construction
• The number of edges of many faces in a line segment arrangement
• The complexity of many cells in arrangements of planes and related problems
• Combinatorial complexity bounds for arrangements of curves and spheres
• Vertical decompositions for triangles in 3-space
• A single cell in an arrangement of convex polyhedra in R^3
• A near-quadratic algorithm for planning the motion of a polygon in a polygonal environment
• Union of hypercubes and 3D Minkowski sums with random sizes
• Implicitly representing arrangements of lines or segments
• The complexity and construction of many faces in arrangements of lines and of segments
• Union of hypercubes and 3D Minkowski sums with random sizes
• A new technique for analyzing substructures in arrangements of piecewise linear surfaces
• 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
• Quasi-optimal upper bounds for simplex range searching and new zone theorems
• Strategies for polyhedral surface decomposition: an experimental study.
• Castles in the air revisited
• Exact Minkowksi sums of polyhedra and exact and efficient decomposition of polyhedra into convex pieces
• Triangulating a nonconvex polytope
• The upper envelope of piecewise linear functions: Algorithms and applications
• Improved combinatorial bounds and efficient techniques for certain motion planning problems with three degrees of freedom
• Robot motion planning and the single cell problem in arrangements
• Bounds on the size of tetrahedralizations
• Almost tight upper bounds for the single cell and zone problems in the three dimensions
• Counting facets and incidences

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2638823)