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?
4
-
4$\begingroup$ dl.acm.org/citation.cfm?id=336215 $O(n\log n)$. $\endgroup$– Andrew D. KingMay 12, 2014 at 19:21
-
$\begingroup$ inf.ethz.ch/personal/gaertner/miniball.html $\endgroup$– sshilovskyMay 12, 2014 at 19:23
-
$\begingroup$ sshilovsky: miniball is a different problem, and is easier to solve quickly. $\endgroup$– David EppsteinMay 13, 2014 at 1:15
-
$\begingroup$ And if you want a practical algorithm: sarielhp.org/p/00/diam.html $\endgroup$– Sariel Har-PeledMay 13, 2014 at 3:57
Add a comment
|