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.











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)