On the overlap area of a disk and a piecewise circular domain.

*(English)*Zbl 1458.90422Summary: We provide an approach to solve the problem of locating a disk so that its overlap area with a piecewise circular domain is near-optimal when considering partial converage. To this purpose, we introduce the concept of overlap area map. Both, overlap area maps and near-optimal locations, provide useful tools for solving problems related to the placement, for example, of emergency warning sirens, cellular towers or radio receiving stations, that are commonly encountered in the location science field. We present parallel algorithms on graphics processing units (GPUs) for computing an overlap area map and obtaining a set of near-optimal locations from the overlap area map. These algorithms have as a key element the overlap area computation process to which we pay special attention. In addition, we describe a way of visualizing the obtained solutions. Integration of computation and visualization facilitates decision makers, with an iterative what-if-analysis process, to gain more information in order to facilitate the selection of an appropriate location. Finally, we also provide and discuss experimental results showing the efficiency and scalability of our approach.

##### MSC:

90B80 | Discrete location and assignment |

90B50 | Management decision making, including multiple objectives |

90-08 | Computational methods for problems pertaining to operations research and mathematical programming |

##### Keywords:

decision support systems; facility placement; service coverage; continuous space; graphics processing unit (GPU)
Full Text:
DOI

##### References:

[1] | Bansal, M.; Kianfar, K., Planar maximum coverage location problem with partial coverage and rectangular demand and service zones, INFORMS J. Comput., 29, 152-169, (2017) · Zbl 1364.90285 |

[2] | Berman, O.; Drezner, Z.; Krass, D., Generalized coverage: new developments in covering location models, Comput. Oper. Res., 37, 1675-1687, (2010) · Zbl 1188.90147 |

[3] | Berman, O.; Krass, D., The generalized maximal covering location problem, Comput. Oper. Res., 29, 563-581, (2002) · Zbl 0995.90056 |

[4] | Berman, O.; Krass, D.; Drezner, Z., The gradual covering decay location problem on a network, Eur. J. Oper. Res., 151, 474-480, (2003) · Zbl 1053.90076 |

[5] | (Cai, Y.; See, S., (2015), Springer: Springer Singapore) |

[6] | Cheng, S. W.; Lam, C. K., Shape matching under rigid motion, Comput. Geom. Theory Appl., Vol. 46, 591-603, (2013) · Zbl 1267.65024 |

[7] | Cheong, O.; Efrat, A.; Har-Peled, S., Finding a guard that sees most and a shop that sells most, Discr. Comput. Geom., 37, 4, 545-563, (2007) · Zbl 1118.52011 |

[8] | Church, R. L., The planar maximal covering location problem, J. Reg. Sci., 24, 2, 185-201, (1984) |

[9] | Church, R. L.; ReVelle, C., The maximal covering location problem, Pap. Reg. Sci. Assoc., 32, 101-118, (1974) |

[10] | Church, R. L.; Roberts, K. L., Generalized coverage models and public facility Location, Papers of the Regional Science Association, 117-135, (1983) |

[11] | Coll, N.; Fort, M.; Sellarés, J. A., Computing the maximum overlap of a disk and a polygon with Holes under translation, XVI Encuentros de Geometría Computacional, 57-60, (2015) |

[12] | Coll, N.; Fort, M.; Sellarés, J. A., Computing the maximum overlap of a disk and a piecewise circular domain under translation, European Workshop on Computational Geometry (EuroCG), 223-226, (2016) |

[13] | Daskin, M. S., Network and Discrete Location: Models, Algorithms and Applications, (1995), John. Wiley and Sons, Inc.: John. Wiley and Sons, Inc. New York · Zbl 0870.90076 |

[14] | Downs, B. T., Jeff camm, an exact algorithm for the maximal covering problem, Nav. Res. Logist., 43, 3, 435-461, (1996) · Zbl 0846.90076 |

