Reverse facility location problems

Abstract

The Reverse Nearest Neighbor (RNN) problem is to find all points in a given data set whose nearest neighbor is a given query point. Given a set of blue points and a set of red points, the bichromatic version of the RNN problem, for a query blue point, is to find all the red points whose blue nearest neighbour is the given query point. In this paper, we introduce and investigate optimization problems according to the Bichromatic Reverse Nearest Neighbor rule (BRNN). We give efficient algorithms to compute a new blue point such that: (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). Our solutions use techniques from computational geometry, such as the concept of depth in an arrangement of disks or upper envelope of surface patches in three dimensions. 1