Vés al contingut (premeu Retorn)

Computational geometry seminar: Computing the L1 Geodesic Diameter and Center of a Polygonal Domain

25/02/2016 de 13:00 a 14:00
Room S215 Omega Building, Campus Nord UPC
Més informació

Room S215 Omega Building, Campus Nord UPC (equiv.: Room 215 Floor Speaker:**Matias Korman Tokuyama Laboratory, Tohoku University (Japan)

Abstract: For a polygonal domain of h holes with a total of n vertices, we present algorithms that compute the L1 geodesic diameter in O(n^2+h^4) time and the L1 geodesic center in O((n^4+n2 h^4)α(n)) time, where α(·) denotes the inverse Ackermann function. No algorithms were known for these problems before. For the Euclidean counterpart, the best algorithms compute the geodesic diameter in O(n^7.73) or O(n^7(h + log n)) time, and compute the geodesic center in O(n^12+ε) time. Therefore, our algorithms are much faster than the algorithms for the Euclidean problems. Our algorithms are based on several interesting observations on L1 shortest paths in polygonal domains. 

Activities are regularly announced at