nach oben

Erschienen in:

2015 | OriginalPaper | Buchkapitel

7. Location of Dimensional Facilities in a Continuous Space

verfasst von : Anita Schöbel

Erschienen in: Location Science

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In many cases, the facilities to be located cannot be represented by isolated points, but may be modeled as dimensional structures. Examples for one-dimensional facilities are straight lines, line segments, or circles while boxes, strips, or balls are two-dimensional facilities. The goal of this chapter is to review the location of lines and circles in the plane and the location of hyperplanes and hyperspheres in higher dimensional spaces. We also discuss the location of some other dimensional facilities. We formulate the resulting location problems, point out some of their important properties and review the basic solution techniques and algorithmic approaches. Our focus lies on presenting a unified understanding of the common characteristics these problems have, and on reviewing the new findings obtained in this field within the last 10 years.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Anti-covering Problems

Nächstes Kapitel Facility Location Under Uncertainty

Agarwal P, Efrat A, Sharir M, Toledo S (1993) Computing a segment center for a planar point set. J Algorithm 15:314–323CrossRef

Agarwal P, Aronov B, Peled S, Sharir M (1999) Approximation and exact algorithms for minimum-width annuli and shells. In: Proceedings of the 15th ACM symposium on computational geometry, pp 380–389

Agarwal P, Peled SH, Varadarajan K (2004) Approximation extent measures of points. J ACM 51:605–635

Alonso J, Martini H, Spirova M (2012a) Minimal enclosing discs, circumcircles, and circumcenters in normed planes (part I). Comput Geom Theor Appl 45:258–274CrossRef

Alonso J, Martini H, Spirova M (2012b) Minimal enclosing discs, circumcircles, and circumcenters in normed planes (part II). Comput Geom Theor Appl 45:350–369CrossRef

Bennet K, Mangasarian O (1992) Robust linear programming discrimination of two linearly inseparable sets. Optim Method Softw 1:23–34CrossRef

Bertsimas D, Shioda R (2007) Classification and regression via integer optimization. Oper Res 55:252–271CrossRef

Blanquero R, Carrizosa E, Hansen P (2009) Locating objects in the plane using global optimization techniques. Math Oper Res 34:837–858CrossRef

Blanquero R, Carrizosa E, Schöbel A, Scholz D (2011) Location of a line in the three-dimensional space. Eur J Oper Res 215:14–20CrossRef

Brimberg J, Nickel S (2009) Constructing a DC decomposition for ordered median problems. J Global Optim 45:187–201CrossRef

Brimberg J, Wesolowsky G (2000) Note: facility location with closest rectangular distances. Nav Res Log 47:77–84CrossRef

Brimberg J, Juel H, Schöbel A (2002) Linear facility location in three dimensions - models and solution methods. Oper Res 50:1050–1057CrossRef

Brimberg J, Juel H, Schöbel A (2003) Properties of 3-dimensional line location models. Ann Oper Res 122:71–85CrossRef

Brimberg J, Juel H, Schöbel A (2009a) Locating a circle on the plane using the minimax criterion. Stud Locat Anal 17:46–60

Brimberg J, Juel H, Schöbel A (2009b) Locating a minisum circle in the plane. Discrete Appl Math 157:901–912CrossRef

Brimberg J, Juel H, Körner MC, Schöbel A (2011a) Locating a general minisum ‘circle’ on the plane. 4OR-Q J Oper Res 9:351–370

Brimberg J, Juel H, Körner MC, Schöbel A (2011b) Locating an axis-parallel rectangle on a Manhattan plane. TOP 22:185–207CrossRef

Brimberg J, Juel H, Körner MC, Schöbel A (2013a) On models for continuous facility location with partial coverage. J Oper Res Soc. doi:JORS.2013.142

Brimberg J, Schieweck R, Schöbel A (2013b) Locating a median line with partial coverage distance. Preprint 32, Institut für Numerische und Angewandte Mathematik, Universität Göttingen. http://num.math.uni-goettingen.de/preprints/files/2013-32.pdf

Brodal GS, Jacob R (2002) Dynamic planar convex hull. In: Proceedings of the 43rd annual IEEE symposium on foundations of computer science, pp 617–626

Carrizosa E, Plastria F (2008) Optimal expected-distance separating halfspace. Math Oper Res 33:662–677CrossRef

Chan TM (2000) Approximating the diameter, width, smalat enclosing cylinder, and minimum-width annulus. In: Proceedings of the 16th annual symposium on computational geometry SCG ’00. ACM, New York, pp 300–309

Cheng SW (1996) Widest empty L-shaped corridor. Inform Process Lett 58:277–283CrossRef

Chernov N, Sapirstein P (2008) Fitting circles to data with correlated noise. Comput Stat Data Anal 52:5328–5337CrossRef

