Timeline for Source for: Geodesics in CAT(0) spaces
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 10, 2017 at 0:08 | comment | added | Joseph O'Rourke | Oh, yes, I don't mean to diminish Hayashi's achievement. But the holy grail is an exact, polynomial-time algorithm. | |
| Dec 9, 2017 at 22:21 | comment | added | Suvrit | Thanks for pointing out -- not sure if there exists a good rounding to obtain an / the exact solution. In any case, I'm typically happy with weakly polytime methods, especially those with the "luxury" of $\log(1/\epsilon)$ :-) | |
| Dec 9, 2017 at 17:57 | comment | added | Joseph O'Rourke | Thanks! Note their algorithm finds an approximation, a path of length at most $d(p,q)+\epsilon$, with the time complexity including $\log (1/\epsilon)$. I do not know if there is a polynomial-time exact algorithm. | |
| Dec 9, 2017 at 17:51 | history | answered | Suvrit | CC BY-SA 3.0 |