[15] | Drezner, T.; Drezner, Z., Replacing continuous demand with discrete demand in a competitive location model, Nav. Res. Logist., 44, 81-95, (1997) · Zbl 0882.90083 |

[16] | Drezner, Z.; Wesolowsky, G. O.; Drezner, T., The gradual covering problem, Naval Res. Logist. (NRL), 51, 841-855, (2004) · Zbl 1075.90047 |

[17] | Espejo, L. G.A.; Galvão, R. D.G.; Boffey, B., Dual-based heuristics for a hierarchical covering location problem, Comput. Oper. Res., 30, 2, 165-180, (2003) · Zbl 1029.90034 |

[18] | Farahani, R. Z.; Asgari, N.; Heidari, N.; Hosseininia, M.; Goh, M., Covering problems in facility location: a review, Comput. Ind. Eng., 62, 368-407, (2012) |

[19] | Galvão, R. D.G., Charles revelle, a lagrangean heuristic for the maximal covering location problema, Eur. J. Oper. Res., 88, 114-123, (1996) |

[20] | (Hwu, W. W., GPU Computing Gems Emerald Edition, (2011), Morgan Kaufmann) |

[21] | Karasakal, O.; Karasakal, E. K., A maximal covering location model in the presence of partial coverage, Comput. Oper. Res., 31, 1515-1526, (2004) · Zbl 1107.90028 |

[22] | Lee, J. M.; Lee, Y. H., Tabu based heuristics for the generalized hierarchical covering location problema, Comput. Ind. Eng., 58, 4, 638-645, (2010) |

[23] | Matisziw, T. C.; Murray, A. T., Siting a facility in continuous space to maximize coverage of a region, Socioecon. Plann. Sci., 43, 131-139, (2009) |

[24] | Megiddo, N.; Zemel, E.; Hakimi, S. L., The maximum coverage location problem, SIAM J. Algebr. Discret. Method., 4, 2, 253-261, (1983) · Zbl 0514.90019 |

[25] | Mount, D. M.; Silverman, R.; Wu, A. Y., On the area of overlap of translated polygons, Comput. Vision Image Underst., 64, 1, 53-61, (1996) |

[26] | Murray, A. T., Geography in coverage modeling: exploiting spatial structure to address complementary partial service of areas, Ann. Assoc. Am. Geogr., 95, 4, 761-772, (2005) |

[27] | Murray, A. T.; Matisziw, T. C.; Wei, H.; Tong, D., A geocomputational heuristic for coverage maximization in service facility siting, Trans. GIS, 12, 6, 757-773, (2008) |

[28] | Murray, A. T.; Tong, D., Coverage optimization in continuous space facility siting, Int. J. Geogr. Inf. Sci., 21, 7, 757-776, (2007) |

[29] | Resende, M. G.C., Computing approximate solutions of the maximum covering problem with GRASP, J. Heurist., 4, 161-177, (1998) · Zbl 0913.90202 |

[30] | ReVelle, C.; Scholssberg, M.; Williams, J., Solving the maximal covering location problem with heuristic concentration, Comput. Oper. Res., 35, 427-435, (2008) · Zbl 1141.90472 |

[31] | Riley, K. F.; Hobson, M. P.; Bence, S. J., Mathematical methods for physics and engineering, (2010), Cambridge University Press · Zbl 0884.00001 |

[32] | Snyder, L. V., Covering Problems, (Eiselt, H. A.; Marianov, V., Foundations of Location Analysis, (2011), Springer-Verlag), 109-135 · Zbl 1387.90117 |

[33] | Song, D.; van der Stappen, A.; Goldberg, K., Exact algorithms for single frame selection on multiaxis satellites, IEEE Trans. Autom. Sci. Eng., 3, 16-28, (2006) |

[34] | Wei, R.; Murray, A. T., Continuous space maximal coverage: insights, advances and challenges, Comput. Oper. Res., 62, 325-336, (2014) · Zbl 1348.90434 |

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.