Coope I (1993) Circle fitting by linear and nonlinear least squares. J Optim Theory Appl 76:381–388CrossRef

Crawford J (1983) A non-iterative method for fitting circular arcs to measured points. Nucl Instrum Methods 211:223–225CrossRef

Das G, Mukhopadhyay D, Nandy S (2009) Improved algorithm for the widest empty 1-corner corridor. Inform Process Lett 109:1060–1065CrossRef

Deshpande A, Rademacher L, Vempala S, Wang G (2006) Matrix approximation and projective clustering via volume sampling. In: Proceedings of the 17th annual ACM-SIAM symposium on discrete algorithms. ACM, New York, pp 1117–1126

Dey T (1998) Improved bounds for planar k-sets and related problems. Discrete Comput Geom 19:373–382CrossRef

Díaz-Bánez JM, Mesa J, Schöbel A (2004) Continuous location of dimensional structures. Eur J Oper Res 152:22–44CrossRef

Díaz-Bánez JM, López MA, Sellarès JA (2006a) Locating an obnoxious plane. Eur J Oper Res 173:556–564CrossRef

Díaz-Bánez JM, López MA, Sellarès JA (2006b) On finding a widest empty 1-corner corridor. Inform Process Lett 98:199–205CrossRef

Díaz-Bánez J, Korman M, Pérez-Lantero P, Ventura I (2013) The 1-median and 1-highway problem. Eur J Oper Res 225:552–557CrossRef

Dicks DR (1985) Early Greek astronomy to aristotle (Aspects of Greek and Roman life series). Cornell University Press, Ithaca

Drezner Z, Brimberg J (2014) Fitting concentric circles to measurements. Math Method Oper Res 29:119–133CrossRef

Drezner T, Drezner Z (2007) Equity models in planar location. Comput Manag Sci 4:1–16CrossRef

Drezner Z, Suzuki A (2004) The big triangle small triangle method for the solution of non-convex facility location problems. Oper Res 52:128–135CrossRef

Drezner Z, Klamroth K, Schöbel A, Wesolowsky G (2001) The weber problem, chap 1. In: Drezner Z, Hamacher H (eds) Facility location - applications and theory. Springer, Berlin/Heidelberg, pp 1–36

Drezner Z, Steiner S, Wesolowsky G (2002) On the circle closest to a set of points. Comput Oper Res 29:637–650CrossRef

Ebara H, Fukuyama N, Nakano H, Nakanishi Y (1989) Roundness algorithms using the voronoi diagrams. In: Proceedings of the 1st Canadian conference on computational geometry, p 41

Edelsbrunner H (1985) Finding transversals for sets of simple geometric figures. Theor Comput Sci 35:55–69CrossRef

Efrat A, Sharir M (1996) A near-linear algorithm for the planar segment-center problem. Discrete Comput Geom 16:239–257CrossRef

Espejo I, Rodríguez-Chía A (2011) Simultaneous location of a service facility and a rapid transit line. Comput Oper Res 38:525–538CrossRef

Espejo I, Rodríguez-Chía A (2012) Simultaneous location of a service facility and a rapid transit line. Comput Oper Res 39:2899–2903CrossRef

Farago F, Curtis M (1994) Handbook of dimensional measurement, 3rd edn. Industrial Press, New York

Gander W, Golub G, Strebel R (1994) Least-squares fitting of circles and ellipses. BIT 34:558–578CrossRef

García-López J, Ramos P, Snoeyink J (1998) Fitting a set of points by a circle. Discrete Comput Geom 20:389–402CrossRef

Gluchshenko O (2008) Annulus and center location problems. Ph.D. thesis, Technische Universität Kaiserslautern

Gluchshenko ON, Hamacher HW, Tamir A (2009) An optimal o(nlogn) algorithm for finding an enclosing planar rectilinear annulus of minimum width. Oper Res Lett 37:168–170CrossRef

Golub G, van Loan C (1980) An analysis of the total least squares problem. SIAM J Numer Anal 17:883–893CrossRef

Hamacher H, Nickel S (1995) Restricted planar location problems and applications. Nav Res Log 42:967–992CrossRef

Har-Peled S, Varadarajan K (2002) Projective clustering in high dimensions using core-sets. In: Proceedings of the 18th annual symposium on computational geometry. ACM, New York, pp 312–318

Helly E (1923) Über Mengen konvexer Körper mit gemeinschaftlichen Punkten. Jahrb Dtsch Math Ver 32:175–176

Houle M, Toussaint G (1985) Computing the width of a set. In: Proceedings of the 1st ACM symposium on computational geometry, pp 1–7

Imai H, Lee D, Yang CD (1992) 1-Segment center problems. ORSA J Comput 4:426–434CrossRef

