Computing the intersection-depth to polyhedra

DOI10.1007/BF01190153zbMath0797.68162OpenAlexW1999134477MaRDI QIDQ2366234

Subhash Suri, David G. Kirkpatrick, David P. Dobkin, J. E. Hershberger

Publication date: 29 June 1993

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

Minkowski sumintersectionplane sweepray shootingpolyhedral hierarchy

Mathematics Subject Classification ID

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

Related Items

Distance measures on intersecting objects and their applications, Fast neighborhood search for two- and three-dimensional nesting problems, Coordinate descent heuristics for the irregular strip packing problem of rasterized shapes, An efficient and robust contact algorithm for a compliant contact force model between bodies of complex geometry, An emergent computation approach to the problem of polygon layout with performance constraints, Minimizing the error of linear separators on linearly inseparable data, Input design for guaranteed fault diagnosis using zonotopes, Interactive generalized penetration depth computation for rigid and articulated models using object norm, Extended local search algorithm based on nonlinear programming for two-dimensional irregular strip packing problem, Witness (Delaunay) graphs, Efficient distance computation in configuration space, Rotational polygon overlap minimization and compaction, A zonotopic set-invariance analysis of replay attacks affecting the supervisory layer, Solving the irregular strip packing problem via guided local search for overlap minimization, An iterated local search algorithm based on nonlinear programming for the irregular strip packing problem, Densest translational lattice packing of non-convex polygons, A new approach for sheet nesting problem using guided cuckoo search and pairwise clustering

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear-time algorithm for computing the Voronoi diagram of a convex polygon
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
• Triangulating a simple polygon
• Algorithms for Reporting and Counting Geometric Intersections
• Optimal Algorithms for the Intersection and the Minimum Distance Problems Between Planar Polygons
• A linear algorithm for determining the separation of convex polyhedra
• Optimal Point Location in a Monotone Subdivision
• Computing the extreme distances between two convex polygons
• Polygon containment under translation
• An O(n2) shortest path algorithm for a non-rotating convex body
• A linear algorithm for computing the visibility polygon from a point
• Optimal Search in Planar Subdivisions