Carregant...
Carregant...

Vés al contingut (premeu Retorn)

The geodesic diameter of polygonal domains

Autor
Bae, S.; Korman, M.; Okamoto, Y.
Tipus d'activitat
Article en revista
Revista
Discrete and computational geometry
Data de publicació
2013-09
Volum
50
Número
2
Pàgina inicial
306
Pàgina final
329
DOI
https://doi.org/10.1007/s00454-013-9527-8 Obrir en finestra nova
Repositori
http://hdl.handle.net/2117/20279 Obrir en finestra nova
Resum
This paper studies the geodesic diameter of polygonal domains having h holes and n corners. For simple polygons (i.e., h = 0), the geodesic diameter is determined by a pair of corners of a given polygon and can be computed in linear time, as shown by Hershberger and Suri. For general polygonal domains with h = 1, however, no algorithm for computing the geodesic diameter was known prior to this paper. In this paper, we present the first algorithms that compute the geodesic diameter of a given pol...
Citació
Bae, S.; Korman, M.; Okamoto, Y. The geodesic diameter of polygonal domains. "Discrete and computational geometry", Setembre 2013, vol. 50, núm. 2, p. 306-329.
Paraules clau
Convex function, Exact algorithm, Geodesic diameter, Lower envelope, Polygonal domain, Shortest path

Participants

  • Bae, SangWon  (autor)
  • Korman Cozzetti, Matias  (autor)
  • Okamoto, Yoshio  (autor)