scientific article; zbMATH DE number 3926242
From MaRDI portal
Publication:3700833
[For the entire collection see Zbl 0568.00020.] Let P and Q be polyhedra one of which is convex. Let n and m be the number of edges of P and Q respectively and let s be the number of edges of the intersection \(P\cap Q\). We show how to compute \(P\cap Q\) in time \(O((n+m+s)\log (n+m+s))\). Previously only algorithms with running time O(nm) were known.
Recommendations
- A complete and efficient algorithm for the intersection of a general and a convex polyhedron
- Optimal detection of intersections between convex polyhedra
- scientific article; zbMATH DE number 6789228
- A simpler linear-time algorithm for intersecting two convex polyhedra in three dimensions
- A simple linear algorithm for intersecting convex polygons
Cited in
(10)- A new O(n \,n) algorithm for computing the intersection of convex polygons
- The shortest watchtower and related problems for polyhedral terrains
- A simple linear algorithm for intersecting convex polygons
- EDGE ADVANCING RULES FOR INTERSECTING SPHERICAL CONVEX POLYGONS
- A complete and efficient algorithm for the intersection of a general and a convex polyhedron
- On ray shooting for triangles in 3-space and related problems
- Optimal detection of intersections between convex polyhedra
- A simpler linear-time algorithm for intersecting two convex polyhedra in three dimensions
- Fast detection of polyhedral intersection
- An n log n algorithm for determining the congruity of polyhedra
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3700833)