No label defined (Q3700833)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3926242
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3926242 |
Statements
1985
0 references
computational geometry
0 references
intersection
0 references
0.8372808694839478
0 references
0.8332754969596863
0 references
0.8285458087921143
0 references
0.8284552693367004
0 references
[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.
0 references