Janardan R, Preparata F (1996) Widest-corridos problems. Nord J Comput 1:231–245

Kapelushnik L (2008) Computing the k-centrum and the ordered median hyperplane. Master’s thesis, School of Computer Science, Tel-Aviv University

Kasa I (1976) A circle fitting procedure and its error analysis. IEEE T Instrum Meas 25:8–14CrossRef

Kelachankuttu H, Batta R, Nagi R (2007) Contour line construction for a new rectangular facility in an existing layout with rectangular departments. Eur J Oper Res 180:149–162CrossRef

Korneenko N, Martini H (1990) Approximating finite weighted point sets by hyperplanes. In: SWAT90. Lecture notes in computer science, vol 447. Springer, pp 276–286

Korneenko N, Martini H (1993) Hyperplane approximation and related topics. In: Pach J (ed) New trends in discrete and computational geometry. Springer, New York, pp 135–162CrossRef

Körner MC (2011) Minisum hyperspheres. Springer, New YorkCrossRef

Körner MC, Brimberg J, Juel H, Schöbel A (2009) General circle location. In: Proceedings of the 21st Canadian conference on computational geometry, pp 111–114

Körner MC, Brimberg J, Juel H, Schöbel A (2011) Geometric fit of a point set by generalized circles. J Global Optim 51:115–132CrossRef

Körner MC, Martini H, Schöbel A (2012) Minisum hyperspheres in normed spaces. Discrete Appl Math 16:2221–2233CrossRef

Krempasky T (2012) Locating median lines and hyperplanes with a restriction on the slope. Ph.D. thesis, Universität Göttingen

Le V, Lee D (1991) Out-of-roundness problem revisited. IEEE Trans Pattern Anal 13:217–223CrossRef

Lee D, Ching Y (1985) The power of geometric duality revisited. Inform Process Lett 21:117–122CrossRef

Lozano AJ, Plastria F (2009) The ordered median Euclidean straight-line location problem. Stud Locat Anal 17:29–43

Lozano AJ, Mesa J, Plastria F (2010) The k-centrum straight-line location problem. J Math Model Algorithms 9:1–17CrossRef

Lozano AJ, Mesa J, Plastria F (2013) Location of weighted anti-ordered median straight lines with euclidean distances. Discrete Appl Math. doi:10.1016/j.dam.2013.04.016

Mangasarian O (1999) Arbitrary-norm separating plane. Oper Res Lett 24:15–23CrossRef

Martini H, Schöbel A (1998) Median hyperplanes in normed spaces—a survey. Discrete Appl Math 89:181–195CrossRef

Martini H, Schöbel A (1999) A characterization of smooth norms. Geom Dedicata 77:173–183CrossRef

Megiddo N (1984) Linear programming in linear time when the dimension is fixed. J ACM 31:114–127CrossRef

Megiddo N, Tamir A (1982) On the complexity of locating linear facilities in the plane. Oper Res Lett 1:194–197CrossRef

Megiddo N, Tamir A (1983) Finding least-distance lines. SIAM J Algebr Discrete Method 4:207–211CrossRef

Morris J, Norback J (1980) A simple approach to linear facility location. Transp Sci 14:1–8CrossRef

Morris J, Norback J (1983) Linear facility location - solving extensions of the basic problem. Eur J Oper Res 12:90–94CrossRef

Moura L, Kitney R (1992) A direct method for least-squares circle fitting. Comput Phys Commun 64:57–63CrossRef

Mukherjee J, Sinha Mahapatra PR, Karmakar A, Das S (2013) Minimum-width rectangular annulus. Theor Comput Sci 508:74–80CrossRef

Narula SC, Wellington JF (1982) The minimum sum of absolute errors regression: a state of the art survey. Int Stat Rev 50:317–326CrossRef

Nickel S, Puerto J (2005) Location theory: a unified approach. Springer, Berlin/Heidelberg

Nievergelt Y (2002) A finite algorithm to fit geometrically all midrange lines, circles, planes, spheres, hyperplanes, and hyperspheres. Numer Math 91:257–303CrossRef

Nievergelt Y (2004) Perturbation analysis for circles, spheres, and generalized hyperspheres fitted to data by geometric total least-squares. Math Comput 73:169–180CrossRef

Nievergelt Y (2010) Median spheres: theory, algorithms, applications. Numer Math 114:573–606CrossRef

Overmars MH, van Leeuwen J (1981) Maintenance of configurations in the plane. J Comput Syst Sci 23:166–204CrossRef

Plastria F (1992) GBSSS: the generalized big square small square method for planar single-facility location. Eur J Oper Res 62:163–174CrossRef

Plastria F (2001) Continuous covering location problems. In: Drezner Z, Hamacher H (eds) Facility location - applications and theory. Springer, Berlin/Heidelberg, pp 1–36

