Carregant...
Carregant...

Vés al contingut (premeu Retorn)

The 1-Center and 1-Highway Problem

Autor
Díaz, J.; Korman, M.; Pérez, P.; Ventura, I.
Tipus d'activitat
Presentació treball a congrés
Nom de l'edició
XIV Spanish Meeting on Computational Geometry
Any de l'edició
2011
Data de presentació
2012
Llibre d'actes
Computational Geometry: XIV Spanish Meeting on Computational Geometry, EGC 2011, dedicated to Ferran Hurtado on the occasion of His 60th birthday, Alcalá de Henares, Spain, June 27-30, 2011: revised selected papers
Pàgina inicial
155
Pàgina final
165
Editor
Springer
Repositori
http://hdl.handle.net/2117/18607 Obrir en finestra nova
URL
http://link.springer.com/chapter/10.1007%2F978-3-642-34191-5_15 Obrir en finestra nova
Resum
In this paper we extend the Rectilinear 1-center as follows: Given a set S of n points in the plane, we are interested in locating a facility point f and a rapid transit line (highway) H that together minimize the expression max p ∈ S d H (p,f), where d H (p,f) is the travel time between p and f. A point p ∈ S uses H to reach f if H saves time for p. We solve the problem in O(n 2) or O(nlogn) time, depending on whether or not the highway’s length is fixed.
Citació
Díaz, J. [et al.]. The 1-Center and 1-Highway Problem. A: Spanish Meeting on Computational Geometry. "Computational Geometry: XIV Spanish Meeting on Computational Geometry, EGC 2011, dedicated to Ferran Hurtado on the occasion of His 60th birthday, Alcalá de Henares, Spain, June 27-30, 2011: revised selected papers". Alcalá de Henares (Madrid): Springer, 2011, p. 155-165.
Paraules clau
Facility location, Geometric optimization, Time metric

Participants

  • Díaz Bañez, José Miguel  (autor ponent)
  • Korman Cozzetti, Matias  (autor ponent)
  • Pérez Lantero, Pablo  (autor ponent)
  • Ventura, Immaculada  (autor ponent)