zbMATH — the first resource for mathematics

The 1-center and 1-highway problem. (English) Zbl 1374.90284
Márquez, Alberto (ed.) et al., 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. Berlin: Springer (ISBN 978-3-642-34190-8/pbk). Lecture Notes in Computer Science 7579, 155-165 (2012).
Summary: 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 \in S } d _{H }(p,f)\), where \(d_{H}(p,f)\) is the travel time between \(p\) and \(f\). A point \(p \in S\) uses \(H\) to reach \(f\) if \(H\) saves time for \(p\). We solve the problem in \(O(n^{2})\) or \(O(n\log n)\) time, depending on whether or not the highway’s length is fixed.
For the entire collection see [Zbl 1253.68016].

90B85 Continuous location
Full Text: DOI
[1] Abellanas, M., Hurtado, F., Icking, C., Klein, R., Langetepe, E., Ma, L., Palop, B., Sacristán, V.: Voronoi diagram for services neighboring a highway. Information Processing Letters 86(5), 283–288 (2003) · Zbl 1162.68725 · doi:10.1016/S0020-0190(02)00505-7
[2] Ahn, H.-K., Alt, H., Asano, T., Bae, S.W., Brass, P., Cheong, O., Knauer, C., Na, H.-S., Shin, C.-S., Wolff, A.: Constructing optimal highways. Int. J. Found. Comput. Sci. 20(1), 3–23 (2009) · Zbl 1171.90443 · doi:10.1142/S0129054109006425
[3] Aichholzer, O., Aurenhammer, F., Palop, B.: Quickest paths, straight skeletons, and the city Voronoi diagram. Discrete & Computational Geometry 31, 17–35 (2004) · Zbl 1159.68614 · doi:10.1007/s00454-003-2947-0
[4] Aloupis, G., Cardinal, J., Collette, S., Hurtado, F., Langerman, S., O’Rourke, J., Palop, B.: Highway hull revisited. Computational Geometry: Theory and Applications 43, 115–130 (2010) · Zbl 1179.90028 · doi:10.1016/j.comgeo.2009.06.001
[5] Bae, S.W., Korman, M., Tokuyama, T.: All Farthest Neighbors in the Presence of Highways and Obstacles. In: Das, S., Uehara, R. (eds.) WALCOM 2009. LNCS, vol. 5431, pp. 71–82. Springer, Heidelberg (2009) · Zbl 1211.68461 · doi:10.1007/978-3-642-00202-1_7
[6] Bajaj, C.: Proving geometric algorithm non-solvability: An application of factoring polynomials. J. Symb. Comput. 2(1), 99–102 (1986) · doi:10.1016/S0747-7171(86)80015-3
[7] Battaudatta, R., Rajan, S.P.: Mixed planar/network facility location problems. Computers & Operations Research 15, 61–67 (1988) · Zbl 0628.90022 · doi:10.1016/0305-0548(88)90029-9
[8] Bespamyatnikh, S., Kirkpatrick, D.: Rectilinear 2-center Problems. In: Proc. 11th Canadian Conference on Computational Geometry, pp. 68–71 (1999)
[9] Bespamyatnikh, S., Segal, M.: Rectilinear Static and Dynamic Discrete 2-Center Problems. In: Dehne, F., Gupta, A., Sack, J.-R., Tamassia, R. (eds.) WADS 1999. LNCS, vol. 1663, pp. 276–287. Springer, Heidelberg (1999) · Zbl 1063.68678 · doi:10.1007/3-540-48447-7_28
[10] Cardinal, J., Collette, S., Hurtado, F., Langerman, S., Palop, B.: Optimal location of transportation devices. Computational Geometry: Theory and Applications 41, 219–229 (2008) · Zbl 1163.90359 · doi:10.1016/j.comgeo.2008.01.001
[11] Carrizosa, E., Rodríguez-Chía, A.M.: Weber problems with alternative transportation systems. European Journal of Operational Research 97(1), 87–93 (1997) · Zbl 0923.90111 · doi:10.1016/S0377-2217(96)00066-5
[12] Díaz-Báñez, J.-M., Korman, M., Pérez-Lantero, P., Ventura, I.: Locating a service facility and a rapid transit line. CoRR, abs/1104.0753 (2011) · Zbl 1374.90283
[13] Díaz-Báñez, J.-M., Korman, M., Pérez-Lantero, P., Ventura, I.: Locating a single facility and a high-speed line. CoRR, abs/1205.1556 (2012) · Zbl 1338.90212
[14] Díaz-Báñez, J.-M., Korman, M., Pérez-Lantero, P., Ventura, I.: The 1-Center and 1-Highway problem. CoRR, abs/1205.1882 (2012)
[15] Díaz-Báñez, J.M., Mesa, J.A., Schobel, A.: Continuous location of dimensional structures. European Journal of Operational Research 152, 22–44 (2002) · Zbl 1040.90021 · doi:10.1016/S0377-2217(02)00647-1
[16] Drezner, Z.: On the rectangular p-center problem. Naval Research Logistics (NRL) 34(2), 229–234 (1987) · Zbl 0614.90034 · doi:10.1002/1520-6750(198704)34:2<229::AID-NAV3220340207>3.0.CO;2-1
[17] Drezner, Z., Hamacher, H.W.: Facility location – applications and theory. Springer (2002) · Zbl 0988.00044 · doi:10.1007/978-3-642-56082-8
[18] Eppstein, D.: Faster construction of planar two-centers. In: Proc. of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1997, pp. 131–138 (1997) · Zbl 1321.68500
[19] Espejo, I., Rodríguez-Chía, A.M.: Simultaneous location of a service facility and a rapid transit line. Computers and Operations Research 38, 525–538 (2011) · Zbl 1231.90274 · doi:10.1016/j.cor.2010.07.013
[20] Feder, T., Greene, D.: Optimal algorithms for approximate clustering. In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC 1988, pp. 434–444. ACM, New York (1988) · doi:10.1145/62212.62255
[21] Huang, P.-H., Tsai, Y.T., Tang, C.Y.: A fast algorithm for the alpha-connected two-center decision problem. Inf. Process. Lett. 85(4), 205–210 (2003) · Zbl 1173.68720 · doi:10.1016/S0020-0190(02)00402-7
[22] Korman, M.: Theory and Applications of Geometric Optimization Problems in Rectilinear Metric Spaces. PhD thesis, Tohoku University (2009); Committee: Nishizeki, T., Shinohara, A., Shioura, A., Tokuyama, T.
[23] Korman, M., Tokuyama, T.: Optimal Insertion of a Segment Highway in a City Metric. In: Hu, X., Wang, J. (eds.) COCOON 2008. LNCS, vol. 5092, pp. 611–620. Springer, Heidelberg (2008) · Zbl 1148.68550 · doi:10.1007/978-3-540-69733-6_60
[24] Laporte, G., Mesa, J.A., Ortega, F.A.: Optimization methods for the planning of rapid transit systems. European Journal of Operational Research 122, 1–10 (2000) · Zbl 0968.90027 · doi:10.1016/S0377-2217(99)00016-8
[25] Plastria, F.: Continuous location problems. In: Drezner, Z. (ed.) Facility Location: A Survey of Applications and Methods, pp. 225–262. Springer (1995) · doi:10.1007/978-1-4612-5355-6_12
[26] Robert, J.-M., Toussaint, G.: Computational Geometry and Facility Location. In: Proc. Inter. Conference on Operations Research and Management Science, pp. 11–15 (1990)
[27] Woeginger, G.J.: A comment on a minmax location problem. Operations Research Letters 23(1-2), 41–43 (1998) · Zbl 0957.90083 · doi:10.1016/S0167-6377(98)00033-9
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.