Advanced
Minimizing the Average Distance of Separated Points on the Plane in the L<sup>1</sup>-Distance
Minimizing the Average Distance of Separated Points on the Plane in the L1-Distance
Journal of information and communication convergence engineering. 2012. Mar, 10(1): 1-4
Copyright ©2012, The Korean Institute of Information and Commucation Engineering
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/3.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • Received : November 09, 2011
  • Accepted : December 20, 2011
  • Published : March 31, 2012
Download
PDF
e-PUB
PubReader
PPT
Export by style
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Jae-Hoon Kim
jhoon@pufs.ac.kr

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 well-known 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 L1 -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 an O ( n log n )-time algorithm to solve our problem.
Keywords
I. INTRODUCTION
Let V and W be two sets of separated points in the plane, specifically, the black points and the white points, respectively. If | V | = n and | W | = m , then the average distance between V and W , denoted by μ( V,W ), is defined to be the average distance of p and q for all point pairs ( p,q ) ∈ V × W :
PPT Slide
Lager Image
wher e d(p,q) denotes the distance of p and q in the plane, in particular, we will only consider the L 1 -distance of the plane in this paper.
In this paper, we consider the case in which V and W are completely separated by a wall . 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 agate g , the distance d(p,q) between a black point p and a white point q in this environment is given by
PPT Slide
Lager Image
In 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 and W , which means constructing the gate to make mutual visits between the two separated areas easy.
This is closely related to the well-known 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, the p -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(n2) . 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 time O(m) . The author provides an algorithm that computes the average distance of a tree with n nodes and p edges in time O(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 1-median problem, it is well-known that there is a linear time algorithm in R. But solving for the exact location of the Euclidean 1-median in two or more dimensions is difficult in general. Indeed, no polynomial-time algorithm is known, nor has the problem been shown to be non-deterministic polynomial-time hard (NP-hard) [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, the p -median can be solved exactly in O(pn) time [6] . However, it is NP-hard even inR 2 [7] . Arora et al. [8] provide an O ( n (O(1+1/e)) )-time e -approximation algorithm.
In the case of the 1-center problem, there is a deterministic O(n) -time algorithm in R 2 [9] . This result has been extended to R d for any fixed d in O(d(O(d))n) time by [10 , 11] . The 2-center problem has been solved by a number of works [12 - 17] . The best recentsolution is an O ( n log 2 n log 2 log n )-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 requiring O(nd+1) time.
The Euclidean k -center problem can be solved in linear time in R using the algorithm of [20] for finding the k -centers in a tree. The problem is shown to be NP-hard in R 2 [7] . There are many approximation algorithms for the Euclidean k -center problem [21 - 24] .
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 and W be the sets of black points and white points, respectively, where | V | = n and | W | = m . There is a wall located between V and W and dividing the black points and the white points.
We consider a gate g , a point lying on the wall. Then the distance d(p,q) between p V and q W is given as d(p,q) = d(p,g) + d(g,q) . To compute the distance easily, we will apply the projections of points in V W onto the wall as shown in Fig. 1 . Let v be a point in V W . Then the projection of v onto the wall is denoted by
PPT Slide
Lager Image
Thus the distance from v to the gate g can be given by
PPT Slide
Lager Image
PPT Slide
Lager Image
The projections of points onto the wall.
Here both the point
PPT Slide
Lager Image
and the gate g are located on the wall. Also note that
PPT Slide
Lager Image
is uniquely determined regardless of the location of the gate g .
For p V and q W , the distance d (p,q) is given as
PPT Slide
Lager Image
Thus, for any black point p V , the sum of distances between it and all white points q W is obtained by
PPT Slide
Lager Image
Thus the sum of distances of all pairs of p V and q W is
PPT Slide
Lager Image
Let
PPT Slide
Lager Image
and O =
PPT Slide
Lager Image
Then both P and Q are fixedly determined. Therefore, the goal is transformed to minimizing the function O . That is, we derive a one-dimensional equivalent problem that finds a gate g to minimize the function O for ( n + m ) points given on the line. From this point on, we will solve the equivalent problem.
Given points
PPT Slide
Lager Image
on the line where |V|= n and |W|= m , we want to obtain a (gate) point g that minimizes the objective function O given by
PPT Slide
Lager Image
Here, we will provide an algorithm A to solve the above problem. We consider the points
PPT Slide
Lager Image
as points p i with weights w i on the line. If p i V , then
PPT Slide
Lager Image
If p i W , then
PPT Slide
Lager Image
Then the objective O' =∑ i w i d ( p i , g ) is the same as
PPT Slide
Lager Image
Thus the optimal solution g also minimizes O' . We will show that the weighted median of points pi minimizes the objective O' .
The weighted median of points pi is defined to be pk , one of the points satisfying
PPT Slide
Lager Image
where ∑ i W i =1.
Thus we consider an algorithm A to find the weighted median of points pi . In A , first sort the points pi in non-decreasing order. Then sum up the weights of points until we have found the median, that is, until the sum is more than or equal to
PPT Slide
Lager Image
Thus A is run in O ( n log n ) time.
Given the validity of the algorithm A , it remains to prove that the weighted median of points minimizes the objective O' . The next theorem shows that.
Theorem 1: Given points pi with weights wi on a line, where ∑ i w i =1, for the weighted median μ of the points, the objective function ∑ i wi d ( p i , p ) is minimized when p =μ.
Proof: First, sort the points pi in non-decreasing order. Then let the weighted median μ be the point pk . Assume to the contrary that the point p minimizing the objective function is not pk . Then we should consider two cases:
PPT Slide
Lager Image
because the points pi are sorted in non-decreasing order. Then we also obtain the following inequalities:
PPT Slide
Lager Image
Then we consider L 1 - L and L 2 - L . We can show the terms are both non-negative as follows:
PPT Slide
Lager Image
because from the definition of the weighted median,
PPT Slide
Lager Image
Consequently, we show that L 1 L and L 2 L . This completes the proof.
Corollary 1: Let V and W be the sets of black points and white points, respectively, divided by a wall, where |V| = n and |W| = m . There is an O (( n + m ) log( n + m ))-time algorithm to find a gate minimizing the average distance between V and W for the L 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.
References
Chung F. R. K 1988 "The average distance and the independence number" Journal of Graph Theory 12 (2) 229 - 235    DOI : 10.1002/jgt.3190120213
Dankelmann P 1993 "Computing the average distance of an interval graph" Information Processing Letters 48 (6) 311 - 314    DOI : 10.1016/0020-0190(93)90174-8
Hakimi S. L 2000 "Location theory" in Handbook of Discrete and Combinatorial Mathematics. CRC Press Boca Raton 986 - 995
Indyk P 1999 "Sublinear time algorithms for metric space problems" Proceedings of the 31st Annual ACM Symposium on the Theory of Computing Atlanta: GA 428 - 434
Bose P , Maheshwari A , Morin P 2003 "Fast approximations for sums of distances, clustering and Fermat-Weber problem" Computational Geometry: Theory and Applications 24 (3) 135 - 146
Hassin R , Tamir A 1991 "Improved complexity bounds for location problems on the real line" Operations Research Letters 10 (7) 395 - 402    DOI : 10.1016/0167-6377(91)90041-M
Megiddo N , Supowit K. J 1984 "On the complexity of some common geometric location problems" SIAM Journal on Computing 13 (1) 182 - 196    DOI : 10.1137/0213014
Arora S , Raghavan P , Rao S 1998 "Approximation schemes for Euclidean k-medians and related problems" Proceedings of the 30th Annual ACM Symposium on Theory of Computing Dallas: TX 106 - 113
Megiddo N 1983 "Linear-time algorithms for linear programming in R3and related problems" SIAM Journal on Computing 12 (4) 759 - 776    DOI : 10.1137/0212052
Agarwal P. K , Sharir M , Toledo S 1993 "An efficient multi-dimensional searching technique and its applications" Duke University Durham: NC Technical Report CS-1993-20
Chazelle B , Matousek J 1996 "On linear-time deterministic algorithms for optimization problems in fixed dimension" Journal of Algorithms 21 (3) 579 - 597    DOI : 10.1006/jagm.1996.0060
Drezner Z 1984 "The planar two-center and two-median problems" Transportation Science 18 (4) 351 - 361    DOI : 10.1287/trsc.18.4.351
Eppstein D 1992 "Dynamic three-dimensional linear programming" ORSA Journal on Computing 4 (4) 360 - 368    DOI : 10.1287/ijoc.4.4.360
Hershberger J 1993 "A faster algorithm for the two-center decision problem" Information Processing Letters 47 (1) 23 - 29    DOI : 10.1016/0020-0190(93)90153-Z
Agarwal P. K , Sharir M 1994 "Planar geometric location problems" Algorithmica 11 185 - 195    DOI : 10.1007/BF01182774
Katz M. J , Sharir M 1993 "An expander-based approach to geometric optimization" Proceedings of the 9th Annual Symposium on Computational Geometry San Diego: CA 198 - 207
Sharir M 1997 "A near-linear algorithm for the planar 2-center problem" Discrete and Computational Geometry 18 (2) 125 - 134    DOI : 10.1007/PL00009311
Chan T. M 1999 "More planar two-center algorithms" Computational Geometry 13 (3) 189 - 198    DOI : 10.1016/S0925-7721(99)00019-X
Agarwal P. K , Sharir M 1998 "Efficient algorithms for geometric optimization" ACM Computing Surveys 30 (4) 412 - 458    DOI : 10.1145/299917.299918
Frederickson G. N 1991 "Parametric search and locating supply centers in trees" Proceedings of the 2nd Workshop on Algorithms and Data Structure Ottawa 299 - 319
Gonzalez T. F 1985 "Clustering to minimize the maximum intercluster distance" Theoretical Computer Science 38 293 - 306    DOI : 10.1016/0304-3975(85)90224-5
Hochbaum D. S , Shmoys D. B 1986 "A unified approach to approximate algorithms for bottleneck problems" Journal of the ACM 33 (3) 533 - 550    DOI : 10.1145/5925.5933
Feder T , Greene D 1988 "Optimal algorithms for approximate clustering" Proceedings of the 20th Annual ACM Symposium on Theory of Computing Chicago: IL 434 - 444
Agarwal P. K , Procopiuc C. M 1998 "Exact and approximation algorithms for clustering" Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms San Francisco: CA 658 - 667