Three location tapas calling for CG sauce

XV Spanish Meeting on Computational Geometry, June 26-28, 2013 Three location tapas calling for CG sauce Frank Plastria∗1 1MOSI - Vrije Universiteit Brussel,Pleinlaan 2, B 1050 Brussels, Belgium Abstract Based on some recent modelling considerations in location theory we call for study of three CG constructs of Voronoi type that seem not to have been studied much before. Introduction There is a strong interrelation and mutual ensemination between (continuous) location theory and computational geometry. The first generates interest into distance optimization problems with geometrical interpretations, the second builds geometrical algorithms for efficient solution to the first’s problems. In this talk I will shortly present some recent work stemming from location theory calling for study of three novel (?) computational geometry constructs. 1 Mixed norm shortest paths The fact that the distance measure may be different from one region to another, contrary to the usual assumption that distance is measured by a single norm, has been acknowledged in only a few location studies. Parlar [14] considers the plane divided by a linear boundary with at one side `2and at the other side `1. Brimberg et al [2] consider a bounded region with a different norm inside and outside, focusing in particular on an axis-parallel rectangular city with `1inside and `2outside. Brimberg et al. [1] and Zaferanieh et al. [19] consider location in a space with two distinct `pnorms in complementary halfplanes. The way to calculate the distance in such a space was studied more in detail by Franco et al [7]. Fathali and Zaferanieh [5] extend this work to include more general block norms. Fliege [6] considers differentiably changing metrics similar to Riemann spaces. Unfortunately part of this work is wrong. All authors consider only two possibilities when calculating distances: when the two points lie in the same halfplane simply use the corresponding distance, and oth- ∗Email: F[email protected]e erwise in two steps via the best possible point on the separating line. Although this is true in some particular cases, e.g. the axis-parallel rectangular city case evoked before (but without inflation factors), Parlar already observed that in general when calculating distance in this naive way distance to a fixed point is not continuous everywhere. Worse: triangle inequality may be violated. This clearly shows that such distance calculation cannot be correct, but none of the authors try to resolve this discrepancy. What should rather be done is to consider shortest path distance in the space, similar to what is done in the so-called weighted (euclidean) region problem well known in CG since the original paper of Mitchell and Papadimitriou [10] (which depicts a clear counterexample to the naive distance above): the length of the shortest possible piecewise linear path using the adequate measure (speed in that paper) in each piece. For two halfspaces with arbitrary distinct norms or gauges we studied more in detail the optimality conditions when crossing the boundary, generalizing Snell’s law in optics. This has nice geometric interpretation and leads to a geometrical view on deriving such distances [16]. What turns out to be crucial is the comparison between the two norms along (the direction of) the separating line. As long as these are equal things remain relatively simple and the naive assumption about distances is correct. However, when they differ things change. One region is then ‘slower’ than the other (as measured along the boundary line). And in such a case some paths connecting two points within the slowest region will consist of three pieces. They ‘hitch a ride’ along the quicker boundary. Thereby continuity of the distance is again guaranteed, but now convexity is partially lost, as illustrated by the balls in the figure below. At right of the vertical separation line we have the slower region in gray with distance measure 4`1, at left the faster region with norm `2. The figure shows balls of increasing mixednorm radius centered at the dot. For very small radius we have the diamond-shaped `1ball. As soon as the radius allows to reach the boundary a part of circular shape arises at left due to two piece shortest paths, which spills over with a linearly moving front at the right corresponding to three piece paths. The white line shows the set of meeting points where one-piece 31 Three tapas with CG sauce and three-piece paths yield equal distance. slow: 4`1 fast: `2 It should be noted that Brimberg et al [2] correctly prove convexity of the distance from a fixed point to all points of the other region, but do not acknowledge that this convexity (quite crucial for their subsequent optimization approaches) does not extend to the whole plane if the fixed point lies in the slower region. The linearly separated two-norm situation is of course only the first step. For adequate description of some reality one will have to consider a plane split into cells each with their own norm or gauge (for asymmetry). How to efficiently calculate shortest path distances in such a context seems to be largely open, apart from some work on approximations, see Cheng et al. [3]. Correctly attacking location problems in such mixed norm spaces is another matter all together. A first step will probably be to look at Voronoi diagrams in such environments. Clearly a lot of opportunities for CG. Interesting applications may be found in firefighting using models to simulate the quite different ways fires spread in various circumstances, taking into account vegetation like (ir)regularly spaced plantations of varying types, influence of terrain inclination, and weather conditions, such as winds and humidity, and so forth. 2 Knapsack Voronoi diagrams Let Sbe a finite set of sources s∈R2with capacities cs>0. Consider the location of a central point x in the plane that should be connected to sufficiently many of the sources to be able to supply given demand D. The supply-weighted sum of distances should be minimized, possibly together with some additional costs f(x): min X s∈S wsd(s, x) + f(x)(1) X s∈S ws≥D(2) 0≤ws≤cs(3) x∈R2(4) This is a continuous single facility location-allocation problem that I have been studying under several variants for f(x), most of the time consisting of fixed weighted distances to demand point(s) [9, 17, 18, 15]. For any fixed location xfinding the best allocation W= (ws)s∈Sfor the supplies is a continuous knapsack problem, easily solved by taking sources s∈S at their full capacity ws=csin non-increasing order of distance d(s, x), until the demand Dis met. Only the last chosen source may contribute below its capacity, and all further sources will not contribute at all (ws= 0). There are only a finite number of allocations Wof such type possible. For any fixed allocation Wfinding the corresponding best site xamounts to solve a single facility minisum location problem (Fermat-Weber problem) which may be easily done by various methods of convex optimization. And this xshould then yield Was optimal allocation. It is therefore of interest to know the regions with fixed allocation. The planar subdivision corresponding to different solutions to this knapsack problem is what I call a Knapsack Voronoi diagram. In case all capacities are equal c, we obtain a traditional k-th order Voronoi diagram with k=dD/ce, with additional splits of some cells as soon as demand is not a multiple of capacity. When capacities differ the order kis not fixed and we have new types of diagrams. In particular vertices of the diagram may have from 3 up to 6 edges. The following examples show how vertices with 5 or 6 edges may arise. Demand is always D= 8, but in the first case ca= 10, cb= 6, cc= 5, while in the second ca= 4, cb= 6, cc= 5.  AAAAAAA a8        abc cba c5b3 acb cab c5a3 bac b6a2 bca b6c2 med(a,b) med(b,c) med(a,c) 32 XV Spanish Meeting on Computational Geometry, June 26-28, 2013  AAAAAAA A A A A A A A        abc a4b4 cba c5b3 acb a4c4 cab c5a3 bac b6a2 bca b6c2 med(a,b) med(b,c) med(a,c) As long as the coefficients of the distances d(s, x) in (1) are simply equal to wsthe edges of the corresponding Knapsack Voronoi diagram remain linear segments. But in some models such as the location of an assembly station [18] additional factors appear and then we need diagrams similar to multiplicatively weighted Voronoi diagrams, where cells have circular arcs as boundaries and may be disconnected. This shows the interest of studying the properties and efficient ways to calculate such diagrams, clearly a task for CG. More general constructs, such as multi-facility versions of previous location models may be considered where the allocation problem for fixed location(s) of the central facility(ies) to be located consists of a linear program with coefficients either fixed or depending only on the distances between sources and facility site(s). Such an LP can generically have only a finite number of optimal solutions, each corresponding to certain linear inequalities between the distances, so corresponding to (often empty) cells of a Voronoi-like diagram. I do not know of any study of such structures. 3 Push-pull Voronoi diagrams for points and polygons Push-pull location problems try to find good sites within a given region for facilities that at the same time are far (pushed away) from some repelling points r∈Rand close (pulled) to some other attracting points a∈A. For euclidean distances Ohsawa [11] fully constructs the set of efficient points for this biobjective maximinminimax problem. He shows that any such efficient point must lie on the boundary of cells obtained by intersecting the farthest-point Voronoi diagram w.r.t. Rwith the closest-point Voronoi diagram w.r.t. A within the given region. These line-segments may then be projected into two-dimensional value-space where an efficient CG boundary seeking technique finishes the job. This work has been extended later first to rectangular distance `1in [13], then to partial coverage problems in [12]. A few years ago together with José Gordillo and Emilio Carrizosa I studied [8] another similar pushpull location problem where the set Rconsists of extensive facilities described as polygonal regions. But instead of looking at the bi-objective problem that has a continuum of efficient solutions, we were looking for one particular solution that ‘best’ separates (if possible) Rfrom A. Separation was measured in a support vector machine way (see e.g. [4]) by maximizing the difference r2 R−r2 Awhere rRis the (euclidean) distance to the closest r∈Rand rAthe farthest distance to some a∈A. In the feasible case where Amay be separated by a circle from all regions in R, i.e. when this objective may be positive, this means geometrically that we seek the largest area annulus enclosing all points of Aand not meeting R. In the non feasible case the objective will always be negative and we look for the smallest area annulus that contains or overlaps all Aand such that its ‘hole’ does not meet R. These two cases are illustrated below; the annulus is coloured as light gray. rA rR (Feasible case) rArR (Unfeasible case) For a site xwe call ‘active’ any rclosest to x(the actual closest point(s) of this ris also called active) and any afarthest from x. We showed that generically three cases may arise at an optimal solution: 33 Three tapas with CG sauce (1) there are 4 active elements with at least one of each type, or there are 3 active elements with one a and two r(in the nonconvex case possible twice the same rwith different active points) either (2) with colinear active points, or (3) one active ractive at a vertex. Enumeration of all realizations of such cases leads to an O(n5)algorithm. However, these conditions are directly related to the farthest point Voronoi diagram VAw.r.t. Aand the closest point Voronoi diagram VRw.r.t. the polygons R. It is well known that edges of VRare parts of bisectors between two polygons, and these consist of successive linear and parabolic pieces depending on whether the active points of both polygons are of the same type (a vertex or on an edge) or not. The points where these pieces touch are called breakpoints. Now Case (1) may be realized in three ways: either as a vertex of VAor as a vertex of VRor as the point of intersection between an edge of VAand an edge of VR. Case (3) corresponds to a breakpoint of some edge of VRand case (2) happens at a finite number of points easily constructed from VR. Therefore using the CG approach should lead to much lower complexity. But this CG approach to the problems remains to be done. It should be noted that in an optimal solution to a multifacility version of this push-pull problem all sites will satisfy the same conditions, so the same set of candidate sites arises, but now several of such sites will have to be combined. References [1] J. Brimberg, H.T. Kakhki, G.O.Wesolowsky, Location among regions with varying norms, Annals of Operations Research 122 (2003), 87– 102. [2] J. Brimberg, H. Kakhki, G. Wesolowsky, Locating a single facility in the plane in the presence of bounded regions and different norms, Journal of the Operational Research Society of Japan 48 (2005) 135–147. [3] S. Cheng, H. Na, A. Vigneron, Y. Wang, Approximate Shortest Paths in Anisotropic Regions, SIAM Journal on Computing (2008) 38 802–824. [4] N. Cristianini and J. Shawe-Taylor. An Introduction to Support Vector Machines and Other Kernel-based Learning Methods. Cambridge University Press, Cambridge, 2000. [5] J. Fathali, M. Zaferanieh, Location problems in regions with lpand block norms, Iranian Journal of Operations Research 2(2011) 72–87. [6] J. Fliege, Efficient dimension reduction in multifacility location problems, Shaker Verlag, Aachen, 1997. [7] L. Franco, F. Velasco, L. Gonzalez-Abril, Gate points in continuous location between regions with different pnorms, European Journal of Operational Research 218 (2012) 648–655. [8] J. Gordillo, F. Plastria, E. Carrizosa, Locating a semi-obnoxious facility with repelling polygonal regions, working paper (2007) 30p. http://www.optimization-online.org/ DB_HTML/2007/04/1652.html [9] L. Kaufman, F.Plastria, The Weber problem with supply surplus, Belgian Journal of Operations Research, Statistics and Computer Science 28 (1988) 15–31. [10] J.S.B. Mitchell, C.H. Papadimitriou, The weighted region problem: finding shortest paths through a weighted planar subdivision, Journal of the ACM 38 (1991) 18–73. [11] Y. Ohsawa, Bicriteria Euclidean location associated with maximin and minimax criteria, Naval Research Logistics 47 (2000) 581–592 [12] Y. Ohsawa, F. Plastria, K. Tamura, Euclidean push-pull partial covering problems, Computers & Operations Research 33 (2006) 3566–3582 [13] Y. Ohsawa, K. Tamura, Efficient location for a semi-obnoxious facility Annals of Operations Research 123 (2003) 173–188 [14] M. Parlar, Single facility location problem with region-dependent distance metrics, International Journal of Systems Sciences 25 (1994) 513–525. [15] F.Plastria, Up and downgrading the euclidean 1-median problem, in preparation (2013) [16] F.Plastria, Shortest paths using varying distance functions, in preparation (2013) [17] F.Plastria, M.Elosmani, On the convergence of the Weiszfeld algorithm for continuous single facility location-allocation problems, TOP 16 (2008) 388–406. [18] F.Plastria, M.Elosmani, Continuous location of an assembly station, TOP First online (April 2011). [19] M. Zaferanieh, H. Kakhki, J. Brimberg, G. Wesolowsky, A BSSS algorithm for the single facility location problem in two regions with different norms, European Journal of Operational Research 190 (2008) 79–89. 34