Approximation algorithms for the mobile piercing set problem with applications to clustering in ad-hoc networks.
The main contributions of this paper are two-fold. First, we present a simple, general framework for obtaining efficient constant-factor approximation algorithms for the mobile piercing set (MPS) problem on unit-disks for standard metrics in fixed dimension vector spaces. More specifically, we provide low constant approximations for L1- and L-norms on a d-dimensional space, for any fixed d > 0, and for the L2-norm on 2- and 3-dimensional spaces. Our framework provides a family of fully-distributed and decentralized algorithms, which adapts (asymptotically) optimally to the mobility of disks, at the expense of a low degradation on the best known approximation factors of the respective centralized algorithms: Our algorithms take O(1) time to update the piercing set maintained, per movement of a disk. We also present a family of fully-distributed algorithms for the MPS problem which either match or improve the best known approximation bounds of centralized algorithms for the respective norms and dimensions.Second, we show how the proposed algorithms can be directly applied to provide theoretical performance analyses for two popular 1-hop clustering algorithms in ad-hoc networks: the lowest-id algorithm and the Least Cluster Change (LCC) algorithm. More specifically, we formally prove that the LCC algorithm adapts in constant time to the mobility of the network nodes, and minimizes (up to low constant factors) the number of 1-hop clusters maintained; we propose an alternative algorithm to the lowest-id algorithm which achieves a better approximation factor without increasing the cost of adapting to changes in the network topology. While there is a vast literature on simulation results for the LCC and the lowest-id algorithms, these had not been formally analysed prior to this work. We also present an O(log n)-approximation algorithm for the mobile piercing set problem for nonuniform disks (i.e., disks that may have different radii), with constant update time.
Introduction
The mobile piercing set (MPS) problem is a variation of the (classical) piercing set problem that arises in
dynamic distributed scenarios. The MPS problem has many applications outside its main computational
geometry domain, as for example in mobile ad-hoc communication networks, as we will see later.
We start by formalizing some basic denitions. A disk D of radius r with center q in < d with respect
to L p norm 1 is given by the set of points rg. Let q(D) denote the center of a
disk D. A piercing set of a given collection of disks D is a set of points P such that for every disk D 2 D,
there exists a point pierces every disk D 2 D. The (classical) k-piercing
set problem seeks to nd whether a piercing set P of cardinality k of D exists, and if so, produces it. If
the value of k is minimal over all possible cardinalities of piercing sets of D then the set P is called a
minimum piercing set of D. The minimum piercing set problem asks for the minimum piercing set of a
given collection D.
We consider a dynamic variation of the classical piercing set problem, which arises in mobile and
distributed scenarios, where disks are moving in space. In the mobile piercing set (MPS) problem, we
would like to maintain a dynamic piercing set P of a collection of mobile disks D such that, at any time
t, P is a minimum piercing set of the current conguration of the disks. In other words, P must adapt
to the mobility of the disks. Moreover, we would like to be able to devise a distributed algorithm to
solve this problem, where the individual disks can decide in a distributed fashion (with no centralized
control) where to place the piercing points. In this scenario, we assume that the disks are able to detect
whether they intersect other disks. We can think about a disk as being the communication range of a
given mobile device (node), which resides at the center of the disk: A disk can communicate with all of
its adjacent nodes by a broadcast operation within O(1) time. Below, we will present applications of the
1 The Lp norm, for any xed p, of a vector z in < d is given by jjzjj
mobile piercing set problem in mobile networks.
In this paper, we focus on the case when the disks are all of the same radius r | or equivalently,
of same diameter 2r. Hence, without loss of generality, in the remainder of this paper, unless stated
otherwise, we assume that therefore that we have a collection of unit-diameter disks, or
unit-disks for short. In Section 5, we address an extension of our algorithms to the nonuniform case,
where the disks may not all have the same radius.
In recent years, the technological advances in wireless communications have led to the realization of
ad-hoc mobile wireless networks, which are self-organizing and which do not rely on any sort of stationary
backbone structure. These networks are expected to signicantly grow in size and usage in the next few
years. For scalability, specially in order to be able to handle updates due to the constant changes in
network topology, clustering becomes mandatory.
As hinted above, mobile unit-disks can be used to model an ad-hoc network where all mobile wireless
nodes have the same range of communication. Each mobile node's communication range is represented
by a disk in < 2 (or < 3 ) centered at the node with radius equal to 1; a mobile node A can communicate
with mobile node B if and only if B is within A's communication range. The ad-hoc network scenario is a
direct application scenario for the unit-disk MPS problem, since an ad-hoc network is fully decentralized
and any algorithm running on such a network must adapt to mobility in an e-cient way.
If all disks are of the same size, then the k-piercing set problem is equivalent to the decision version
of a well-known problem: the geometric k-center problem [2]. The k-center problem under L p metric
is dened as follows: Given a set S of n demand points in < d , nd a set P of k supply points so that
the maximum L p distance between a demand point and its nearest supply point in P is minimized. The
corresponding decision problem is to determine, for a given radius r, whether S can be covered by the
union of k L p -disks of radius r, or in other words, to determine whether there exists a set of k points that
pierces the set of n L p -disks of radius r centered at the points of S. In some applications, P is required
to be a subset of S, in which case the problem is referred to as the discrete k-center problem. When
we choose the L 2 metric, the problem is called the Euclidean k-center problem, while for L1 metric the
problem is called the rectilinear k-center problem. Since the Euclidean and rectilinear k-center problems
in < 2 are NP-complete (see e.g. [26, 29]) when k is part of the input, the planar unit-disk k-piercing
set problem in < 2 under norms is also NP-complete. Unfortunately, an approximation
algorithm for the k-center problem does not translate directly into an approximation algorithm for the
unit-disk piercing set problem (and vice-versa), since an algorithm for the former problem will give an
approximation on the radius of the covering disks, while for the latter problem we need an approximation
on the number of piercing points. Still, the two approximation factors are highly related [2].
The remainder of this paper is organized as follows. In Section 1.1, we state our main contributions in
this work. In Section 2, we discuss more related work in the literature. Section 3 proves some geometric
properties of the piercing set problem. We use the results in Section 3 to develop the approximation
algorithms presented in Sections 4 and 5: The algorithm introduced in Section 4 leads to lower approximation
factors, for the norms and dimensions considered, while the one in Section 5 adapts optimally
to the movement of disks. In Section 6, we relate the algorithms presented for the MPS problem to
clustering in ad-hoc networks. Finally, we present some future work directions in Section 7.
1.1 Our results
In this paper we propose fully distributed (decentralized) approximation algorithms for the unit-disk
MPS problem for some xed norms and dimensions. All of the approximation factors presented in this
paper are with respect to the number of points in a minimum piercing set.
For each algorithm, we are interested in computing the cost associated with building an initial approximate
piercing set for the given initial conguration of the collection of disks | which we call the
setup cost of the algorithm | and the cost associated with updating the current piercing set due to the
movement of a disk | which we call the update cost of the algorithm. Actually we charge the update
costs per event, as we explain below. We assume that all the costs that do not involve communication
between disks are negligible when compared to the cost of a disk communicating with its neighbors
(through a broadcast operation). Therefore we will only consider communication costs when evaluating
the algorithms considered.
In order to maintain an optimal or approximate piercing set of the disks, there are two situations
which mandate an update on the current piercing set. The rst situation is when the movement of a
disk D results in having at least one disk D 0 of D unpierced (note that D 0 may be D itself). The second
situation is when some piercing points in the set maintained become \redundant", and we may need to
remove them from the set. Thus, we say that an (update) event is triggered (or happened) whenever one
of the two situations just described occurs.
The main contributions of this paper are two-fold. First, we present a family of constant-factor
approximation algorithms | represented by the M-algorithm | for the unit-disk MPS problem with
(asymptotically) optimal setup and update costs, for all the norms and space dimensions considered.
Moreover, we achieve this without a signicant increase in the approximation factor of the corresponding
best known approximation algorithms for the classical piercing set problem. Let P  be a minimum
piercing set. More specically, in d dimensions, we devise a 2 d -approximation algorithm under L 1 or
L1 . For L 2 norm, we devise a seven-approximation algorithm in < 2 , and a 21-approximation algorithm
in < 3 . All these algorithms have O(jP  cost and O(1) update cost. Note that any dynamic
algorithm that approximates the minimum piercing set of a collection of mobile disks has setup cost
jP  j), and update cost
st These algorithms are the rst constant-approximation algorithms for
the unit-disk MPS problem, with asymptotically optimal setup and update costs. We summarize these
results in Table 1. 2
We also present a second family of fully distributed algorithms | represented by the A-algorithm |
for L 1 or L1 norms in any space < d , and for L 2 norm in < 2 and < 3 . These algorithms achieve the same,
or better, constant approximation factors as the best known centralized algorithms for the corresponding
norm and space dimension, but have a poorer update cost of O(jP  j). These algorithms are, to the best
of our knowledge, the rst fully distributed (decentralized) approximation algorithms which achieve the
same approximation factors as their centralized counterparts. These algorithms are of interest since, for
example, they provide an alternative algorithm to the lowest-id clustering algorithm in ad-hoc networks,
which would achieve a four- (resp., 11-) approximation factor in < 2 (resp., < 3 ) without an increase on
setup and update costs. We summarize these results in Table 2. 2
The simple framework presented for the M-algorithm, which can handle mobility e-ciently in a
dynamic scenario, is an important contribution of this work on its own. It avoids the use of involved data
structures, which in general cannot avoid the use of some sort of \centralization" (even if implicitly). In
order to be able to apply the given framework to a particular norm and dimension, one needs only to
be able to compute a set of piercing points which are guaranteed to pierce the immediate neighborhood
2 All the results are for unit-disks; Lp is equivalent to L1 for any p in one dimension.
of any disk D: The number of such points will be used in bounding the approximation factor of the
algorithms proposed.
The second main contribution of this work is the application of the algorithms developed for the MPS
problem to the problem of nding an e-cient self-organizing one-hop underlying clustering structure
for (wireless and mobile) ad-hoc networks, as seen in Section 6. In fact, one can use the algorithms
developed for the MPS problem to derive the rst theoretical performance analyses of the popular Least
proposed by Chiang et al. [7], and of the lowest-id algorithm (discussed
by Gerla and Tsai in [15]), both in terms of the number of one-hop clusters maintained and in terms of
update and setup costs, thus providing a deeper understanding of these two algorithms and validating
the existing simulation results for the same. No previous formal analysis of either algorithm exists in
the literature. Namely, we show that the LCC algorithm has the same approximation factor, setup and
update costs as the M-algorithm for L 2 in < 2 (or < 3 ), and that the lowest-id algorithm also maintains
the same approximation factor as the M-algorithm, while incurring higher update costs.
Another contribution of our work addresses the MPS problem on nonuniform radius disks. Then, if
the ratio between the maximum and minimum disk radii is bounded by a polynomial on
present a fully-distributed O(log n)-approximation algorithm for this problem, with constant update cost.
Related Work
The k-center and k-piercing problems have been extensively studied. In d dimensions, a brute-force
approach leads to an exact algorithm for the k-center problem with running time O(n dk+2 ). For the
planar case of the Euclidean k-center problem, Hwang et al. [24] gave an n O(
improving
Drezner [9] solution which runs in time O(n 2k+1 ). An algorithm with the same running time was
presented in Hwang et al. [23] for the planar discrete Euclidean k-center problem. Recently, Agarwal and
Procopiuc [1] extended and simplied the technique by Hwang et al. [24] to obtain an n O(k 1 1=d
algorithm for computing the Euclidean k-center problem in d dimensions.
Sharir and Welzl [32] explain a reduction from the rectilinear k-center problem to the k-piercing set
problem (under L1 metric), using a sorted matrix searching technique developed by Frederickson and
Johnson [13]. Ko et al. [26] proved the hardness of the planar version of the rectilinear k-center and
presented an O(n log n) time 2-approximation (on the covering radius) algorithm. (In fact, Ko et al. [26]
proved that, unless the best approximation factor that can be achieved in polynomial time for
the rectilinear k-center problem is 2.) Several approximation results (on the radii of the disks) have been
obtained in [11, 17, 20, 21]. For more results on the k-center problem, please refer to [2].
Regarding the k-piercing set problem in < d , Fowler et al. [12] proved the NP-completeness of nding
the minimum value of k for a given set of n disks. Hochbaum and Maas [19] gave an O(l d n 2l d +1 )
polynomial time algorithm for the minimum piercing set problem with approximation factor (1
l ) d for
any xed integer l  1. Thus, for yields an O(n 3
with performance ratio 2 d . For the one-dimensional case, Katz et al. [25] presented an algorithm that
maintains the exact piercing set of points for a collection of n intervals in O(jP  j log n) time, where
P  is a minimum piercing set. Their solution can be adapted to obtain an algorithm with distributed
running time O(jP  computing a minimum piercing set of n intervals. Nielsen [30] proposed a 2 d 1 -
approximation algorithm that works in d-dimensional space under L1 metric in O(dn
where c is the size of the piercing set found. This algorithm is based on the divide-and-conquer paradigm.
Although not stated explicitly, the approximation on the radius of the k-center problem in [1] implies
a four-approximation algorithm for the minimum piercing set problem for < 2 and L 2 . Efrat et al. [10]
introduced a dynamic data structure based on segment trees which can be used for the piercing set
problem. They presented a sequential algorithm which gives a constant factor approximation for the
minimum piercing set problem for \fat" objects with polynomial setup and update time. See [10] for the
denition of \fatness" and more details.
A large number of clustering algorithms have been proposed and evaluated through simulations in
the ad-hoc network domain, as for example in [3, 4, 15, 27, 28, 31]. Gerla and Tsai in [15] considered two
distributed clustering algorithms, the lowest-id algorithm and the highest-degree algorithm, which select
respectively the lowest-id mobile or the highest degree mobile in a one-hop neighborhood as the cluster-
head. A weight oriented clustering algorithm, more suitable to \quasi-static" networks, was introduced
by Basagni [4], where one-hop clusters are formed according to a weight-based criterion that allows the
choice of the nodes that coordinate the clustering process based on node mobility-related parameters.
In [27], Lin and Gerla described a non-overlapping clustering algorithm where clusters are able to be
dynamically recongured.
The LCC algorithm proposed by Chiang et al. [7] aims to maintain a one-hop clustering of a mobile
network with least number of changes in the clustering structure, where clusters will be broken and
re-clustered only when necessary. In fact, our algorithm for the MPS problem, when translated to a
clustering algorithm in the ad-hoc scenario, is essentially the LCC algorithm, as discussed in Section 6.
Recently, researchers have investigated using geometric centers as clusterheads in order to minimize
the maximum communication cost between a clusterhead and the cluster members. Bepamyatnikh et
al. [6] discussed how to compute and maintain the one-center and the one-median for a given set of n
moving points on the plane (the one-median is a point that minimizes the sum of all distances to the
input points). Their algorithm can be used to select clusterheads if mobiles are already partitioned into
clusters.
Gao et al. [14] proposed a randomized algorithm for maintaining a set of clusters based on geometric
centers, for a xed radius, among moving points on the plane. Their algorithms have expected approximation
factor on the optimal number of centers (or, equivalently, of clusters) of c 1 log n for intervals
and of c 2
n for squares 3 , for some constants c 1 and c 2 . The probability that there are more than c
times the optimal number of centers is 1=n for the case of intervals; for squares, the probability that
there are more than c
times the optimal number of centers is 1=n
extension of this basic algorithm led to a hierarchical algorithm, also presented in [14], based on kinetic
data structures [5]. The hierarchical algorithm admits an expected constant approximation factor on the
number of discrete centers, where the approximation factor also depends linearly on the constants c 1 and
. The dependency of the approximation factor and the probability that the algorithm chooses more
than a constant times the optimal number of centers is similar to that of the non-hierarchical algorithm
for the squares case. The constants c 1 and c 2 , which have not been explicitly determined in [14], can be
shown to be very large (certainly more than an order of magnitude larger than the corresponding approximation
constant presented in this paper), even if we allow the probability of deviating from the expected
constant approximation on the number of centers (which depends linearly on c 1 and c 2 ) not to be close
to one. Their algorithm has an expected update time of O(log 3:6 n) (while the update cost is constant in
our algorithm), the number of levels used in the hierarchy is O(log log n), with O(n log n log log n) total
space.
3 Disks in 1D correspond to intervals on the line; in 2D, Disks under L1 or L1 are called squares.
Har-Peled [18] found a scheme for determining centers in advance, if the degree of motion of the nodes
is known: More specically, if in the optimal solution the number of centers is k and r is the optimal
radius for the points moving with degree of motion ', then his scheme guarantees a 2 '+1 -approximation
(of the radius) with k '+1 centers chosen from the set of input points before the points start to move.
3 Geometry for the Piercing Set Problem
In this section, we prove some geometric properties of the minimum piercing set problem. More specif-
ically, we solve the minimum piercing set problem on the neighborhood of a disk, which will provide the
basic building block for our approximation algorithms presented in the following sections. The main
step of the approximation algorithms is to select an unpierced unit-disk and pierce all of its neighbors.
By repeating this procedure, we will eventually pierce all unit-disks and form a piercing set. The approximation
factors are determined by the number of piercing points chosen for each selected unpierced
unit-disk.
If two disks D and D 0 intersect, we say that D is a neighbor of D 0 . The neighborhood of a disk D,
denoted by N (D), is dened as the collection of all disks that intersect D, N
Note that D 2 N (D).
We are interested on the minimum number of points that pierce all disks in the neighborhood of a
given disk. However, this number may vary, depending on the distribution of the disks in the particular
neighborhood in consideration. Thus, we compute the minimum number (along with the xed positions)
of points needed to pierce any possible neighborhood of a disk. This number is called the neighborhood
piercing number. The neighborhood piercing number is tight in the sense that for any set of points with
smaller cardinality, we can nd some conguration of the neighborhood of a disk which has an unpierced
disk. The corresponding piercing points are called the neighborhood piercing points. Clearly, the piercing
number is a function of both dimension d and norm index p. Hence, we denote the neighborhood piercing
number for dimension d and norm index p as N(d; p), and we use PN(D; d; p) to denote a corresponding set
of neighborhood piercing points of a unit-disk D. 4 We prove in this section that N(d;
for all d  1, and that N(2; 7. We also place an upper bound of 21 on N(3; 2). For each of the
norms and dimensions considered, we give a corresponding set of neighborhood piercing points.
4 In general, we omit the parameters p, d, or D, whenever clear from the context.
First we reduce the minimum piercing set problem into an equivalent disk covering problem. Let D
be a collection of unit-disks and P be a set of points. Let P 0 be the set of centers of all disks in D, and
D 0 be a collection of unit-disks centered at points in P . Then P pierces D if and only if D 0 covers P 0 .
Moreover, P is a minimum piercing set for D if and only if D 0 is a minimum set of disks (with respect
to cardinality) that covers P 0 . We dene the unit-disk covering problem to be the problem of nding the
minimum k such that there are k unit-disks whose union covers a given point set.
We now reduce the problem of nding the neighborhood piercing number to a unit-disk covering
problem as follows. For a unit-disk D, all the centers of unit-disks in N (D) are located in the region
is the center of D. Conversely, a disk centered at any
point in G must intersect D. Therefore, we seek for the minimum number of unit-disks that cover region
G. The centers of those disks serve as the set of neighborhood piercing points PN(D). The tightness of
N can be seen from the fact that in the disk covering problem, we cannot cover the entire region G with
less than N disks, as proven in the following lemma. Note that the region G is a disk of radius 1, and
that all of the disks that we use to cover G are unit-disks (i.e., of radius 1).
Lemma 1 The neighborhood piercing number is equal to 2 d for a d-dimensional space under L 1 or L1
norm. The neighborhood piercing number for two dimensions and L 2 is equal to seven.
Proof: For any L p norm, in a d-dimensional space, the ratio of the area of G to the area of a unit-disk
is 2 d . Thus, we need at least 2 d disks to cover G | i.e., N  2 d for any dimension d  1 and any norm
. The lower bound of 2 d is in fact tight for since in any dimension d, the unit-disk
D has 2 d \corners" under these norms, and the set of unit-disks centered at those \corners" cover the
entire region G.
The case more involved since we cannot pack \spheres" as tightly as \hypercubes" without
leaving uncovered points in the region G, if no intersection of disks is allowed. Without loss of generality,
assume that we are covering the neighborhood of a disk D centered at the origin. Any given point
can be represented by ('; ), where 0  '  1 and 0    2 are the radius and angle on the polar axis
coordinates of p, respectively. A set PN(D) is given by the points with polar coordinates (0; 0), (
6 ), as shown. (If we assume that point q represents the origin
in

Figure

1-(a), then PN(D) is given by the points q,r,s,t,u,v and w.) Consider the sector 0
For the other sectors, analogous arguments apply after a rotation. Let 1, be a point
in G such that 0    . If '  1=2, then p is covered by D. The boundary of the unit-disk centered at
intersects the boundary of region G at points (1; 0) and (1; ). It also intersects the boundary of
D at points ( 1
is located in the unit-disk centered at (
The perimeter of the boundary of region G is 2, and one unit-disk can cover at most of this
perimeter. Thus we need at least six unit-disks to cover the boundary of G | i.e., seven is the minimum
number of unit-disks covering the entire region G. Hence N(2; 7.

Figure

1-(a) shows an optimal seven-disk covering with disks centered at q,r,s,t,u,v and w, for the
region G under L 2 norm in < 2 . If is the center of the unit-disk D, the Cartesian coordinates
of the six other points are (x  3
For L 2 norm in < 3 , we were only able to place an upper bound on the number of unit-disks needed
to cover a disk of diameter 2, hence placing an upper bound on N(3; 2). A simple argument [22] su-ces
to verify that 20 unit-disks centered at some evenly spaced points on the surface of G plus a unit-disk
D centered at the origin cover a disk G of diameter two also centered at the origin. Hence we have
It remains an open problem to compute the exact value of N(3; 2). The neighborhood
piercing number for L 2 is closely related to the sphere packing and sphere covering problems described
in [8].
When compared to the results in the literature, the approximation factors based on the neighborhood
piercing points are not the best known. For example, we have shown that N(1; which leads to a
two-approximation algorithm for piercing unit-intervals on the line (see Section 5). In [16, p. 193] (see
also [25]), an exact solution (i.e., one-approximation) for piercing unit-intervals is proposed. The idea
there, shown in Figure 2, is to start from the rightmost interval D, where only one endpoint of D | the
left endpoint l | is enough for piercing all neighbors of D (since D has no neighbor to its right). In order
to be able to extend and generalize this idea to other norms and higher dimensions, we need to dene,
the halfspace of a disk D with orientation ~n, denoted by HD (~n): HD
0g.
For the one-dimensional case, all of the centers of the neighboring disks of the rightmost interval D are
located in the half space HD ( 1) (to the \left" of D), and only half of the neighborhood piercing points
(i.e., only N(1)=2 points) are enough for piercing N (D). More generally, in any d-dimensional space,
there exists an orientation ~n, such that we need roughly half of the neighborhood piercing points to pierce
all the neighbors of disk D located in HD (~n). The minimum number of piercing points needed for the
halfspace HD (~n), over all possible orientations ~n, is called the halfspace neighborhood piercing number,
and is denoted by N . The set of corresponding piercing points are called the halfspace neighborhood
piercing points of D and are denoted by PN(D).
If PN(D) is symmetric with respect to the center of the unit-disk D, then
e if the center of
D does not belong to PN , or
otherwise. Note that this is the case for PN(d; 1), PN(d;1)
and PN(2; 2). The set of piercing points which correspond to the upper bound of 21 for N(3; 2) is not
symmetric, but we can still nd an orientation such that 11 points are enough to pierce the halfspace
neighborhood of a disk with respect to the orientation. Figure 1-(b) illustrates halfspace neighborhood
piercing points | points q,r,s and t | for < 2 under L 2 norm. The orientation considered is
(0; 1).

Table

3 summarizes some values of neighborhood piercing number and that on halfspace for lower
dimensions and norms L 1 ; L1 and L 2 , where we denote the minimum of N(~n) as N and corresponding
PN(~n) as PN . It follows from the upper bound on N(3; 2) that N  11 for L 2 and < 3 . The corresponding
halfspace neighborhood piercing points are also a subset of the points used for establishing the upper
bound on N(3; 2). It also remains an open question to determine the exact value of N for L 2 and < 3 .
For an orientation ~n, if we order all unit-disks D in D according to the values ~q(D)  ~n, then a
unit-disk D bearing the smallest ~q(D)  ~n value satises the property that all its neighbors are located
in the halfspace HD (~n). Thus, by carefully choosing the order in which we consider the neighborhoods
of disks to be pierced, we can use the halfspace neighborhood piercing points as the basis of the fully-distributed
algorithms for the MPS problem presented in Section 4, which match or improve the best
known approximation factors of the respective centralized algorithms.
The problem of computing N for other L p metrics is more involved and may not have many practical
applications. A method to estimate an upper bound on N and compute the corresponding set of
neighborhood piercing points for arbitrary L p metrics is discussed in [22] for completeness.
4 Better Approximation Factors
In this section we present a family of constant-factor fully-distributed (decentralized) approximation
algorithms for the piercing set problem, which at least match the best known approximation factors of
centralized algorithms for the respective norms and dimensions. This algorithm introduces some basic
concepts which will be useful when developing the algorithms in Section 5. Also, the algorithm presented
in this section directly translates into an alternative to the lowest-id clustering algorithm for ad-hoc
networks (discussed in Section which achieves a better approximation factor on the number of clusters
maintained. The algorithms in this section all follow a general algorithmic framework, which we call the
A-algorithm (for having better approximation factors) in contrast with the slightly looser approximation
factors of the other family of algorithms presented in Section 5 (represented by the M-algorithm) which
can better handle mobility.
Consider a set of unit-disks in a d-dimensional space under norm L p . As shown in Section 3, we need
at most N piercing points to pierce the neighborhood of a unit-disk D bearing the smallest ~q(D) ~n among
the (unpierced) disks in its neighborhood, where ~n is an orientation that gives N . We call such a disk
D a top disk. Thus, at each step of the algorithm, each top unpierced disk D elects itself as a piercing
disk and selects the points in PN(D) as piercing points. Since all the unpierced disks in N (D) are now
pierced by PN(D), we mark all the unpierced disks in N (D) as pierced, and repeat the procedure above.
After repeating this step for at most jP  j times, all the unit-disks in D are pierced and a piercing set
with cardinality at most N times jP  j is produced, as shown in Theorem 1. Provided that broadcasting
has O(1) cost, the running time of the distributed A-algorithm is O(jP  j). Theorem 1 states the main
properties of the A-algorithm. This theorem actually extends the results in [25] and in [30] | for L 1 and
L1 norms in d-dimensional spaces | to a more general distributed scenario, and also to the L 2 norm in
two- and three-dimensional space.
We re-invoke the A-algorithm to maintain the piercing set every time an event (as dened in Section
happens. In a distributed scenario, this can be done by
ooding a reset message to unpierce all
disks. Thus the update cost of the A-algorithm is also O(jP  j).
Theorem 1 The approximation factor of the distributed A-algorithm is N , and its setup and update
costs are both O(jP  j).
Proof: For each piercing unit-disk D, we need at least one point in the minimum piercing set P  to
pierce D. For any two distinct piercing unit-disks D and E, the point in P  that pierces D cannot pierce
since no two (distinct) piercing disks intersect. Thus we have at most jP  j piercing unit-disks. For
each piercing unit-disk, we select N piercing points. Hence the approximation factor follows. It takes
constant time to pierce the neighborhood of each piercing unit-disk using a broadcast operation. Hence
the running time for both setup and update operations is O(jP  j).
5 Better Handling of Mobility
We now present the M-algorithm, a fully distributed constant approximation algorithm for the mobile
piercing set problem that adapts optimally to the mobility of disks: The update cost of the M-algorithm is
O(1). We break the M-algorithm into two parts: the M-Setup algorithm, which builds an initial piercing
set, and the M-Update algorithm, which is in charge of adapting the piercing set maintained in response to
the mobility of disks (we will see later that the M-Update algorithm may initiate a local call to M-Setup
as a subroutine at some of the disks). The M-algorithm is more suitable for highly dynamic ad-hoc mobile
network scenarios.
The key idea behind the M-algorithm is to break the sequential running fashion of the A-algorithm.
In the A-algorithm, an ordering of the unit-disks is mandatory (even if implicitly). As shown in Figure 3,
in the worst-case, the movement of one disk (the rightmost one in the gure) could lead to a global
update of all selected piercing disks, while the cardinality of the minimum piercing set does not change.
In order to maintain a relatively stable piercing set, the desired algorithm needs to be able to sever this
\cascading eect" | i.e., the algorithm needs to be able to keep the updates local. Lemma 2 shows
that the cardinality of an optimal piercing set cannot change by much, due to the movement of a single
disk. This property suggests that an update can be kept local. The proof of this lemma, while trivial, is
presented here for completeness.
Lemma 2 If at one time only one unit-disk moves, then jjP  j jP  jj  1, where P  denotes a minimum
piercing set before the movement, and P  denotes a minimum piercing set after the movement.
Proof: If the cardinality of the minimum piercing set changes, then it can either increase or decrease.
Since the reverse of a movement that increases the cardinality of the minimum piercing set is a movement
that decreases it, we only need to show that the cardinality of the minimum piercing set cannot be
increased by more than 1. Let D be the moving disk. Since only D moves, D is the only disk which may
become unpierced. Let piercing set after the movement. Let P  be a
minimum piercing set after the movement of D, jP  j  jP 1. Hence jjP  j jP  jj  1.
In the M-Setup algorithm, instead of choosing a disk with respect to the ordering given by a direction
~n, we select arbitrary unpierced disks as piercing disks in each step, then pierce the neighborhood of each
selected disk D using the points in PN(D). By repeating this procedure O(jP  times, we will generate
a piercing set for D: Since now we use N points to pierce the neighborhood of each selected piercing disk,
the approximation factor is roughly doubled compared to that of the A-algorithm. However, this small
degradation in the approximation factor pays for an optimal update strategy, as will be shown later.
In order to implement the above idea in a distributed fashion, we repeat the following procedure. Each
disk D rst checks if there are any piercing disks in its neighborhood. If so, then D marks itself as pierced.
Otherwise, each unpierced disk tries to become a piercing disk itself. In order to guarantee that only one
disk becomes a piercing disk in an unpierced disk's neighborhood | this is a key property for proving the
approximation factor of this algorithm | a mechanism such as \lowest labeled neighbor wins" (assuming
that each disk has a unique identication label) is required. Note that, unlike the A-algorithm, in the
M-Setup algorithm disks do not need to know the disks' coordinates (since no comparisons of the ~q(D)  ~n
values are required), which may be desirable in an ad-hoc network scenario. The proof of Theorem 2 is
analog to that of Theorem 1, and is therefore omitted.
Theorem 2 The M-Setup generates a piercing set of cardinality within a factor of N of jP  j in O(jP
time.
As disks start moving in space, each disk needs to be able to trigger an update procedure whenever
an update is necessary. To facilitate the following discussion, we call a disk that is not a piercing disk
a normal disk. When a disk moves, the following events may make the current piercing set invalid
and trigger an update: (i) the boundaries of two piercing disks D and E meet (thus D may become a
redundant piercing disk); (ii) the boundaries of one piercing disk D and some normal disk D 0 pierced by
separate (thus at least one of the disks becomes unpierced). An M-Update procedure is initiated at
disk D in events of type (i), or at disks D and D 0 for events of type (ii). The M-Update procedure can
be divided into two phases: In the rst phase, we will unmark some of the disks as to be now unpierced;
in the second phase, we select piercing disks for those unpierced disks. The second phase is executed by
a local call to M-Setup initiated at each unpierced disk.
The details of the M-Update procedure are as follows. If we have an event of type (i), the M-Update
will degrade disk D to a normal disk and unpierce all disks that were currently pierced by D (including
D itself). Otherwise, if case (ii) applies, the M-Update will simply unpierce disk D 0 . Each node that
is marked unpierced by the M-Update procedure will invoke M-Setup locally. The M-Setup procedure
invoked at an unpierced disk F will rst check if any of its neighbors is a piercing disk. If so, it marks
itself pierced. Otherwise, if F has the lowest label among its unpierced neighbors, it elects itself as a
piercing disk and marks all its unpierced neighbors as pierced. The M-Setup and M-Update algorithms
are shown in Figure 4.
As proven in Theorem 3, all unit-disks will be pierced at the end of the calls to M-Setup, and the
approximation factor on the size of the piercing set maintained is still guaranteed to be N .
Theorem 3 The M-Update procedure maintains an N-approximation of the MPS, with update cost of
O(1) for each event.
Proof: First we show that the running time of M-Update is constant per event. Assume that at one
time only one event occurs. All the disks possibly aected by the event are located in the neighborhood
of a disk D. Thus the operation of marking disks as unpierced (in the rst phase) takes constant time.
Since all nodes that invoked a call to M-Setup were neighbors of a former piercing disk D, it follows
that the calls to M-Setup will have at most a constant number, N , of rounds of \lowest labeled neighbor
wins" until a valid set of piercing disks is restored. Therefore the total time taken by each of the invoked
M-Setup calls also takes constant time. If several events occur at the same time, then the nal eect is
the same as if a sequence of events occurs in a row, and the update cost per event remains the same.
Now we show that the approximation factor maintained is equal to N . Clearly the resulting piercing
set is determined by the collection of selected piercing unit-disks. We will show that the updated collection
of piercing disks produced by the M-Update procedure could have been the initial collection of piercing
disks produced by the M-Setup algorithm (for a given ordering of the labels of the disks), thus proving
the claimed approximation factor. Assume that the collection of selected piercing
unit-disks before the call to M-Update is invoked is an N-approximation on the MPS. Let E 0 be the
collection of selected piercing unit-disks after the call to M-Update is completed at all nodes (which may
involve calling the M-Setup algorithm locally). One of the following four cases may occur:
Case 1. A normal unit-disk D 0 moves and after the movement, it is still pierced by some piercing unit-
disk in E. In this case, the M-Update procedure never invokes M-Setup at a node, and
still need at least one piercing point to pierce each of the selected piercing disks (no two piercing disks
overlap) and since E was an N-approximation of the MPS, the approximation factor still holds.
Case 2. A normal unit-disk D 0 moves, and after the movement, D 0 is no longer pierced by a piercing
unit-disk in E. In this case, the M-Setup procedure invoked by the call to M-Update will upgrade D 0 to
a piercing disk. Thus g.
We prove the bound on the size of the piercing set maintained by showing that E 0 could have been
obtained by a general call to the M-Setup algorithm to the current conguration (placement in space) of
the disks if all disks were currently unpierced, for a given assignment of labels to the disks. Suppose that
the labels of the disks in E 0 are smaller than the labels of all other disks in D, and that label(D 1
Thus, on or before step i  m, disk D i will be selected by M-Setup to become
a piercing disk (since all D i 's were unpierced disks in E initially, and no two piercing disks intersect).
After all disks D are selected, only disk D 0 is not pierced. Thus M-Setup must select D 0 to be
a piercing disk. Hence E 0 is obtained, proving the N-approximation factor on the cardinality of the set
of piercing points produced.
Case 3. A piercing unit-disk D moves and after the movement, D is pierced by some other piercing
. The M-Update will degrade D to a normal disk and
unpierce all unit-disks previously pierced by D. The M-Update procedure then invokes local calls to
M-Setup at all unpierced disks. For each unit-disk D 0 previously pierced by D, M-Setup will rst check
if there is another piercing disk that pierces D 0 . If so, D 0 will be marked pierced. Otherwise, if there
are neighbors of D which still remain unpierced, then the M-Setup algorithm will upgrade some normal
disks to piercing disks. Let E be the collection of those upgraded piercing disks.
Then we have as the new set of piercing disks. As in Case 2, if label(D 1 ) <
disks E not in E 0 , the M-Setup
algorithm when applied to the current conguration of the disks in D, assuming all disks are unpierced
at start, will produce E 0 as the resulting set of piercing disks. Thus the N-approximation factor follows.
Case 4. A piercing unit-disk D moves and after the movement, D is not pierced by any other piercing
Essentially the same as Case 3, but for the fact that we do not degrade D to a normal
disk.
A simple extension of the M-algorithm provides a polylog approximation algorithm for the nonuniform
case. If the collection contains disks of various radii, then we can guarantee an N-approximation if at
each step we nd the unpierced disk of smallest radii in the collection and pierce all of its neighborhood.
However, we cannot guarantee having O(1) update cost in this case. Without loss of generality, assume
that the minimum radius of a disk is equal to 1. If the largest disk radius is bounded by a polynomial on
then we have the following Corollary:
Corollary 1 By grouping the disks into O(log n) classes such that each class contains disks of radii in
have an O(log n) approximation for the MPS problem on nonuniform disks with distributed
update cost of O(1).
Proof: In each class, as we show below, N 2 points are enough to pierce an arbitrary neighborhood.
Since we have O(log n) classes, and the piercing set for each class is a N 2 -approximation of the overall
minimum piercing set, the approximation factor is bounded by O(log n). Once a disk moves, it only
aects the piercing set selected for one class, thus the update cost is still constant. We now show that
points are in fact enough for covering a disk of diameter 2 i+2 , using disks of diameter in [2 In
the worst case, we need to cover a region of diameter 2 i+2 with disks of diameter 2 i . We can do this in
two phases. First we cover the region using N disks of diameter 2 i+1 . Then for each disk D of diameter
using N disks of diameter 2 i .
6 Applications to Clustering in Mobile Networks
For the ad-hoc network scenario described in the introduction, where all nodes have equal range of
communication, the algorithms proposed for the mobile piercing set problem can be directly applied in
order to obtain a one-hop clustering of the network. A clustering of a network G is a partition of the
nodes of G into subsets (clusters) C i , where for each C i , we elect a node v 2 C i as its clusterhead. A
one-hop clustering of G is a clustering of G such that every node in the network can communicate in
one-hop with the clusterhead of the cluster it belongs to. We can view the network G as a collection of
unit-disks in < 2 (resp., < 3 ) under L 2 (as discussed in the introduction).
The algorithm in Section 5 can be used to obtain an almost optimal (with respect to number of clusters)
one-hop clustering of a wireless network where all nodes have equal communication range. We have that
is a lower bound on the minimum number of 1-hop
clusters (and therefore on the number of selected clusterheads) needed to cover the entire network, since
we need at least one clusterhead for each neighborhood of a piercing disk (the clusterhead centered at
the center of the respective piercing disk can communicate with all disks in the neighborhood), and since
we use at most seven (resp., 21) piercing points for each of these neighborhoods in a minimum piercing
set in < 2 (resp., < 3 ). The number of piercing disks selected by the algorithm in Section 5 is at most jP  j.
Since each of these piercing disks D corresponds uniquely to a one-hop cluster C in the network (given
by all the disks pierced by D), and since the union of all these clusters covers the entire network, we have
that the number of clusters is at most jP  j, which is a seven-approximation (resp., 21-approximation) on
the minimum number of one-hop clusters needed in < 2 (resp., < 3 ). This algorithm is also suitable for
maintaining such an optimal structure as nodes start moving in space, with optimal update costs. The
algorithm tends to keep the number of changes in the set of selected clusterheads low.
In fact, the algorithm presented in Section 5, when translated to a clustering algorithm on ad-hoc
networks, is essentially the same as the Least Cluster Change (LCC) algorithm presented by Chiang et
al. [7]. Therefore, in this paper we provide a theoretical analysis of the performance of this popular
clustering algorithm, validating the simulation results that showed that the clusters maintained by this
algorithm are relatively stable. More specically, we have proved that this algorithm sustains a seven-
approximation on the number of one-hop clusters maintained, while incurring optimal setup and update
costs.
A closer look at the lowest-id algorithm, investigated by Gerla and Tsai in [15], shows that this
algorithm corresponds to several applications of the M-Setup procedure of Section 5. Every time a disk
becomes unpierced, or two piercing disks intersect, the lowest-id algorithm starts updating the clustering
cover maintained in a fashion that may correspond to an application of the M-Setup algorithm on the
current conguration of the disks if all disks were unpierced | in the worst-case, the lowest-id algorithm
may generate a \cascading eect" which correspond to an application of the M-Setup algorithm on a
collection of all unpierced disks, if the disk labels are given by the node ids. Thus the setup and the
worst-case update costs of the lowest-id algorithm are both O(jP  j), and the approximation on the number
of clusters maintained is equal to seven and 21, for < 2 and < 3 respectively.
7 Future work
There are many natural extensions of the work in this paper. We would like to extend the one-hop
clustering structure to a full network clustering hierarchy. One idea would be to apply the same algorithm
presented to construct O(log n) clustering covers of the network: Clustering i would be obtained by
assuming that all disks have radius equal to 2 i , for One problem with
this strategy is that by articially increasing the communication ranges on the nodes in the network (radii
of the disks), a resulting cluster in the hierarchy may not even be connected. Other directions for future
work are (i) to develop constant approximation algorithms for piercing a collection of disks of dierent
radii; (ii) to extend any results on nonuniform radius disks to ad-hoc network clustering | note that if
we have nonuniform radius disks, we can no longer guarantee symmetric communication between nodes
in the network; and (iii) to determine the exact neighborhood piercing number for L 2 norm in three- (or
higher) dimensional spaces.

Acknowledgment

We would like to express our thanks to Martin Ziegler for valuable discussions on estimating N(3; 2).



--R

Exact and approximation algorithms for clustering.

Distributed and mobility-adaptive clustering for multimedia support in multi-hop wireless networks
Distributed clustering for ad-hoc networks
Data structures for mobile data.
Mobile facility location.
Routing in clustered multihop
Sphere packings

Dynamic data structures for fat objects and their applications.
Optimal algorithms for approximate clustering.
Optimal packing and covering in the plane are NP-complete
Generalized selection and ranking: sorted matrices.
Discrete mobile centers.
Multicluster mobile multimedia radio networks.
Algorithmic Graph Theory.
Covering a set of points in multidimensional space.
Clustering motion.
Approximation schemes for covering and packing problems in image processing and vlsi.
A best possible heuristic for the k-center problem

Approximation algorithms for the mobile piercing set problem with applications to clustering.
The generalized searching over separators strategy to solve some np-hard problems in subexponential time
The slab dividing approach to solve the euclidean p-center problem
Maintenance of a piercing set for intervals with applications.
An optimal approximation algorithm for the rectilinear m-center problem
Adaptive clustering for mobile wireless networks.
A mobility-based framework for adaptive clustering in wireless ad-hoc networks
On the complexity of some common geometric location problems.
Fast stabbing of boxes in high dimensions.
Hierarchically-organized, multihop mobile wireless for quality- of-service support

--TR
A unified approach to approximation algorithms for bottleneck problems
Sphere-packings, lattices, and groups
Optimal algorithms for approximate clustering
generalized selection and ranking: sorted matrices
Approximation algorithms for hitting objects with straight lines
Approximation schemes for covering and packing problems in image processing and VLSI
Rectilinear and polygonal <italic>p</italic>-piercing and <italic>p</italic>-center problems
Multicluster, mobile, multimedia radio network
Hierarchically-organized, multihop mobile wireless networks for quality-of-service support
Efficient algorithms for geometric optimization
Data structures for mobile data
Exact and approximation algorithms for clustering
Mobile facility location (extended abstract)
Discrete mobile centers
Dynamic Data Structures for Fat Objects and Their Applications
Maintenance of a Percing Set for Intervals with Applications
Fast Stabbing of Boxes in High Dimensions
Distributed Clustering for Ad Hoc Networks
Clustering Motion

--CTR
Fabian Kuhn , Aaron Zollinger, Ad-hoc networks beyond unit disk graphs, Proceedings of the joint workshop on Foundations of mobile computing, p.69-78, September 19, 2003, San Diego, CA, USA
clustering;mobile ad-hoc networks;approximation algorithms;piercing set;distributed protocols