Locating Objects in the Plane Using Global Optimization Techniques

MATHEMATICS OF OPERATIONS RESEARCH Vol. 34, No. 4, November 2009, pp. 837–858 issn 0364-765Xeissn 1526-54710934040837 informs® doi 10.1287/moor.1090.0406 © 2009 INFORMS Locating Objects in the Plane Using Global Optimization Techniques Rafael Blanquero, Emilio Carrizosa Facultad de Matemáticas, Universidad de Sevilla, 41012 Sevilla, Spain {[email protected],[email protected]} Pierre Hansen GERAD and HEC Montréal, Montréal, Québec H3T 2A7, Canada, [email protected] We address the problem of locating objects in the plane such as segments, arcs of circumferences, arbitrary convex sets, their complements or their boundaries. Given a set of points, we seek the rotation and translation for such an object optimizing a very general performance measure, which includes as a particular case the classical objectives in semi-obnoxious facility location. In general, the above-mentioned model yields a global optimization problem, whose resolution is dealt with using difference of convex (DC) techniques such as outer approximation or branch and bound. Key words: global optimization; DC optimization; location of objects; computational metrology MSC2000 subject classification: Primary: 90B85; secondary: 90C26 OR/MS subject classification: Primary: facilities/equipment planning, location/continuous; secondary: programming, nonlinear History: Received April 4, 2008; revised November 2, 2008, and March 2, 2009. Published online in Articles in Advance October 7, 2009. 1. Introduction. Classical models considered in Location Theory deal with the problem of finding the optimal location, at some point or points of a given space and according to some effectiveness measure, for one or several point-wise facilities that provide service to a set of users located at given demand points. As a natural extension of these models, the problem of locating objects arises, where the facilities to be located are dimensional structures that cannot be modeled as isolated points (see Díaz-Báñez et al. [25] for a review on this topic). The location of dimensional structures has found applications in many areas (see Díaz-Báñez et al. [25], Le and Lee [51], Späth [75], Srinivasan [77], Ventura and Yeralan [82], Yeralan and Ventura [85], Zwick [86] and references therein for details). A nonexhaustive list of practical uses, collected from the literature, is the following: •Locational Analysis: location of pipelines, sewage systems or irrigation ditches, design of transportation networks, distribution routes, or obnoxious routes; •Computational Geometry: pattern recognition and computer vision, mechanical assembly, computer graphics, image processing, cartography, geographical information systems; •Computational metrology; •Industrial, military, and robotic task planning; •Neurosurgery; •Very Large Scale Integration (VLSI) chip design; •Reflectometry. Although in the last few years many papers on this topic have been written, the vast majority of them consider objects with very simple shapes, such as lines (Agarwal and Sharir [1], Edelsbrunner [29], Houle and Toussaint [43], Megiddo and Tamir [56,57], Morris and Norback [60,61], Robert and Toussaint [67], Schöbel [69,70,71,72], Wagner [83]), segments (Agarwal et al. [4], Efrat and Sharir [30], Imai et al. [46], McKinnon and Barber [55], Schöbel [71]), half-lines (Díaz-Báñez and Díaz [22], Lee and Wu [52], Morris and Norback [61]), hyperplanes (Brimberg et al. [11], Houle et al. [44], Korneenko and Martini [49], Martini and Schöbel [54], Nievergelt [63], Norback and Morris [64], Plastria and Carrizosa [65], Schöbel [71]), disks and other conic sections (de Berg et al. [21], Brimberg et al. [12,13,14], Dai et al. [20], Drezner et al. [28], Gander et al. [32], García-López et al. [33], Gass et al. [34], Laporte et al. [50], Le and Lee [51], Nievergelt [63], Rivlin [66], Späth [74,75,76], Ventura and Yeralan [82], Yeralan and Ventura [85]), or polygonal curves (Chan and Chin [17], Díaz-Báñez and Mesa [23,24], Drezner and Wesolowsky [27], Goodrich [35], Hakimi and Schmeichel [36], Imai and Iri [45], Melkman and O’Rourke [58]). Exact algorithms have been suggested in most cases. A review of the literature on this topic uncovers other important omissions in the existing models for locating dimensional structures. Indeed, all of them consider the location of a purely attractive facility (i.e., one that provides service without harmful effects on nearby population), whereas the case of an obnoxious facility or, with 837 Blanquero, Carrizosa, and Hansen: Locating Objects in the Plane 838 Mathematics of Operations Research 34(4), pp. 837–858, © 2009 INFORMS more generality, a semi-obnoxious facility (Carrizosa and Plastria [16]), seems to remain unexplored (the design of an obnoxious route, Drezner and Wesolowsky [27], Erkut and Verter [31], Karkazis and Boffey [47], Marianov et al. [53], is, perhaps, the only exception). The way in which the suitability of a given location is valued (i.e., the objective function, which depends—as a last resort—on the distance from every client to the new facility) shows limitations in those models, such as assuming that the interaction between every demand point and the new facility depends on the distance in a linear way; moreover, these interactions are combined in the objective function according to very simple schemes, namely, the addition of them, which gives rise to the so-called median or minisum problem, and the maximum of them, which gives rise to the center or minimax problem. More realistic approaches, such as assuming a nonlinear dependence on the distance (e.g., exponential) or combining the interactions following more sophisticated patterns, have not been considered in the literature. Although some of the models that can be found in the literature have a convex objective function, these problems are multimodal in general (especially when the shape of the object to be located becomes more complex). In spite of this fact, their exact resolution using global optimization techniques has not been explored so far (with the exception of Dai et al. [20] for a particular problem). As a paradigmatic case one can quote the problem of locating a circumference, a nonconvex optimization problem for which heuristic resolution techniques and local search algorithms have been suggested (Drezner et al. [28], Späth [74]). In this paper we address the problem of locating objects in the plane under a global optimization point of view, using difference of convex (DC) optimization techniques to obtain a globally optimal location. Properties of DC functions (functions which can be written as a difference of two convex functions) have been analyzed in the last 50 years; see, e.g., Hartman [38], Hiriart-Urruty [39], Horst and Thoai [41], Horst and Tuy [42], Tuy [78,80] and the references therein. This properties, briefly reviewed in §2, have been exploited in algorithmic tools such as Branch and Bound (e.g., Cambini and Sodini [15], Horst and Thoai [41]), Outer Approximation (e.g., Horst and Thoai [41], Tuy [79]), or Covering Methods (e.g., Blanquero and Carrizosa [7]), and have been successfully applied in different domains such as Machine Learning (e.g., Shen et al. [73]), Finance (e.g., Konno et al. [48]), Computational Chemistry (e.g., An and Tao [5]), or Logistics (Holmberg and Tuy [40]); see An and Tao [6] for further applications. Location Analysis has also been a fruitful field of application of DC methods; see, e.g., Blanquero and Carrizosa [9], Chen et al. [18,19], Drezner [26], Hansen et al. [37], Tuy et al. [81] and the references therein. The models addressed share the property that the objective function is written as a function (typically a weighted sum, or the pointwise maximum or minimum) of certain convex functions, namely, the distances (induced by norms) from a finite set of users to the facilities to be located. The feasible region is assumed to be rather simple (say, a finite union of polytopes in the plane), and the key issue is how to obtain a DC decomposition of the objective function. With such DC decomposition available, general-purpose techniques (e.g., Branch and Bound) are used to solve the problem. In Chen et al. [18], a semi-obnoxious location problem is considered: the weighted sum of distances to a set of individuals is to be minimized. Because the weights are unrestricted in sign, the objective function is written as the difference of two convex functions: the weighted sum of the distances with positive weights and the sum of distances with negative weights. This model is generalized in Tuy et al. [81]: A facility is to be located in the plane by minimizing a sum of convex decreasing or concave increasing functions of the distances from the facility to a set of users. Because the distance functions used are convex, the algebra for the composition of DC functions allows one to derive a DC decomposition for the objective. In Chen et al. [19], the problem of locating pfacilities in the plane minimizing the weighted sum of the distances from users to their closest facility is considered. The objective is a weighted sum of the minimum of convex functions (distances). Because both the sum and the minimum of DC functions is DC, a DC decomposition is available. The paper also analyzes some variants of this model, and the very same strategy is used. In Blanquero and Carrizosa [9], a biobjective problem is formulated for locating a semi-obnoxious facility; an approximation to the set of efficient solutions is obtained by solving a series of dimensional problems constrained to arcs in the plane. A convenient parameterization of the decision variables allows the authors to use the results in Blanquero and Carrizosa [8] to write such problems as one-dimensional optimization problems with DC objective and an interval as feasible set. In Drezner [26], a bounding procedure (to be imbedded in Branch-and-Bound methods) is suggested for problems in which the objective is DC and can be written as a sum of univariate convex (or concave) functions of the distances. A handful of models are shown in Drezner [26] to belong to this class. More recently, Blanquero and Carrizosa [10] have shown how a refinement of the bounds is possible if the objective is DC and can be written as a sum of univariate convex (or concave) monotonic functions of the distances. Blanquero, Carrizosa, and Hansen: Locating Objects in the Plane Mathematics of Operations Research 34(4), pp. 837–858, © 2009 INFORMS 839 The papers mentioned above consider the facility to be located to be a point in the plane. Here we propose a model that provides great flexibility both in the objective function and in the shape of the dimensional structure to be located. To do this, we show how to obtain DC decompositions for functions involving distances to sets. This and the algebra of DC functions will enable us to write the objective function as the difference of two convex functions, whose optimization is addressed via a general-purpose covering algorithm described in Blanquero and Carrizosa [7]. The paper is structured as follows. In §2we recall some key properties of DC functions, while §3is devoted to relating the distance to an arbitrary set Swith DC functions. In §4, a quite general location problem is introduced. How to obtain DC decompositions for particular shapes of Sis discussed in §5and, finally, some illustrative examples are provided in §6. 2. DC functions: basic properties. For completeness we start with a short review of the properties of DC functions that are used later. The reader is referred to Horst and Thoai [41], Horst and Tuy [42], Tuy [78,80] for further details. Given a convex set ⊂d, a function f −→ is DC on if it admits a DC decomposition, that is, if it can be written as fx=f1x −f2x where f1and f2are convex functions on . As an extension, a function h=h1h k  −→ kis said to be DC on if its components h1h kare DC on . Although most functions encountered in practice are DC (Tuy [80]), finding a DC decomposition for these functions (a prerequisite for applying most powerful DC optimization methods) is, in general, a far from trivial task and becomes a serious handicap in applying DC techniques. In spite of it, the class of DC functions has a nice property that mitigates this drawback, namely, it is closed under the usual operations that appear in optimization problems, such as linear combination, pointwise maximum and minimum, product, quotient, and composition. Hence, it usually suffices to know a DC decomposition of the operands involved to obtain a DC decomposition of the final result. For example, for scalars i,i=1r, and functions gi=pi−qi, i=1r, with piqiconvex on the convex set , the weighted sum r i=1igiis DC, and admits the following DC decomposition: r  i=1 igi= ii>0 ipi+ ii<0 −iqi− ii<0 −ipi+ ii>0 iqi(1) We also have that the pointwise maximum of DC functions gi=pi−qi,i=1r (with piqiconvex), is DC, and it admits the following decomposition: max i=1r gi=max i=1rpi+ j=i qj− r  i=1 qi(2) In particular, a DC decomposition for max0p−q, with pand qconvex, is given by max0p−q =maxp q −q(3) and, as a straightforward consequence, if g=p−qwith pand qconvex functions, one obtains the following DC representation for g=max0g+max0−g: g=2maxpq −p +q (4) The composition of DC functions requires a deeper analysis. Given two convex sets 1⊂nand 2⊂m,it is well known that, if f  1−→ 2and g 2−→ are DC, then gfis also a DC function; however, there is no general result providing a DC decomposition of gfexplicitly, and only in some particular cases can such a decomposition be obtained. For example, when m=1 and gis a convex or concave monotone function, a DC representation of gfcan easily be computed under mild conditions (see §3.3 in Tuy [80]), which has been successfully applied to the resolution of location problems (Tuy et al. [81]). In particular, Proposition 3.7 in Tuy [80] (reproduced below) will be used later in this paper (g −denotes the left derivative of the convex function g). Blanquero, Carrizosa, and Hansen: Locating Objects in the Plane 840 Mathematics of Operations Research 34(4), pp. 837–858, © 2009 INFORMS Proposition 2.1. Let fx=f+x −f−x where f+f−M−→ +are convex functions on a compact convex set M⊂nsuch that 0≤fx≤a∀x∈M.Ifg 0a−→ is a convex nondecreasing function such that g −a < +, then gfx is a DC function on Mwith DC decomposition gfx =ux −Ka +f−x −f+x where ux =gfx+Ka+f−x−f+x is a convex function and Kis any constant satisfying K≥g −a. Another interesting property is obtained when gisagauge, i.e., a real convex function defined as gx = inft > 0x∈tB where Bis a convex set, the interior of which contains the origin; see Michelot [59] and Rockafellar [68] (note that every norm is a gauge). In such a case, the following result lets us obtain a DC decomposition for gf(Blanquero and Carrizosa [8]). Proposition 2.2. Let ⊂nbe a convex set. Let g m→be a gauge in mwith unit ball B, let f=f1f m  →mbe a DC vector-valued function, with DC decomposition known: fi=f+ i−f− i, with f+ i,f− iconvex. For any i=1m, let Mi≥maxgei g−ei, where eiis the ith unit vector of m. Then, gf →is a DC function and a DC decomposition for it is given by gf=u−v (5) with u=gf+ m  i=1 Mif + i+f− iv= m  i=1 Mif + i+f− i This will be a key result in the methodology provided in this paper for locating objects. 3. Distance to a set. Given an arbitrary set S⊂d, we consider the function distance to Sunder the Euclidean norm, defined as dSx =inf s∈Sx−sx∈d When Sis a convex set, dSis convex (Webster [84]), so that local optimization algorithms can be applied to solve location problems where this function appears. However, when Sis an arbitrary set, the convexity of dS cannot be ensured anymore and the use of local search methods may not provide the global optimum. In that case, the problem should be tackled under a global optimization point of view. Since dSis Lipschitz-continuous, with Lipschitz constant 1 (see Webster [84, p. 45]), Lipschitz optimization can be applied. In the following sections we show that DC optimization (Horst and Tuy [42], Tuy [78,80]) can also be applied in this context, providing sharper results than the Lipschitz optimization approach. We first explore the DC character of the function dS. We begin this study stating a well-known property (Horst and Tuy [42], Tuy [80]). Proposition 3.1. Let S⊂dbe an arbitrary set. Then d2 Sis a DC function with DC decomposition d2 Sx =x2−x2−d2 Sx Using this result one can show that the function dSraised to the power p, with p≥2, is DC, and it is possible to obtain explicitly a DC decomposition for this function over a compact set: Corollary 3.1. Let S⊂dbe an arbitrary set. Then dp Sis a DC function for p≥2. Moreover, dp Sadmits the following DC decomposition over a compact set M⊂d: dp Sx =dp Sx +Ka −d2 Sx −Ka −d2 Sx x ∈M for any a≥maxx∈Mdp Sx and K≥p/2ap/2−1. Proof. Given a≥maxx∈Md2 Sx, the function dp Scan be written as dp Sx =qd2 Sx, where q 0a−→  is given by qt =tp/2. For all p≥2, the function qis a convex nondecreasing function such that q −a = p/2ap/2−1<+, so that using Proposition 2.1 the result follows.  The previous result not only shows the DC character of the function dp Sfor p≥2, but also provides a DC decomposition for it, the key factor in DC optimization. However, for 1 ≤p<2, the function dp Sis not DC in general. To show that, let us consider for p=1 the set S=xnn∈∪0, where xn=1/2n, and the points yn=1 2xn+xn+1,n∈. We will prove that the right-derivative of dSat 0, given by lim x↓0 dSx −dS0 x−0(6) Blanquero, Carrizosa, and Hansen: Locating Objects in the Plane Mathematics of Operations Research 34(4), pp. 837–858, © 2009 INFORMS 841 yn+1 yn xn dS(x) Figure 1. Graph of dSin counterexample. does not exist, so dscannot be written as the difference of two convex functions (in that case, dswould have side derivatives and these would be of bounded variation: Hartman [38]). Indeed, note that dSxn−dS0 xn−0=0∀nand dSyn−dS0 yn−0=1/3∀n from where we conclude that the limit (6) does not exist, and the proof is complete. To show that dp Sis not DC in general for 1 <p<2, let us consider the set S=ynn∈, where y1=1, yn+1=yn−2xn, and xn=1/pn1/p−1(the graph of dSin the interval yn+1ynis depicted in Figure 1). By construction, the derivative of dp Sx (denoted here by gpx) in the interval yn+1yn+1+xnis gpx =px −yn+1p−1=pdp−1 Sx Let us denote by Lthe length of the arc of gpon the interval yn+1yn+1+xnand by Lthe length of the straight segment with extreme points yn+10and yn+1+xnpxp−1 n. Then we have L≥L=x2 n+pxp−1 n2≥p2x2p−1 n=1 n Taking into account that n1/n =+, it follows that gpis not rectifiable; that is, it is not of bounded variation. Hence, dp Scannot be DC, because in that case its side derivatives would be of bounded variation, Rockafellar [68]. 4. The location model. The literature on continuous location is dominated by models where the facility to be located reduces to a point, an assumption that cannot be made in general (see Díaz-Báñez et al. [25] for motivating examples). However, following a more realistic and modern approach, in this paper we will assume that the facility Swhose location is sought, is an arbitrary subset of 2and also that Sis a semiobnoxious facility; that is, it provides service to a set A+=a1a2a nof demand points or users, but, together with this, it has some negative effect on the population or the environment, so we can distinguish a set A−=an+1an+2a n+mof points that are affected in a negative way. The new facility must be located as near to its potential clients as possible and, at the same time, it must be placed far from the negatively affected points; the model considered here will combine these opposed and irreconcilable aims. Let us denote by TSu+ the image of the server Safter a translation of vector u∈2and a counterclockwise rotation of angle +∈02, with center at the origin, applied in this order. Then, the aim of the decision maker is to find uand +optimizing an effectiveness measure depending on the distance to the points aifrom TSu+; this yields the optimal location for the object Sregarding the attraction and repulsion points, under the selected criterion. Such a location can be obtained as the solution of the following optimization problem: min u∈U +∈02, h+dp TSu+a1d p TSu+an (7) −h−dp TSu+an+1d p TSu+an+m (8) where •h+n−→ and h−m−→ are gauges, that is, h+x =inft > 0x∈tB+x∈n h−y =inft > 0y∈tB−y∈m where B+⊂nand B−⊂mare convex sets, the interior of which contain the origins of nand m, respectively. Blanquero, Carrizosa, and Hansen: Locating Objects in the Plane 842 Mathematics of Operations Research 34(4), pp. 837–858, © 2009 INFORMS •U⊂2is the set of allowed translation vectors. We assume this set is compact, which is not a strong hypothesis, because in real applications the set of feasible locations for the object Susually has this property. In the following, we will assume that the distance to the facility, dSx, can be computed for every point x∈ 2. This computation can be made by using closed expressions if Shas specific geometric forms (circumference, disk, polyhedral set,), or by solving a convex problem when Sis convex. In more complex cases, it suffices to solve a univariate DC optimization problem, assuming that a DC decomposition for a parametric representation of the boundary of Sis known. As mentioned above, our aim is to find the translation and the rotation that provide, coming from the initial position of the facility S, an optimal location for it. These movements enjoy the following basic property when they are used under the Euclidean distance. Proposition 4.1. Translations and rotations are isometric under the Euclidean distance. Thus, the distance from any point to the image of Safter a given movement of this kind (translation plus rotation), fits in the distance to the set Sfrom the image of the point after applying the inverse movement; that is, dTSu+x =dST −1 xu + (9) This property allows us to state the following equivalent formulation for the location model (8): min t∈.Ft=h+dp Sf1td p Sfnt −h−dp Sfn+1td p Sfn+mt (10) where .=U×02, ⊂3and fi.−→ 2is defined as fit =T−1 aiu+, for t=u+ ∈.and i= 1n+m. Note that the function Fin the objective of (10) gives us great flexibility because, with a suitable choice of the gauges h+and h−, one obtains as particular cases a broad variety of models and criteria of common use in Location Theory. For example: •Location of attractive facilities: h−=0. •Location of obnoxious facilities: h+=0. •Location of semi-obnoxious facilities: h+≥0 and h−≥0. •Minisum and Maxisum criteria: h±=1(weighted). •Minimax criterion: h+=. •Cent-dian criterion: h+=1−01+0. Finding the optimal location for the object Sby using the model proposed here involves the resolution of the nonlinear optimization problem (10), which may have several local optima, as shown in the next example. Example 4.1. Given the points 24and 612and the nonconvex polygon Swith vertices −40,05, 40, and 02, consider the problem of finding the translation and the rotation of Sminimizing the maximum of the distances from the points to the image of Sunder these transformations. Figure 2depicts the objective function of this problem when the second component of the translation vector u2has been set equal to 0, showing its multimodal character. The location problem was solved 10,000 times using a local optimization algorithm (the so-called simplex method of Nelder and Mead [62]), starting each execution with a translation vector and an angle randomly generated in −2020×−2020×02,. In 54.5 per cent of the runs, the local search method failed to find the global optimal solution, being trapped in a local minimum. The previous example shows that, if just local-search procedures are used, the algorithm may be trapped in a local optimum. Even if the probability of obtaining a bad local optimum were low, we would not be sure of having obtained the global optimum, which may be a must for location problems when the facilities to be located involve high risk or investment. Hence, global optimization techniques, such as DC optimization, seem to be the most convenient approach for solving the location problem (10). The serious drawback of the DC optimization methods proposed is that a DC decomposition for Fis needed. With this purpose in mind, the use of Proposition 2.2 allows us to obtain such a DC representation, under some conditions over the functions dp S. For the sake of completeness, we rewrite next that result, adapted to the context of this paper. Proposition 4.2. Assume that 1it =dp Sfit is a DC function with known DC decomposition, 1it = 1+ it −1− it, for all i=1n+m. Then Ftis DC with DC decomposition Ft=F+t −F−t Blanquero, Carrizosa, and Hansen: Locating Objects in the Plane Mathematics of Operations Research 34(4), pp. 837–858, © 2009 INFORMS 843 01234567 –20 –10 0 10 20 6 8 10 12 14 16 18 20 22 24 26 α u1 Figure 2. Objective function in Example 4.1 with u2=0. with F+t =h+11t1 nt + n  i=1 Mi1+ it +1− it + n+m  i=n+1 Ni1+ it +1− it F−t =h−11t1 nt + n  i=1 Mi1+ it +1− it + n+m  i=n+1 Ni1+ it +1− it where Mi≥maxh+ ieih+ i−ei,Ni≥maxh− i˜ei−nh− i−˜ei−n, and ejand ˜ejare the jth unit vectors of n and m, respectively. As a particular case, if the gauge h+is an Lq-norm, one can take Mi=1 for all i=1n. Analogously, the constants Ni,i=n+1n+m, can also be taken equal to 1 if the function h−is also a norm of this kind. Remark 4.1. The application of Proposition 4.2 for obtaining a DC decomposition of the objective Fin (10) is based on the fact that h+and h−are gauges. Nevertheless, this requirement on h+and h−can be softened, provided that the functions involved ensure the DC character of Fand allows us to obtain a DC representation for it. As an example, one can choose h+=max−x1−xnand h−=0, yielding the maximin criterion (obviously h+is not a gauge); if every function 1iis DC with known DC decomposition, getting a DC representation for Fis an easy task using the algebra of DC functions (see §2). As a consequence of Proposition 4.2, the main difficulty found to solve Problem (10) by using DC optimization techniques reduces to getting a DC decomposition for every function 1i=dp Sfit,i=1n+m. When p≥1, such a decomposition can be obtained from a DC representation of the functions dSfit by using Proposition 2.1, which is stated next for this particular context. Proposition 4.3. Assume that dSf t is DC with DC decomposition dSf t =3+t −3−t. Then dp Sf t is DC for p≥1and a DC decomposition is given by dp Sf t =dp Sf t +Ka +3−t −3+t −Ka +3−t −3+t for any K≥pap−1and a≥maxt∈.dSf t. Blanquero, Carrizosa, and Hansen: Locating Objects in the Plane 844 Mathematics of Operations Research 34(4), pp. 837–858, © 2009 INFORMS From the previous reasoning, it is clear that the problem reduces to getting a DC decomposition for dSfi. In what follows, the variable trepresents the pair u+, where uis the translation vector and +gives the rotation angle. Note that the functions fit =T−1 aiu+ are DC, because they can be written as fit =f1it f2it =−u1+xicos+ +yisin+ −u2−xisin+ +yicos+ where ai=xiyiand u=u1u2. Moreover, it is a trivial task to compute a DC decomposition for f1iand f2i, so that our final aim is to obtain a DC decomposition for dSf t, assuming that a DC representation of ft is known. In the following section we show some particular cases with practical interest in which a DC decomposition for dSf t—and thus for the objective of (10)—can be explicitly obtained. 5. Obtaining a DC decomposition for dS.As has been made clear in the previous section, getting a global optimal solution for the location model (10) by using DC optimization methods calls for having DC decompositions for the functions dSfit which can be obtained from DC decompositions for fit,i= 1n+m. Although it will not be possible, in general, to obtain such a decomposition for an arbitrary object S, we will next show that this task is feasible in most cases of interest from the viewpoint of practical applications. 5.1. Convex set. Proposition 5.1. Let S⊂dbe convex and let f k−→ dbe a DC function with known DC decomposition fj=f+ j−f− jj=1d Then a DC decomposition for dSf t is given by dSf t =3+t −3−t where 3+t =dSf t + d  j=1 f + jt +f− jt 3−t = d  j=1 f + jt +f− jt Proof. Let us denote by B1the unit ball in dfor the Euclidean distance; i.e., B1=u ∈du≤1. Then, given s∈S,wehave ft−s=max u∈B1 uf t −s =max u∈B1 d  j=1 ujfjt −sj =max u∈B1 d  j=1 ujf + jt −f − jt +sj =max u∈B1 d  j=1 1+ujf + jt +1−ujf − jt +sj−sj− d  j=1 f + jt +f− jt from which we obtain dSf t =inf s∈Sft−s =inf s∈Smax u∈B1 d  j=1 1+ujf + jt +1−ujf − jt +sj−sj− d  j=1 f + jt +f− jt (11) Blanquero, Carrizosa, and Hansen: Locating Objects in the Plane Mathematics of Operations Research 34(4), pp. 837–858, © 2009 INFORMS 845 The function 3−t =d j=1f + jt+f− jt is convex because it is the sum of convex functions. To show that the remaining term in (11) is also convex (and, as a consequence, that dSf t is DC), note that we can interchange the maximum and the infimum since Sis convex and B1is convex and compact. This yields max u∈B1 inf s∈Sd  j=1 1+ujf + jt +1−ujf − jt +sj−sj =max u∈B1 inf s∈Sd  j=1 1+ujf + jt +1−ujf − jt − d  j=1 ujsj =max u∈B1d  j=1 1+ujf + jt +1−ujf − jt−sup s∈S us The first part of the last expression is a convex function, because it is the pointwise maximum of convex functions (note that 1 +ujand 1 −ujare nonnegative because u∈B1) and the second one does not depend on t, so it is a constant. Therefore, (11) provides a DC decomposition for dSf t, showing the result.  Next we analyze some particular cases of interest for location in the plane, for which alternative DC decompositions to those provided by the previous result can be obtained. For the sake of simplicity, we only consider the planar case (d=2), though the results extend to arbitrary dimensions. Proposition 5.2 (Disk). Given C∈2and R∈, let S=x ∈2x−C≤R and let f k−→ 2be a DC function with known DC decomposition, fj=f+ j−f− jj=12 Then a DC decomposition for dSf t is given by dSf t =maxg−t g+t −g−t where g+t =ft−C+ 2  j=1 f + jt +f− jt −Cj−R g−t = 2  j=1 f + jt +f− jt −Cj Proof. The distance from ft to a disk of center Cand radius Radmits the following expression: dSf t =max0ft−C−R The function ft−C−Ris DC, because it is the composition of a norm with a DC function and, using Proposition 4.2, a DC decomposition for it is given by g+−g−. Finally, using (3), the result follows.  Proposition 5.3 (Line). Given a∈2,a= 0, and b∈, let S=x ∈2ax=b and let f k−→ 2 be a DC function with known DC decomposition, fj=f+ j−f− j,j=12. Then a DC decomposition for dSf t is given by dSf t =2 amaxg+t g−t −1 ag+t +g−t where g+t = 2  j=1 aj+ajf + jt +aj−ajf − jt g−t = 2  j=1 ajf + jt +f− jt +b Blanquero, Carrizosa, and Hansen: Locating Objects in the Plane 852 Mathematics of Operations Research 34(4), pp. 837–858, © 2009 INFORMS –5 0 5 10 15 –5 0 5 10 15 –5 0 5 10 15 –5 0 5 10 15 Figure 3. Points and optimal circumference in Example 6.1. 6. Numerical examples. The location problem (10) has been written as a DC optimization problem over a polytope, and a DC decomposition for its objective has been obtained in a wide variety of cases. The optimal solution of this optimization problem can be computed using standard DC optimization techniques, such as branch-and-bound or outer approximation methods. To show the viability of the suggested methodology from a computational point of view, we have considered a set of examples with different levels of difficulty. All of them have been solved using the covering method proposed in Blanquero and Carrizosa [7]. Example 6.1. In Späth [74], the author considers the following problem: given a set of eight points ai8 i=1, find the circumference Sthat minimizes the sum of squared distances from the points to S. One has to find the center Cand the radius Rof the circumference solving the following optimization problem: min CR 8  i=1 ai−C−R2(20) In Späth [74], (20) is solved using local search techniques, ignoring the multimodality character that the problem could have because of the nonconvexity of its objective. To obtain the global optimum, it is clear that the objective function is DC, and a DC decomposition for it can easily be constructed. Using the above-mentioned DC optimization method, we have checked that the local optimal solution provided in that paper is also the global optimal solution. Figure 3shows the position of the points aias well as the optimal circumference. Example 6.2. Given the set of 30 points in Table 1,ai30 i=1, we consider the problem of finding the circumference Sthat minimizes the sum of the distances from the points to S. As in the previous example, our aim is to find the center Cand the radius Rof a circumference solving the following optimization problem: min CR 30  i=1 ai−C−R(21) Problem (21) can be solved with the global optimization approach proposed in this paper, because a DC decomposition for its objective can be easily computed using (4). After 51 iterations of the covering algorithm, Table 1. Points used in Examples 6.2,6.3,6.4, and 6.5. Point Coordinates Point Coordinates Point Coordinates 101211 9621 187 202212 91522 1811 311013 10223 1813 42114 121424 1825 52315 141025 195 622516 15326 2016 74417 151627 2019 841518 152528 2119 941819 161129 2421 10 6220 17330 259 Blanquero, Carrizosa, and Hansen: Locating Objects in the Plane Mathematics of Operations Research 34(4), pp. 837–858, © 2009 INFORMS 853 0 10 20 30 –5 0 5 10 15 20 25 30 0 10 20 30 –5 0 5 10 15 20 25 30 Figure 4. Points and optimal circumference in Example 6.2. we obtained as the optimal solution the circumference with center 10351225and radius 1035302, with a tolerance of 10−5. The position of the points ai, as well as the optimal location of the circumference, are depicted in Figure 4. Example 6.3. As an extension of Example 6.2, we consider the following semi-obnoxious facility location problem of locating a circumference close to some points but far from other points: min CR  i∈I+ ai−C−R− i∈I− ai−C−R(22) where I+=3k10 k=1,I−=130\I+, and the points ai30 i=1are given in Table 1. As in the previous example, a DC decomposition for the objective of Problem (22) can be easily obtained. The optimal solution is the circumference with center 1802703and radius 947, obtained by using the covering algorithm after 74 iterations, with a tolerance of 10−5. The position of the points ai, as well as the optimal location of the circumference are depicted in Figure 5(attractive points as squares and repulsive points as circles). Example 6.4. Consider the set of 30 points in Table 1,ai30 i=1, and let Sbe the nonconvex polygon with vertices 00,105,510,1015, and 015. We seek the translation and the rotation of Sminimizing the sum of the distances from the points to the image of Sunder these transformations. Since Sis the union of five segments, one can tackle this problem by using Propositions 5.10 and 5.5 to obtain a DC decompostion for its objective. The application of the covering algorithm (with a tolerance >=10−5) provided as the optimal solution, after 806 iterations, the polygon with vertices 2901497,813509, 13021021,1813533, and 17901532. The initial and the final (optimal) position of the polygon, together with the points aiare depicted in Figure 6. 0 10 20 30 –5 0 5 10 15 20 25 30 0 10 20 30 –5 0 5 10 15 20 25 30 Figure 5. Points and optimal circumference in Example 6.3. Blanquero, Carrizosa, and Hansen: Locating Objects in the Plane 854 Mathematics of Operations Research 34(4), pp. 837–858, © 2009 INFORMS 0 10 20 30 –5 0 5 10 15 20 25 30 0 10 20 30 –5 0 5 10 15 20 25 30 Figure 6. Initial and optimal position for the polygon in Example 6.4. Example 6.5. Consider the set of 30 points in the plane given in Table 1and the object Scomposed by the following figures: •The circumference with center 00and radius 4. •The boundary of the rectangle with vertices 55,520,1520, and 155. One aim is to obtain the translation and the rotation of Sminimizing the sum of the distances from the points to the image of Sunder these transformations. Taking into account that Sis a finite collection of objects (a circumference plus four segments), one can use Proposition 5.10 to obtain a DC decomposition for dS, after applying Propositions 5.8 and 5.5 to obtain individual DC decompositions for the components. After 59 iterations of the covering algorithm, we obtained as the optimal solution the circumference with center 19872154and radius 4, and the rectangle with vertices 14641679,1390180,391229, and 4641729; the tolerance used was 10−5. The initial and the final position of the object after applying the optimization method, as well as the points ai, are shown in Figure 7. To complete the previous computational experience, we have solved every problem described in Examples 6.1 to 6.5 with a variable number of demand points nfrom 10 to 10,000, randomly generated in the square 025× 025. For the problem in Example 6.3, points with an index multiple of three were considered to have a repulsive character. The covering algorithm in Blanquero and Carrizosa [7], used to solve all the problems was implemented in a Fortran program compiled by Intel Fortran 10.1 and ran on a 2.4 GHz computer under Windows XP. The solutions were found to a relative accuracy of 10−5. The computational results obtained for these problems are shown in Tables 2–6. Each table shows some statistics results (minimum, maximum, and average) for three indicators of the algorithm performance: number of iterations, number of vertices in the final polytope (recall that the covering algorithm involves a polytope at every iteration, which is obtained from the previous one by adding a linear restriction), and run time. Ten runs for each problem and value of nwere performed to obtain the above-mentioned measurements. 0 10 20 30 –5 0 5 10 15 20 25 30 0 10 20 30 –5 0 5 10 15 20 25 30 Figure 7. Initial and optimal position for the object in Example 6.5. Blanquero, Carrizosa, and Hansen: Locating Objects in the Plane Mathematics of Operations Research 34(4), pp. 837–858, © 2009 INFORMS 855 Table 2. Computational results for the object considered in Example 6.1. Iterations Vertices Time (seconds) nMin Max Ave Min Max Ave Min Max Ave 10 558 987 68990 3295 5921 411770 002 002 002 20 520 1043 69140 3108 6264 415110 002 003 003 50 583 809 68170 3479 4889 409440 003 006 004 100 640 1048 75600 3840 6394 455000 008 013 009 200 669 785 72830 4045 4737 438060 016 017 017 500 722 903 79720 4351 5467 481100 041 052 045 1,000 786 927 85090 4726 5611 514160 088 106 096 2,000 793 929 86290 4780 5628 521080 178 208 193 5,000 840 913 88260 5079 5561 533620 467 516 494 10,000 876 949 91580 5239 5734 553160 972 1067 1021 Table 3. Computational results for the object considered in Example 6.2. Iterations Vertices Time (seconds) nMin Max Ave Min Max Ave Min Max Ave 10 33 46 3750 174 257 20450 000 000 000 20 38 62 4790 199 346 26190 000 000 000 50 47 75 5700 243 416 31130 000 002 000 100 53 94 7150 277 545 39390 000 002 000 200 69 84 7730 383 471 42610 000 002 001 500 74 97 8560 399 541 47410 003 005 004 1,000 81 114 9650 443 629 53400 006 011 008 2,000 83 132 11020 443 745 61600 014 023 019 5,000 106 142 11720 575 794 64880 044 066 050 10,000 111 146 12370 599 826 68820 089 133 106 Table 4. Computational results for the object considered in Example 6.3. Iterations Vertices Time (seconds) nMin Max Ave Min Max Ave Min Max Ave 10 31 91 5530 155 545 30870 000 000 000 20 38 86 6410 204 483 35800 000 002 000 50 47 218 10660 238 1249 60450 000 002 001 100 113 193 13510 640 1107 77490 002 002 002 200 114 237 15680 651 1397 90850 002 006 004 500 165 257 21530 948 1508 126050 011 016 013 1,000 190 335 24070 1100 1989 141380 022 041 028 2,000 226 358 27880 1293 2140 164150 052 091 068 5,000 272 400 32660 1607 2371 193800 161 247 199 10,000 287 442 35760 1694 2654 212450 345 559 442 Table 5. Computational results for the object considered in Example 6.4. Iterations Vertices Time (seconds) nMin Max Ave Min Max Ave Min Max Ave 10 426 1237 77490 2334 7060 449240 006 017 012 20 744 2188 121690 4294 13420 718030 020 069 036 50 903 2264 154770 5134 13634 922750 063 170 115 100 1426 3843 213240 8557 23635 1285050 217 609 325 200 1476 3273 235950 8790 20048 1433280 442 1025 728 500 2205 5759 350460 13346 35936 2150510 1692 4695 2767 1,000 2754 4464 361950 16696 27623 2224260 4266 7161 5726 2,000 2865 4758 383260 17472 29357 2357090 8981 15158 12175 5,000 3654 6815 491910 22416 42478 3045150 28992 55766 39574 10,000 3831 6163 472100 23546 38417 2917740 60400 100136 75444 Blanquero, Carrizosa, and Hansen: Locating Objects in the Plane 856 Mathematics of Operations Research 34(4), pp. 837–858, © 2009 INFORMS Table 6. Computational results for the object considered in Example 6.5. Iterations Vertices Time (seconds) nMin Max Ave Min Max Ave Min Max Ave 10 348 727 48000 1882 4170 267440 005 011 006 20 503 881 65640 2830 5049 371270 013 025 017 50 661 1468 102800 3790 8508 594590 042 102 070 100 818 1589 119780 4573 9485 696490 106 233 165 200 970 2297 163580 5674 13765 968870 270 673 467 500 1635 3233 236200 9485 19632 1415170 1141 2439 1741 1,000 1632 3371 271200 9406 20294 1627940 2277 5028 4025 2,000 3013 4084 349810 18305 25070 2131000 9127 12578 10695 5,000 3060 5154 407380 18534 31714 2485620 23186 40416 31326 10,000 3495 7177 466040 21258 44383 2856830 53205 113284 72344 The problem of locating a circumference with variable radius (Table 3) shows the best performance, with an average CPU time of 1.06 seconds for 10,000 demand points. On the other hand, the worst results are given by the problem of locating the pentagon considered in Example 6.4, with 754.44 seconds of average CPU time for the same number of points, which can be considered a good result taking into account the size of the problem and its level of difficulty. In summary, the proposed methodology lets us efficiently obtain the optimal location with respect to a set of points for a great variety of objects. Acknowledgments. The research of the first two authors was supported by Grants MTM2008-3032 of Ministerio de Ciencia e Innovación, Spain, and FQM-329 of PAIDI, Spain. The authors thank I. Bomze for his helpful remarks. References [1] Agarwal, P. K., M. Sharir. 1994. Planar geometric location problems. Algorithmica 11 185–195. [2] Agarwal, P. K., C. M. Procopiuc, K. R. Varadarajan. 2003. A (1+>)-approximation algorithm for 2-line center. Comput. Geometry 26 119–128. [3] Agarwal, P. K., C. M. Procopiuc, K. R. Varadarajan. 2005. Approximation algorithms for a k-line center. Algorithmica 42 221–230. [4] Agarwal, P. K., A. Efrat, M. Sharir, S. Toledo. 1993. Computing a segment center for a planar point set. J. Algorithms 15 314–323. [5] An, L. T. H., P. D. Tao. 2003. Large-scale molecular optimization from distance matrices by a D.C. optimization approach. SIAM J. Optim. 14 77–114. [6] An, L. T. H., P. D. Tao. 2005. The DC (difference of convex functions) programming and DCA revisited with DC models of real-world nonconvex optimization problems. Ann. Oper. Res. 133 23–46. [7] Blanquero, R., E. Carrizosa. 2000. On covering methods for DC optimization. J. Global Optim. 18 265–274. [8] Blanquero, R., E. Carrizosa. 2000. Optimization of the norm of a vector-valued DC function and applications. J. Optim. Theory Appl. 107 245–260. [9] Blanquero, R., E. Carrizosa. 2002. A D.C. biobjective location model. J. Global Optim. 23 139–154. [10] Blanquero, R., E. Carrizosa. 2008. Continuous location problems and big triangle small triangle: Constructing better bounds. J. Global Optim. http://www.springerlink.com/content/t8322883354940ur/, DOI 10.1007/s10898-008-9381-z. [11] Brimberg, J., H. Juel, A. Schöbel. 2002. Linear facility location in three dimensions—Models and solution methods. Oper. Res. 50 1050–1057. [12] Brimberg, J., H. Juel, A. Schöbel. 2009. Locating a circle on the plane using the minimax criterion. Stud. Locational Anal., Issue 17(September). [13] Brimberg, J., H. Juel, A. Schöbel. 2007. Locating a circle on a sphere. Oper. Res. 55 782–791. [14] Brimberg, J., H. Juel, A. Schöbel. 2009. Locating a minisum circle on the plane. Discrete Appl. Math. 157 901–912. [15] Cambini, R., C. Sodini. 2005. Decomposition methods for solving nonconvex quadratic programs via branch and bound. J. Global Optim. 33 313–336. [16] Carrizosa, E., F. Plastria. 1999. Location of semi-obnoxious facilities. Stud. Locat. Anal. 12 1–27. [17] Chan, W. S., F. Chin. 1996. Approximation of polygonal curves with minimum number of line segments or minimun error. Internat. J. Comput. Geom. Appl. 659–77. [18] Chen, P. C., P. Hansen, B. Jaumard, H. Tuy. 1992. Weber’s problem with attraction and repulsion. J. Regional Sci. 32 467–486. [19] Chen, P. C., P. Hansen, B. Jaumard, H. Tuy. 1998. Solution of the multisource Weber and conditional Weber problems by D.-C. programming. Oper. Res. 46 548–562. [20] Dai, Y., J. Shi, Y. Yamamoto. 1996. Global optimization problem with multiple reverse convex constraints and its application to out-of-roundness problem. J. Oper. Res. Soc. Japan 39 356–371. [21] de Berg, M., J. Bose, D. Bremmer, S. Ramaswami, G. Wilfong. 1997. Computing constrained minimum-width annuli of point sets. Lecture Notes in Computer Science, Vol. 1272. Springer, New York, 392–401. [22] Díaz-Báñez, J. M., P. Díaz. 2000. The half-line center problem with ll1metrics. Stud. Locational Anal. 15 83–97. [23] Díaz-Báñez, J. M., J. A. Mesa. 1998. Location of rectilinear center trajectories. Top 6159–177. Blanquero, Carrizosa, and Hansen: Locating Objects in the Plane Mathematics of Operations Research 34(4), pp. 837–858, © 2009 INFORMS 857 [24] Díaz-Báñez, J. M., J. A. Mesa. 2001. Fitting rectilinear paths to a set of points in the plane. Eur. J. Oper. Res. 130 214–222. [25] Díaz-Báñez, J. M., J. A. Mesa, A. Schöbel. 2004. Continuous location of dimensional structures. Eur. J. Oper. Res. 152 22–44. [26] Drezner, Z. 2007. A general global optimization approach for solving location problems in the plane. J. Global Optim. 37 305–319. [27] Drezner, Z., G. O. Wesolowsky. 1989. Location of an obnoxious route. J. Oper. Res. Soc. 40 1011–1018. [28] Drezner, Z., S. Steiner, G. O. Wesolowsky. 2002. On the circle closest to a set of points. Comput. Oper. Res. 29 637–650. [29] Edelsbrunner, H. 1985. Finding transversals for sets of simple geometric figures. Theoret. Comput. Sci. 35 55–69. [30] Efrat, A., M. Sharir. 1996. A near-linear algorithm for the planar segment-center problem. Discrete Comput. Geom. 16 239–257. [31] Erkut, E., V. Verter. 1995. Hazardous materials logistics. Z. Drezner, ed. Facility Location: A Survey of Applications and Methods. Springer-Verlag, New York, 467–506. [32] Gander, W., G. H. Golub, R. Strebel. 1994. Least squares fitting of circles and ellipses. BIT 34 558–578. [33] García-López, J., P. Ramos, J. Snoeyink. 1998. Fitting a set of points by a circle. Discrete Comput. Geom. 20 389–402. [34] Gass, S. I., C. Witzgall, H. H. Harary. 1998. Fitting circles and spheres to coordinate measuring machine data. F. Giannessi, T. Rapcsák, S. Komlósic, eds. New Trends in Math. Program. Kluwer Academic Publishers, Dordrecht, The Netherlands, 65–92. [35] Goodrich, M. T. 1995. Efficient piecewise-linear function approximation using the uniform metric. Discrete Comput. Geometry 14 445–462. [36] Hakimi, S. L., E. F. Schmeichel. 1991. Fitting polygonal functions to a set of points in the plane. CVGIP: Graphical Models Image Process 53 132–136. [37] Hansen, P., B. Jaumard, H. Tuy. 1995. Global optimization in location. Z. Drezner, ed. Facility Location: A Survey of Applications and Methods. Springer-Verlag, New York, 43–68. [38] Hartman, P., 1959. On functions representable as a difference of convex functions. Pacific J. Math. 9707–713. [39] Hiriart-Urruty, J. B. 1986. Generalized differentiability, duality, and optimization for problems dealing with differences of convex functions. J. Ponstein, ed. Lecture Notes in Economics and Mathematical Systems, Vol. 256. Springer-Verlag, Berlin, 37–69. [40] Holmberg, K., H. Tuy. 1999. A production-transportation problem with stochastic demand and concave production costs. Math. Programming 85 157–179. [41] Horst, R., N. V. Thoai. 1999. DC programming: Overview. J. Optim. Theory Appl. 103 1–43. [42] Horst, R., H. Tuy. 1996. Global Optimization. Deterministic Approaches. Springer-Verlag, Berlin. [43] Houle, M. E., G. T. Toussaint. 1988. Computing the width of a set. IEEE Trans. Pattern Anal. 10 760–765. [44] Houle, M. E., H. Imai, K. Imai, J. M. Robert, P. Yamamoto. 1993. Orthogonal weighted linear L1and Lapproximation and applications. Discrete Appl. Math. 43 217–232. [45] Imai, H., M. Iri. 1988. Polygonal approximations of a curve-formulation and algorithms. G. T. Toussaint, ed. Computational Morphology. North-Holland, Amsterdam, 71–86. [46] Imai, H., D. T. Lee, C. Yang. 1992. 1-segment center problem. ORSA J. Comput. 4426–434. [47] Karkazis, J., T. B. Boffey. 1995. Optimal location of routes for vehicles transporting hazardous materials. Eur. J. Oper. Res. 86 201–215. [48] Konno, H., K. Akishino, R. Yamamoto. 2005. Optimization of a long-short portfolio under nonconvex transaction cost. Comput. Optim. Appl. 32 115–132. [49] Korneenko, N. M., H. Martini. 1993. Hyperplane approximation and related topics. J. Pach, ed. New Trends in Discrete and Computational Geometry. Springer-Verlag, New York, 135–162. [50] Laporte, G., J. A. Mesa, F. Ortega. 1994. Assessing topological configuration for rapid transit networks. Stud. Locational Anal. 7 105–121. [51] Le, V. B., D. T. Lee. 1991. Out-of-roundness problem revisited. IEEE Trans. Pattern Anal. 13 217–223. [52] Lee, D. T., Y. F. Wu. 1986. Geometric complexity of some location problems. Algorithmica 1193–211. [53] Marianov, V., C. ReVelle, S. Shih. 2002. Anticoverage models for obnoxious material transportation. Environ. Planning B: Planning Design 29 141–150. [54] Martini, H., A. Schöbel. 2001. Median and center hyperplanes in Minkowski spaces-–A unifying approach. Discrete Math. 241 407–426. [55] McKinnon, R. D., G. M. Barber. 1972. A new approach to network generation and map representation: The linear case of the location-allocation problem. Geographical Anal. 4156–168. [56] Megiddo, N., A. Tamir. 1982. On the complexity of locating linear facilities in the plane. Oper. Res. Lett. 1194–197. [57] Megiddo, N., A. Tamir. 1983. Finding least-distance lines. SIAM. J. Algebraic Discrete Methods 4207–211. [58] Melkman, A., J. O’Rourke. 1988. On polygonal chain approximation. G. T. Toussaint, ed. Computational Morphology. North-Holland, Amsterdam, 87–95. [59] Michelot. C. 1993. The mathematics of the continuous location. Stud. Locational Anal. 559–83. [60] Morris, J. G., J. P. Norback. 1983. A simple approach to linear facility location. Transportation Sci. 14 1–8. [61] Morris, J. G., J. P. Norback. 1983. Linear facility location-solving extensions on the basic problems. Eur. J. Oper. Res. 12 90–94. [62] Nelder, J. A., R. Mead. 1964. A simplex method for function minimization. Comput. J. 7308–313. [63] Nievergelt, Y. 2002. A finite algorithm to fit geometrically all midrange lines, circles, planes, spheres, hyperplanes, and hyperspheres. Numer. Math. 91 257–303. [64] Norback, J. P., J. G. Morris. 1980. Fitting hyperplanes by minimizing orthogonal deviations. Math. Programming 19 102–105. [65] Plastria, F., E. Carrizosa. 2001. Gauge-distances and median hyperplanes. J. Optim. Theory Appl. 110 173–182. [66] Rivlin, T. J. 1972. Approximation by circles. Computing 193–104. [67] Robert, J. M., G. T. Toussaint. 1994. Linear approximation of simple objects. Comput. Geometry 427–52. [68] Rockafellar, R. T. 1970. Convex Analysis. Princeton University Press, Princeton, NJ. [69] Schöbel, A. 1996. Locating least-distant lines with block norms. Stud. Locational Anal. 10 139–150. [70] Schöbel, A. 1998. Locating least distant lines in the plane. Eur. J. Oper. Res. 106 152–159. [71] Schöbel, A. 1999. Locating Lines and Hyperplanes: Theory and Algorithms. Kluwer Academic Publishers, Dordrecht, The Netherlands. [72] Schöbel, A. 1999. Solving restricted line location problems via a dual interpretation. Discrete Appl. Math. 93 109–125. [73] Shen, X., G. C. Tseng, X. Zhang, W. H. Wong. 2003. On 1-learning. J. Amer. Statist. Assoc. 98 724–734. Blanquero, Carrizosa, and Hansen: Locating Objects in the Plane 858 Mathematics of Operations Research 34(4), pp. 837–858, © 2009 INFORMS [74] Späth, H. 1996. Least-squares fitting by circles. Computing 57 179–185. [75] Späth, H. 1997. Least-squares fitting of ellipses and hyperbolas. Comput. Statist. 12 329–341. [76] Späth, H. 1997. Orthogonal least squares fitting by conic sections. S. Van Huffel, ed. Recent Advances in Total Least Squares and Errors-in-Variables Modeling. SIAM, Philadelphia, 259–264. [77] Srinivasan, V. 1996. How tall is the pyramid of Cheops?and other problems in computational metrology. SIAM News 864–72. [78] Tuy, H. 1995. D.C. optimization: Theory, methods and algorithms. R. Horst, P. M. Pardalos, eds. Handbook of Global Optimization. Kluwer Academic Publishers, Dordrecht, The Netherlands, 149–216. [79] Tuy, H. 1995. Canonical DC programming problem: Outer approximation methods revisited. Oper. Res. Lett. 18 99–106. [80] Tuy, H. 1998. Convex Analysis and Global Optimization. Kluwer Academic Publishers, Dordrecht, The Netherlands. [81] Tuy, H., F. Al-Khayyal, F. Zhou. 1995. A D.C. optimization method for single facility location problems. J. Global Optim. 7209–227. [82] Ventura, J. A., S. Yeralan. 1989. The minimax center estimation problem for automated roundness inspection. Eur. J. Oper. Res. 41 64–72. [83] Wagner, H. M. 1959. Linear programming techniques for regression analysis. J. Amer. Statist. Assoc. 54 206–212. [84] Webster, R. 1994. Convexity. Oxford University Press, Oxford, UK. [85] Yeralan, S., J. A. Ventura. 1988. Computerized roundness inspection. Internat. J. Production Res. 26 1921–1935. [86] Zwick. S. 1997. Applications of orthogonal distance regression in metrology. S. Van Huffel, ed. Recent Advances in Total Least Squares and Errors-in-Variables Modeling. SIAM, Philadelphia, 265–272.