Minimizing the Average Distance of Separated Points on the Plane in the L ^{1}Distance
 Author: Kim JaeHoon
 Organization: Kim JaeHoon
 Publish: Journal of information and communication convergence engineering Volume 10, Issue1, p1~4, 31 March 2012

ABSTRACT
Given separated points divided by a line, called a wall, in a plane, we aim to make a gate in the wall to connect the separated points to each other. In this setting, the problem is to find a location for the gate that minimizes the average distance between the points. The problem is a variant of the wellknown facility location problem, which is extensively studied in the fields of operations research, location theory, theoretical computer science, and so on. In this paper, we consider the
distance of the points in the plane. The points are projected onto the wall and so the problem is transformed to a proximity problem of points on a line. Then it is shown that the transformed problem is related to the weighted median problem of points on the line. Therefore, we obtain anL ^{1}O ( )time algorithm to solve our problem.n logn

KEYWORD
Average distance , L1distance , Facility location , Weighted median

I. INTRODUCTION
Let V and W be two sets of separated points in the plane, specifically, the
black points and thewhite points, respectively. If V  =n and W  =m , then theaverage distance betweenV andW , denoted by μ(V,W ), is defined to be the average distance ofp andq for all point pairs (p,q ) ∈V ×W :wher e
d(p,q) denotes the distance ofp andq in the plane, in particular, we will only consider theL ^{1}distance of the plane in this paper.In this paper, we consider the case in which
V andW are completely separated by awall . This is inspired by the situation where the Palestinian area and the Israeli area are separated by a wall. We cannot go through the wall from a black point to a white point. Thus we wish to make a gate in the wall in order to connect black points and white points. Then, to go from a black point to a white point, we should go from the black point to the gate and then from the gate to the white point. Therefore, for agateg , the distanced(p,q) between a black pointp and a white pointq in this environment is given byIn this paper, we will investigate a location problem in this environment, which is about where to make a gate in the wall. In particular, we are concerned in locating the gate to minimize the average distance between
V andW , which means constructing the gate to make mutual visits between the two separated areas easy.This is closely related to the wellknown
facility location problem, in which a company wants to open up a number of facilities to serve their customers. In the problem, both the opening of a facility at a specific location and the service of a customer by a facility incurs some cost. The goal is to minimize the overall cost of opening enough facilities to serve all the customers.There are four primary problems in facility location: the
p median problem, thep center problem, the uncapacitated facility locationproblem (UFLP) and the quadratic assignment problem (QAP). These problems are specific variants of the general facility location problem.Our problem may be considered one of a number of variants of the facility location problem. It corresponds to the case in which there is no cost to open a facility, say a gate, and the service costs are the distances between the pairs of black and white points.
In this paper, we will obtain an efficient algorithm to find a gate in the wall minimizing the average distance between black points and white points.
II. RELATED WORK
The problem of determining the average distance is mostly concentrated on the graph. One method of computing the average distance of a graph with n nodes is simply to compute the distances between all pairs of vertices, which is performed in time
O(n^{2}) . In [1], the author asked whether the average distance of a graph is easier to compute than all distances between vertices of the graph. An affirmative answer is given in [2], which presents an algorithm that computes the average distance of an interval graph with m edges of unit weight in timeO(m) . The author provides an algorithm that computes the average distance of a tree with n nodes and p edges in timeO(n) .Our problem is related to variants of the facility location problem in the Euclidean space: the median problem and the center problem. In the median problem, the sum of distances from the clients to their nearest facilities is minimized, whereas the maximum distance between the clients and their nearest facilities is minimized in the center problem.
For the 1median problem, it is wellknown that there is a linear time algorithm in R. But solving for the exact location of the Euclidean 1median in two or more dimensions is difficult in general. Indeed, no polynomialtime algorithm is known, nor has the problem been shown to be nondeterministic polynomialtime hard (NPhard) [3]. There is a randomized algorithm with its running time linear in n and polynomial in 1/
e [4, 5].For an arbitrary
p , in R, thep median can be solved exactly inO(pn) time [6]. However, it is NPhard even inR^{2}[7]. Arora et al. [8] provide anO (n ^{(O(1+1/e))})timee approximation algorithm.In the case of the 1center problem, there is a deterministic
O(n) time algorithm in R^{2} [9]. This result has been extended to R^{d} for any fixedd inO(d^{(O(d))}n) time by [10, 11]. The 2center problem has been solved by a number of works [1217]. The best recentsolution is anO (n log^{2}n log^{2} logn )time algorithm given in [18]. Agarwal and Sharir [19] provide a generalization of Drezner’s algorithm from R^{2} to R^{d} to give an algorithm requiringO(n^{d+1}) time.The Euclidean
k center problem can be solved in linear time in R using the algorithm of [20] for finding thek centers in a tree. The problem is shown to be NPhard in R^{2} [7]. There are many approximation algorithms for the Euclideank center problem [2124].The problem that we will deal with is one of various variants of the facility location problem and it is first investigated in this paper. We will propose an efficient algorithm running in linear time.
III. ALGORITHMS
Let
V andW be the sets of black points and white points, respectively, where V  =n and W  =m . There is a wall located betweenV andW and dividing the black points and the white points.We consider a gate
g , a point lying on the wall. Then the distanced(p,q) betweenp ∈V andq ∈W is given asd(p,q) =d(p,g) +d(g,q) . To compute the distance easily, we will apply the projections of points inV ∪W onto the wall as shown in Fig. 1. Letv be a point inV ∪W . Then the projection ofv onto the wall is denoted byThus the distance from
v to the gateg can be given byHere both the point
and the gate
g are located on the wall. Also note thatis uniquely determined regardless of the location of the gate
g .For
p ∈V andq ∈W , the distanced (p,q) is given asThus, for any black point
p ∈V , the sum of distances between it and all white pointsq ∈W is obtained byThus the sum of distances of all pairs of
p ∈V andq ∈W isLet
and
O =Then both
P andQ are fixedly determined. Therefore, the goal is transformed to minimizing the functionO . That is, we derive a onedimensional equivalent problem that finds a gate g to minimize the functionO for (n +m ) points given on the line. From this point on, we will solve the equivalent problem.Given points
on the line where V=
n and W=m , we want to obtain a (gate) pointg that minimizes the objective functionO given byHere, we will provide an algorithm
A to solve the above problem. We consider the pointsas points
p _{i} with weightsw _{i} on the line. Ifp _{i} ∈V , thenIf
p _{i} ∈W , thenThen the objective
O' =∑_{i}w _{i}d (p _{i},g ) is the same asThus the optimal solution
g also minimizesO' . We will show that the weighted median of pointsp_{i} minimizes the objectiveO' .The weighted median of points
p_{i} is defined to bep_{k} , one of the points satisfyingwhere ∑_{i}
W _{i} =1.Thus we consider an algorithm
A to find the weighted median of pointsp_{i} . InA , first sort the pointsp_{i} in nondecreasing order. Then sum up the weights of points until we have found the median, that is, until the sum is more than or equal toThus
A is run inO (n logn ) time.Given the validity of the algorithm
A , it remains to prove that the weighted median of points minimizes the objectiveO' . The next theorem shows that. Theorem 1: Given pointsp_{i} with weightsw_{i} on a line, where ∑_{i}w _{i} =1, for the weighted median μ of the points, the objective function ∑_{i}w_{i} d (p _{i} ,p ) is minimized whenp =μ.Proof: First, sort the pointsp_{i} in nondecreasing order. Then let the weighted median μ be the pointp_{k} . Assume to the contrary that the pointp minimizing the objective function is notp_{k} . Then we should consider two cases:because the points
p_{i} are sorted in nondecreasing order. Then we also obtain the following inequalities:Then we consider
L _{1}L andL _{2}L . We can show the terms are both nonnegative as follows:because from the definition of the weighted median,
Consequently, we show that
L _{1} ≥L andL _{2} ≥L . This completes the proof.Corollary 1: LetV andW be the sets of black points and white points, respectively, divided by a wall, where V =n and W =m . There is anO ((n +m ) log(n +m ))time algorithm to find a gate minimizing the average distance betweenV andW for theL ^{1}distance of the plane.IV. CONCLUSIONS
In this paper, we consider a variant of the facility problem in a plane. Given separated points divided by a wall, we find a gate locationon the wall to minimize the average distances between the points in L^{1}distance. An O(n log?n)time algorithm is provided, where n is the total number of points.
For further work, we may considervarious objective functions, for example, the longest distance between points, called by the diameter. Also the problem in which the number of gates is more than one is interesting.

[Fig. 1.] The projections of points onto the wall.