Loading...
Loading...

Go to the content (press return)

The 1-Center and 1-Highway Problem

Author
Díaz, J.; Korman, M.; Pérez, P.; Ventura, I.
Type of activity
Presentation of work at congresses
Name of edition
XIV Spanish Meeting on Computational Geometry
Date of publication
2011
Presentation's date
2012
Book of congress proceedings
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
First page
155
Last page
165
Publisher
Springer
Repository
http://hdl.handle.net/2117/18607 Open in new window
URL
http://link.springer.com/chapter/10.1007%2F978-3-642-34191-5_15 Open in new window
Abstract
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.
Citation
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.
Keywords
Facility location, Geometric optimization, Time metric

Participants

  • Díaz Bañez, José Miguel  (author and speaker )
  • Korman Cozzetti, Matias  (author and speaker )
  • Pérez Lantero, Pablo  (author and speaker )
  • Ventura Molina, Inmaculada  (author and speaker )