A linear algorithm for determining the separation of convex polyhedra
From MaRDI portal
Publication:3697818
DOI10.1016/0196-6774(85)90007-0zbMath0577.52004OpenAlexW2005538657MaRDI QIDQ3697818
David P. Dobkin, David G. Kirkpatrick
Publication date: 1985
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(85)90007-0
convex polyhedradetection problem(k-d) intersection(k-d) intersection construction problem(k-d) separation problemhierarchical description of polyhedra
Software, source code, etc. for problems pertaining to convex and discrete geometry (52-04) Inequalities and extremum problems involving convexity in convex geometry (52A40) Polytopes and polyhedra (52Bxx)
Related Items
Efficient ray shooting and hidden surface removal, Computation of penetration between smooth convex objects in three-dimensional space, Computing the intersection-depth to polyhedra, Lower bounds for intersection searching and fractional cascading in higher dimension, Approximating points by a piecewise linear function, Two alternatives for the cubic algorithm, A neural network measuring the intersection of \(m\)-dimensional convex polyhedra, Piecewise linear paths among convex obstacles, Finding the projection on a polytope: An iterative method, Minimum polygonal separation, Parallel construction of subdivision hierarchies, On Ray Shooting for Triangles in 3-Space and Related Problems, An output sensitive algorithm for discrete convex hulls, Subquadratic algorithms for succinct stable matching, Dynamic minimum bichromatic separating circle, Simplex Range Searching and Its Variants: A Review, Computational geometry in a curved world, Applications of generalized matrix searching to geometric algorithms, On separating points by lines, Parallel collision detection between moving robots for practical motion planning, Applications of a new space-partitioning technique, Outlier respecting points approximation, Dynamic point location in arrangements of hyperplanes, Algorithms for weak and wide separation of sets, Computing the shortest watchtower of a polyhedral terrain in \(O(n\log n)\) time., A linear programming-based algorithm for the signed separation of (non-smooth) convex bodies, Computing hereditary convex structures, Witness (Delaunay) graphs, Approximating nearest neighbor among triangles in convex position, COMPUTING LARGEST CIRCLES SEPARATING TWO SETS OF SEGMENTS, A simpler linear-time algorithm for intersecting two convex polyhedra in three dimensions, On determining optimal strategies in pursuit games in the plane, Space sweep solves intersection of convex polyhedra, New applications of random sampling in computational geometry, An Improved Ray Shooting Method for Constructive Solid Geometry Models Via Tree Contraction
