<p>A polyhedron is given as a set of its vertex coordinates. Is it possible to find its diameter faster than $O(n^2)$?</p>

<p>Or, maybe, some another common polyhedron representation would help fasten this?</p>

CC BY-SA 3.0
2014-05-12T19:21:49.137Z
http://dl.acm.org/citation.cfm?id=336215 $O(n\log n)$.
Andrew D. King
CC BY-SA 3.0
2014-05-12T19:23:28.603Z
http://www.inf.ethz.ch/personal/gaertner/miniball.html
sshilovsky
CC BY-SA 3.0
2014-05-13T01:15:41.883Z
sshilovsky: miniball is a different problem, and is easier to solve quickly.
David Eppstein
CC BY-SA 3.0
2014-05-13T03:57:26.067Z
And if you want a practical algorithm:
http://sarielhp.org/p/00/diam.html
Sariel Har-Peled
<graph-algorithms><polytope>
Computing diameter of a 3D polyhedron
sshilovsky
# Computing diameter of a 3D polyhedron

(Asked by: username_0 on 2014-05-12)

A polyhedron is given as a set of its vertex coordinates. Is it possible to find its diameter faster than $O(n^2)$?

Or, maybe, some another common polyhedron representation would help fasten this?

**Tags:** graph-algorithms, polytope

> **Comments:**
> **username_1**: http://dl.acm.org/citation.cfm?id=336215 $O(n\log n)$.  
> **username_0**: http://www.inf.ethz.ch/personal/gaertner/miniball.html  
> **username_2**: username_0: miniball is a different problem, and is easier to solve quickly.  
> **username_3**: And if you want a practical algorithm: http://sarielhp.org/p/00/diam.html  

---

## 0 answers

