Facility location problems in the plane based on reverse nearest neighbor queries

S. Cabello, J.M. Díaz-Báñez, S. Langerman, C. Seara and I. Ventura

European Journal of Operational Research, 2010, vol. 202, issue 1, 99-106

Abstract: For a finite set of points S, the (monochromatic) reverse nearest neighbor (RNN) rule associates with any query point q the subset of points in S that have q as its nearest neighbor. In the bichromatic reverse nearest neighbor (BRNN) rule, sets of red and blue points are given and any blue query is associated with the subset of red points that have it as its nearest blue neighbor. In this paper we introduce and study new optimization problems in the plane based on the bichromatic reverse nearest neighbor (BRNN) rule. We provide efficient algorithms to compute a new blue point under criteria such as: (1) the number of associated red points is maximum (MAXCOV criterion); (2) the maximum distance to the associated red points is minimum (MINMAX criterion); (3) the minimum distance to the associated red points is maximum (MAXMIN criterion). These problems arise in the competitive location area where competing facilities are established. Our solutions use techniques from computational geometry, such as the concept of depth of an arrangement of disks or upper envelope of surface patches in three dimensions.

Keywords: Reverse; nearest; neighbor; Competitive; location; Computational; geometry (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377-2217(09)00291-4
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:202:y:2010:i:1:p:99-106

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().