A linear algorithm for determining the separation of convex polyhedra

DOI10.1016/0196-6774(85)90007-0MaRDI QIDQ3697818zbMATH OpenOpenAlexFDO

Authors David P. Dobkin, David 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

zbMATH Keywords

(k-d) intersection(k-d) intersection construction problem(k-d) separation problemconvex polyhedradetection problemhierarchical description of polyhedra

Mathematics Subject Classification ID

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)

Recommendations

• An optimal algorithm for finding the separation of simple polygons
• A new linear algorithm for intersecting convex polygons
• A simple linear algorithm for intersecting convex polygons
• On a calculation of an arbitrary separating hyperplane of convex polyhedral sets
• scientific article; zbMATH DE number 4211553
• scientific article; zbMATH DE number 742976
• Separation and approximation of polyhedral objects
• A linear time algorithm for the computation of some distance functions between convex polygons
• A linear-time algorithm for computing the Voronoi diagram of a convex polygon
• scientific article; zbMATH DE number 741006

Cited in

(51)

• Two alternatives for the cubic algorithm
• Minimum polygonal separation
• Parallel construction of subdivision hierarchies
• Applications of a new space-partitioning technique
• Dynamic point location in arrangements of hyperplanes
• On determining optimal strategies in pursuit games in the plane
• Efficient ray shooting and hidden surface removal
• Finding the projection on a polytope: An iterative method
• An output sensitive algorithm for discrete convex hulls
• New applications of random sampling in computational geometry
• Lower bounds for intersection searching and fractional cascading in higher dimension
• A neural network measuring the intersection of m-dimensional convex polyhedra
• Piecewise linear paths among convex obstacles
• Separation and approximation of polyhedral objects
• On separating points by lines
• Computing the intersection-depth to polyhedra
• Approximating points by a piecewise linear function
• Dynamic minimum bichromatic separating circle
• Computing the shortest watchtower of a polyhedral terrain in \(O(n\log n)\) time.
• On the problem polyhedral separability: a numerical solution
• Parallel collision detection between moving robots for practical motion planning
• scientific article; zbMATH DE number 177829 (Why is no real title available?)
• Linear algorithm to find the largest intriangles of a planar convex polygon
• Computation of penetration between smooth convex objects in three-dimensional space
• An Improved Ray Shooting Method for Constructive Solid Geometry Models Via Tree Contraction
• scientific article; zbMATH DE number 1537530 (Why is no real title available?)
• Simplex Range Searching and Its Variants: A Review
• COMPUTING AN ALMOST MINIMUM SET OF SPANNING LINE SEGMENTS OF A POLYHEDRON
• COMPUTING LARGEST CIRCLES SEPARATING TWO SETS OF SEGMENTS
• scientific article; zbMATH DE number 742976 (Why is no real title available?)
• Fast Combinatorial Algorithm for Tightly Separating Hyperplanes
• On ray shooting for triangles in 3-space and related problems
• Outlier respecting points approximation
• Collision of convex objects
• Computing hereditary convex structures
• Towards the computation of the convex hull of a configuration from its corresponding separating matrix
• scientific article; zbMATH DE number 5066290 (Why is no real title available?)
• Witness (Delaunay) graphs
• A Separation Algorithm for b-Matching Degree-Sequence Polyhedra
• An algorithm to find the lineality space of the positive hull of a set of vectors
• Algorithms for weak and wide separation of sets
• On the d-independence number in 1-planar graphs
• On the independence number of 1-planar graphs
• On computing the maximum-volume bichromatic separating box
• A linear programming-based algorithm for the signed separation of (non-smooth) convex bodies
• A simpler linear-time algorithm for intersecting two convex polyhedra in three dimensions
• Convexity helps iterated search in 3D
• Space sweep solves intersection of convex polyhedra
• Computational geometry in a curved world
• Applications of generalized matrix searching to geometric algorithms
• Approximating nearest neighbor among triangles in convex position

This page was built for publication: A linear algorithm for determining the separation of convex polyhedra

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