Plastria F, Carrizosa E (2001) Gauge-distances and median hyperplanes. J Optim Theory Appl 110:173–182CrossRef

Plastria F, Carrizosa E (2012) Minmax-distance approximation and separation problems: geometrical properties. Math Program 132:153–177CrossRef

Rivlin T (1979) Approximation by circles. Computing 21:1–17CrossRef

Robert JM (1991) Linear approximation and line transversals. Ph.D. thesis, School of Computer Sciences, McGill University, Montreal

Robert JM, Toussaint G (1994) Linear approximation of simple objects. Comput Geom Theor Appl 4:27–52CrossRef

Robins G, Shute C (1987) The Rhind mathematical papyrus. An ancient Egyptian text. British Museum

Rockafellar R (1970) Convex analysis. Princeton Landmarks, Princeton

Rorres C, Romano D (1997) Finding the center of a circular starting line in an Ancient Greek stadium. SIAM Rev 39:745–754CrossRef

Sarkar A, Batta R, Nagi R (2007) Placing a finite size facility with a center objective on a rectangular plane with barriers. Eur J Oper Res 179:1160–1176CrossRef

Savas S, Batta R, Nagi R (2002) Finite-size facility placement in the presence of barriers to rectilinear travel. Oper Res 50:1018–1031CrossRef

Schieweck R (2013) Lower bounds for line location problems via demand regions. Technical report 28. Institut für Numerische und Angewandte Mathematik, Universität of Göttingen, Göttingen

Schieweck R, Schöbel A (2012) Properties and algorithms for line location with extensions. In: Proceedings of the 28th European workshop on computational geometry, Assisi, Italy, pp 185–188

Schöbel A (1996) Locating least-distant lines with block norms. Stud Locat Anal 10:139–150

Schöbel A (1997) Locating line segments with vertical distances. Stud Locat Anal 11:143–158

Schöbel A (1998) Locating least distant lines in the plane. Eur J Oper Res 106:152–159CrossRef

Schöbel A (1999a) Locating lines and hyperplanes—theory and algorithms. Applied optimization series, vol 25. Kluwer, Dordrecht

Schöbel A (1999b) Solving restricted line location problems via a dual interpretation. Discrete Appl Math 93:109–125CrossRef

Schöbel A (2003) Anchored hyperplane location problems. Discrete Comput Geom 29:229–238CrossRef

Schöbel A, Scholz D (2010) The Big Cube Small Cube solution method for multidimensional facility location problems. Comput Oper Res 37:115–122CrossRef

Schömer E, Sellen J, Teichmann M, Yap C (2000) Smallest enclosing cylinders. Algorithmica 27:170–186CrossRef

Späth H (1997) Least squares fitting of ellipses and hyperbolas. Comput Stat 12:329–341

Späth H (1998) Least-squares fitting with spheres. J Optim Theory Appl 96:191–199CrossRef

Sun T (2009) Applying particle swarm optimization algorithm to roundness measurement. Expert Syst Appl 36:3428–3438CrossRef

Suzuki T (2005) Optimal location of orbital routes in a circular city. Presented at ISOLDE X—10th international symposium on locational decisions, Sevilla and Islantilla, 2–8 June 20005

Swanson K, Lee DT, Wu V (1995) An optimal algorithm for roundness determination on convex polygons. Comput Geom Theor Appl 5:225–235CrossRef

Ventura J, Yeralan S (1989) The minmax center estimation problem. Eur J Oper Res 41:64–72CrossRef

Wang L, Gordon MD, Zhu J (2006) Regularized least absolute deviations regression and an efficient algorithm for parameter tuning. In: Proceedings of the 6th international conference on data mining. IEEE, New York, pp 690–700

Wesolowsky G (1972) Rectangular distance location under the minimax optimality criterion. Transp Sci 6:103–113CrossRef

Wesolowsky G (1975) Location of the median line for weighted points. Environ Plan A 7:163–170CrossRef

Yamamoto P, Kato K, Imai K, Imai H (1988) Algorithms for vertical and orthogonal L ₁ linear approximation of points. In: Proceedings of the 4th annual symposium on computational geometry, pp 352–361

Yeralan S, Ventura J (1988) Computerized roundness inspection. Int J Prod Res 26:1921–1935CrossRef

Zemel E (1984) An O(n) algorithm for the linear multiple choice knapsack problem and related problems. Inform Process Lett 18:123–128CrossRef

Titel: Location of Dimensional Facilities in a Continuous Space
verfasst von: Anita Schöbel
Verlag: Springer International Publishing
Buch: Location Science
Print ISBN: 978-3-319-13110-8

Electronic ISBN: 978-3-319-13111-5

Copyright-Jahr: 2015
DOI: https://doi.org/10.1007/978-3-319-13111-5_7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner