# Online Dominating Set and Independent Set

Minati De  Dept. of Mathematics, Indian Institute of Technology Delhi, New
Delhi, India-110016
<EMAIL_ADDRESS><EMAIL_ADDRESS>Sambhav Khurana  Dept. of Mathematics, Indian Institute of Technology Delhi,
New Delhi, India-110016
<EMAIL_ADDRESS><EMAIL_ADDRESS>Satyam
Singh  Dept. of Mathematics, Indian Institute of Technology Delhi, New Delhi,
India-110016
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Finding minimum dominating set and maximum independent set for graphs in the
classical online setup are notorious due to their disastrous $\Omega(n)$ lower
bound of the competitive ratio that even holds for interval graphs, where $n$
is the number of vertices. In this paper, inspired by Newton number, first, we
introduce the independent kissing number $\zeta$ of a graph. We prove that the
well known online greedy algorithm for dominating set achieves optimal
competitive ratio $\zeta$ for any graph. We show that the same greedy
algorithm achieves optimal competitive ratio $\zeta$ for online maximum
independent set of a class of graphs with independent kissing number $\zeta$.
For minimum connected dominating set problem, we prove that online greedy
algorithm achieves an asymptotic competitive ratio of $2(\zeta-1)$, whereas
for a family of translated convex objects the lower bound is
$\frac{2\zeta-1}{3}$. Finally, we study the value of $\zeta$ for some specific
families of geometric objects: fixed and arbitrary oriented unit hyper-cubes
in $\mathbb{R}^{d}$, congruent balls in $\mathbb{R}^{3}$, fixed oriented unit
triangles, fixed and arbitrary oriented regular polygons in $\mathbb{R}^{2}$.
For each of these families, we also present lower bounds of the minimum
connected dominating set problem.

Keywords: independent kissing number, competitive ratio, dominating set,
geometric intersection graph, independent set, online algorithm.

##  1 Introduction

In this paper, we have considered online versions of some well known NP-hard
problems on graphs. For a graph $G=(V,E)$, a subset $D$ of $V$ is a
_dominating set_ (DS) if each vertex $v\in V$ is either in $D$ or it is
adjacent to some vertex in $D$. The _minimum dominating set_ (MDS) problem
involves finding a dominating set of $G$ that has minimum number of vertices.
A dominating set $D$ is said to be a _connected dominating set_ (CDS) if the
induced subgraph $G[D]$ is connected (if $G$ is not connected then $G[D]$ must
be connected for each connected component of $G$). A dominating set $D$ is
said to be an _independent dominating set_ (IDS) if the induced subgraph
$G[D]$ is an independent set. Note that an _independent set_ (IS) of a graph
$G(V,E)$ is a subset $I\subseteq V$ such that no two vertices of $I$ are
adjacent to each other. The _maximum independent set_ (MIS) problem is to find
an independent set with maximum number of vertices.

Apart from theoretical implications, there are several applications of these
problems. For example, a DS can be thought of as transmitting stations that
can transmit messages to all stations in the network [25]. A CDS is often used
as the virtual backbone in a network where nodes in the CDS are responsible to
relay messages [12, 16]. A relevant issue arises regarding the maintenance of
the DS or CDS as the network topology changes with time. On the other hand,
the IS plays a vital role in resource scheduling [17]. Requests for resources
or sets of resources arrive online, and two requests can only be serviced
simultaneously if they do not involve the same resource.

Online computation models the real world phenomena: irreversibility of time
(or decisions) and uncertainty of future (or order of input). As a result,
online models of computation get a considerable amount of attention in recent
time. In the classical online setting for graph problems, the graph is
revealed vertex by vertex, together with edges to all previously revealed
vertices. One needs to maintain a feasible solution for the revealed vertices,
and need to make a decision whether to include the newly revealed vertex into
the solution set. The decision to include a vertex in the solution set can not
be changed later. Unfortunately, in this classical online model, for both MDS
and MIS problems, the competitive ratio has a lower bound of $\Omega(n)$ that
holds even for interval graphs, where $n$ is the number of vertices revealed
to the algorithm [19, 24]. Due to this hopeless lower bound, the literature on
these problems in the classical online model is rather scarce in comparison
with scheduling, routing, and packing problems. In order to obtain meaningful
results, one often needs to restrict inputs to a special class of graphs or
change the model of computation.

In this paper, we have considered geometric intersection graphs. They have
various practical applications in wireless sensors and network routing [8,
18]. For a family ${\cal S}$ of geometric objects in $\mathbb{R}^{d}$, the
geometric intersection graph $G$ of ${\cal S}$ is an undirected graph with set
of vertices same as ${\cal S}$ and the set of edges is defined as
$E=\\{(u,v)|u,v\in{\cal S},u\cap v\neq\emptyset\\}$. For example, if $\cal S$
is a family of disks then the corresponding graph is known to be a disk graph.

###  1.1 Model of computation

Similar to Boyar et al. [4], we consider vertex arrival model. In the context
of geometric intersection graphs, the input objects are not known apriori,
rather they are revealed one by one in discrete time steps. An online
algorithm needs to take irrevocable decision after each time step without
knowing the future part of the input, it needs to maintain a valid dominating
set. As in [11], in case of CDS, not only the newly revealed object, the
online algorithm can add any previously seen objects to the existing solution
set to make the graph connected. We analyze the quality of our online
algorithm by competitive analysis [2], where competitive ratio is the measure
of comparison. In the following we have defined competitive ratio with respect
to a minimization problem. For a maximization problem, one can define it in a
similar way. An online algorithm $ALG$ for a minimization problem is said to
be _$\alpha$ -competitive_, if there exists a constant $\beta$ such that for
any input sequence $\sigma$, we have
$|ALG_{\sigma}|\leq\alpha\times|OPT_{\sigma}|+\beta$, where $ALG_{\sigma}$ and
$OPT_{\sigma}$ are the cost of the solution produced by the algorithm $ALG$
and an optimal offline algorithm, respectively. The smallest $\alpha$ for
which $ALG$ is $\alpha$-competitive is known as _asymptotic competitive ratio_
of $ALG$. The smallest $\alpha$ for which $ALG$ is $\alpha$-competitive with
$\beta$= $0$ is called the _absolute competitive ratio_ of $ALG$ [7].
Throughout the paper, if not mentioned explicitly, by competitive ratio we
mean absolute competitive ratio.

###  1.2 Related Works

The dominating set and its variants are well studied in the offline setup for
graphs as well as geometric objects. Finding MDS is already known to be NP-
hard [14, 23] in the offline setup even for unit disks and unit squares.
Polynomial time approximation scheme (PTAS) is known when the objects are
homothets of a convex objects [9]. King and Tzeng [19] initiated the study in
the context of online version for MDS. They showed that for general graph, the
greedy algorithm achieves a competitive ratio of $n-1$, which is also tight
bound achievable by any online algorithm for the MDS problem, where $n$ is the
number of vertices of graph. Even for interval graph, the lower bound of the
competitive ratio is $n-1$ and the simple greedy algorithm achieves this bound
[19]. Eidenbenz [11] and Boyar et al. [4] studied DS, CDS and IDS for specific
graph classes: trees, bipartite graphs, bounded degree graphs, planar graphs.
Their results are summarized in Table 2 of [4]. For tree, Eidenbenz [11] and
Boyar et al. [4] gave an upper bound on the competitive ratio as three for
MDS. Later, Kobayashi [21] proved that three is also the lower bound for tree.
Eidenbenz [11] proved that greedy algorithm achieves the tight bound of five
for MDS of unit disk graph. For CDS, they showed that greedy algorithm
achieves competitive ratio of $8+\epsilon$ whereas the lower bound is $10/3$.
In this paper, we have studied the performance of the greedy algorithm for
other geometric intersection graphs.

The maximum independent set problem is also an NP-hard problem even for graphs
with bounded degree 3 [1]. In the geometric setup, when the objects are pseudo
disks PTAS is known due to Chan and Har-Peled [6]. The study of online
versions of IS was initiated due to scheduling of intervals [24]. In the
classical online setup, even for interval graphs, it is known that no
algorithm can achieve a competitive ratio better that $n-1$, where $n$ is the
number of nodes [15, 24]. As a result, researchers have studied this problem
in several other variants of online models. Halldorsson et al. [17] studied
the MIS problem for graphs in two different models. In the first model, the
algorithm can maintain a multiple number $r(n)$ of solutions and choose the
largest one as the final one, where $n$ is the number of vertices. They proved
that the best competitive ratio for this model is $\theta(\frac{n}{logn})$
when $r(n)$ is a polynomial, and $\theta(n)$ when $r(n)$ is a constant. Then
they introduced a more powerful model where the algorithm can copy
intermediate solutions and extend the copied solutions in different ways. In
this model, they showed that the problem attains an upper bound
$O(\frac{n}{logn})$ and a lower bound $\Omega(\frac{n}{log^{3}n})$ when $r(n)$
is a polynomial, and it achieves a tight bound of $\theta(n)$ when $r(n)$ is a
constant. Due to the devastating lower bound of $\Omega(n)$ in the worst case
analysis, Göbel et al. [15] studied the online independent set via stochastic
analysis. With stochastic analysis, they proved that graphs, with bounded
inductive independence number $\rho$, has competitive ratio $4c^{3}\rho^{2}$,
where $c\geq 1$. Note that the inductive independence number for geometric
intersection graph of translates of a convex object in $\mathbb{R}^{2}$ is $3$
[28]. Ye and Borodin [28] conjectured that the inductive independence number
is $5$ for geometric intersection graph of translates of a convex object in
$\mathbb{R}^{3}$. Therefore, the result in [15] is at least $36$ and $100$
competitive for translates of a convex object in $\mathbb{R}^{2}$ and
$\mathbb{R}^{3}$, respectively. Göbel et al. [15] also studied the weighted
version of the MIS problem and proved using stochastic analysis that one can
achieve $O(\rho^{2}\log n)$ competitive ratio, whereas they have proved that
the lower bound of the problem is $\Omega(\frac{\log^{2}\log n}{\log n})$ even
for weighted interval graphs. In this paper, we have studied the worst case
analysis of the MIS problem for geometric intersection graphs in the classical
online model.

###  1.3 Notation and Preliminaries

We use $[n]$ to denote the set $\\{1,2,\ldots,n\\}$. We use $\mathbb{Z}_{n}$
to denote the set $\\{0,1,\ldots,n-1\\}$ of non-negative integers less than
$n$, where the arithmetic operations such as addition, subtraction and
multiplication are modulo $n$. By a _geometric object_ , we refer to a compact
convex set in $\mathbb{R}^{d}$ with non-empty interior. The _center_ of a
geometric object is defined as the centre of the smallest radius ball
inscribing that geometric object. The _neighbourhood_ $N(u)$ of a geometric
object $u$, belonging to a family $\cal S$ of geometric objects, is defined as
the region that contains all the centers of objects of $\cal S$ that touch or
intersect $u$. A geometric object whose center lies in $N(u)$ is referred as a
_neighbour_ of $u$. Two objects are _congruent_ if one can be transformed into
the other by a combination of rigid motions, namely a translation, a rotation,
and a reflection. Two geometric objects are said to be _non-overlapping_ if
they have no common interior, whereas we call them _non-touching_ if their
intersection is empty. For a convex object $u\subset\mathbb{R}^{d}$, _Newton
number_ (a.k.a. _Kissing number_), denoted as $K(u)$, is the maximum number of
non-overlapping congruent copies of $u$ that can be arranged around $u$ so
that each of them touches $u$ [10, 5]. Some known bounds are as follows:
$K(P_{3})=12,K(P_{4})=8$ and $K(P_{n})=5$, where $P_{n}$ is a regular polygon
with $n\geq 5$ [31]; $K(B_{2})=6$, $K(B_{3})=12$, where $B_{2}$ and $B_{3}$
are balls in $\mathbb{R}^{2}$ and $\mathbb{R}^{3}$, respectively [5, 10, 22,
26]. The kissing number for hyper-cubes is at least $3^{d}-1$, and whether
this bound is sharp or not is still not settled. Throughout the paper, we have
used $opt_{cds}$ to denote the size of the optimal connected dominating set in
the offline setup.

| $K(U)$ |  |  $\zeta$, DS, IDS, IS | CDS
---|---|---|---|---
Types of Geometric Objects |  Bounds |  Previously known upper bound for IS $4c^{3}\rho^{2\$}$ [15] |  Bounds |  Asymptotic competitive ratio of $GCDS$ |  Lower Bound when ${}^{*}opt_{cds}=1$ |  Lower Bound otherwise
Fixed oriented unit squares |  $8$ [29] |  $36c^{3}$ [15, 28] |  $4$ |  $6$ |  $6$ |  $\frac{7}{3}$
Fixed oriented unit hyper-cubes in $\mathbb{R}^{d}$ |  ($3^{d}-1$,-) |  $4c^{3}(2d-1)^{2\\#}$ [15, 28] |  $2^{d}$ |  ($2^{d+1}-2$) |  $7.2^{d-2}-1$ |  $\frac{7.2^{d-2}}{3}$
Arbitrary oriented unit squares |  $8$ [29] |  $\\_\\_$ |  $\\{6,7\\}$ |  $12$ |  $10$ |  $\frac{11}{3}$
Arbitrary oriented unit hyper-cubes in $\mathbb{R}^{d}$ |  $(3^{d}-1$,-) |  $\\_\\_$ |  $[3.2^{d-1}$,-) |  __ |  $11.2^{d-2}-1$ |  $\frac{11.2^{d-2}}{3}$
Unit disks |  $6$ [5, 31] |  $36c^{3}$ [15, 28] |  $5$ [11] |  $6.906$ [11, 13] |  $8$ |  $3$ [11]
Unit balls |  $12$ [5] |  $100c^{3\\#}$ [15, 28] |  $12$ |  $22$ |  $17$ |  $6$
Fixed oriented unit triangles |  __ |  $36c^{3}$ [15, 28] |  $\\{5,6\\}$ |  $10$ |  $9$ |  $\frac{10}{3}$
Regular $k$-gons (fixed oriented) |  $6$ [31] |  $36c^{3}$ [15, 28] |  $\\{5,6\\}$ |  $10$ |  $8$ |  $3$
Arbitrary oriented Regular $k$-gons ($5\leq k\leq 10$) |  $6$ [31] |  __ |  $6$ |  $10$ |  10 |  $\frac{11}{3}$

$ $c\geq 1$ and $\rho$ is inductive independent number.

*$opt_{cds}$ is the size of an optimal solution for CDS in the offline setup.

# Ye and Borodin [28] conjectured that the inductive independent number $\rho$
of translates of a convex object in $\mathbb{R}^{d}$ is $2d-1$.

Table 1:  Summary of Results: previously known results are marked in gray.

###  1.4 Our Contributions

First, similar to the kissing number, we introduce independent kissing number
$\zeta$ (see Definition 1) for a family of geometric objects, as well as for
graphs. Note that for a set of congruent objects, the value of independent
kissing number is bounded from above by its kissing number. The independent
kissing number is a fixed constant for several families of geometric objects:
translated and/or rotated copies of a convex object in $\mathbb{R}^{d}$, fat
objects etc. Of course, the value depends upon $d$.

Next, for any graph with independent kissing number $\zeta$, we prove that the
well known online greedy algorithm for dominating set achieves a competitive
ratio of $\zeta$, and any deterministic online algorithm can achieve a
competitive ratio at most $\zeta$. This implies that the greedy algorithm for
dominating set is optimal for any graph in the classical online setup. Note
that the online algorithm need not know the value of $\zeta$. Since the greedy
algorithm reports independent dominating set, the same result holds for
independent dominating set for geometric intersection graphs in the online
setup.

For the maximum independent set problem, we prove that the same greedy
algorithm achieves an optimal competitive ratio of $\zeta$ for graphs with
independent kissing number $\zeta$. This result improves the best known upper
bound of the problem for several geometric intersection graphs. The comparison
is given in Table 1.

Next, we prove that, for any graph with independent kissing number $\zeta$,
the online greedy algorithm for connected dominating set achieves an
asymptotic competitive ratio at most $2(\zeta-1)$. For a geometric
intersection graph of translated copies of a convex objects in
$\mathbb{R}^{2}$ with independent kissing number $\zeta$, we prove that CDS
has a lower bound of $\frac{2\zeta-1}{3}$.

As a consequence, the independent kissing number $\zeta$ becomes an
interesting parameter of a graph. To get the idea of the value of $\zeta$ for
specific families of geometric objects, we consider fixed oriented unit hyper-
cubes in $\mathbb{R}^{d}$, congruent balls in $\mathbb{R}^{3}$, fixed oriented
unit triangles and regular polygons in $\mathbb{R}^{2}$. We show that the
value of $\zeta$ for fixed oriented unit hyper-cubes in $\mathbb{R}^{d}$ is
$2^{d}$. It happens to be that for congruent balls in $\mathbb{R}^{3}$, the
value of $\zeta$ is 12 which is also same as its kissing number. For both
fixed oriented unit triangles and fixed oriented regular polygons in
$\mathbb{R}^{2}$, we show that $5\leq\zeta\leq 6$. For each of these specific
families, we also study the lower bound of CDS problem. Our results are
summarized in Table 1.

###  1.5 Organization

In Section 2, we introduce the independent kissing number. Next, in Section 3,
we have discussed the performance of well known online greedy algorithms for
MDS, MIS and MCDS problem for graphs with independent kissing number $\zeta$.
Then in Section 4, we propose a lower bound of MCDS problem for translated
copies of a convex object in $\mathbb{R}^{2}$. After that, in Sections 5-9, we
have discussed the value of $\zeta$ and lower bound of MCDS for specific
families of geometric intersection graphs. Finally, in Section 10, we give a
conclusion.

##  2  Independent Kissing Number

First, we introduce _independent kissing number_ $\zeta$ for a family $\cal S$
of geometric objects in $\mathbb{R}^{d}$.

######  Definition 1 (Independent Kissing Number).

Let $\cal S$ be a family of geometric objects, and let $u$ be any object
belonging to the family ${\cal S}$. Let $\zeta_{u}$ be the maximum number of
pairwise non-touching objects in $\cal S$ that can be arranged in and around
$u$ such that all of them are dominated/intersected by $u$. The independent
kissing number $\zeta$ of $\cal S$ is defined to be $\max_{u\in{\cal
S}}\zeta_{u}$.

A set $K$ of objects belonging to the family $\cal S$ is said to form an
_independent kissing configuration_ if (i) there exists an object $u\in K$
that intersects all the objects in $K\setminus\\{u\\}$, and (ii) all the
objects in $K\setminus\\{u\\}$ are mutually non-touching to each other. Here
$u$ and $K\setminus\\{u\\}$ are said to be the _core_ and _independent set_ ,
respectively, of the independent kissing configuration. The configuration is
considered _optimal_ if $|K\setminus\\{u\\}|=\zeta$, where $\zeta$ is the
independent kissing number of $\cal S$. The configuration is said to be
_standard_ if all the objects in $K\setminus\\{u\\}$ are mutually non-
overlapping with $u$, i.e., their common interior is empty but intersection is
non-empty. For illustration, see Figure 1(b).

#### Kissing Number vs Independent Kissing Number

Note that the kissing number is defined mainly for a set of congruent objects.
On the other hand, the independent kissing number is defined for any set of
geometric objects. In kissing configuration, the objects around $u$ are non-
overlapping but they are allowed to touch each other; on the other hand, in
the independent kissing configuration, the objects around $u$ are non-
touching. For more illustration, see Figure 1. For a set of congruent copies
of $u$, it is easy to observe that the value of independent kissing number is
at most $K(u)$, the kissing number of $u$.

(a)

(b)

Figure 1: (a) Optimal kissing configuration, and (b) optimal independent
kissing configuration for unit disks.

#### Graph Theoretic View

Now, we give an alternative definition of independent kissing number in terms
of graph. Let $G=(V,E)$ be a graph. For any vertex $v\in V$, we denote
$N(v)=\\{u(\neq v)\in V|(u,v)\in E\\}$ as the neighbourhood of the vertex $v$.
For any subset $V^{\prime}\subseteq V$, the _induced subgraph_ $G[V^{\prime}]$
is the graph whose vertex set is $V^{\prime}$ and the edge set consists of all
of the edges in $E$ that have both endpoints in $V^{\prime}$. By $\alpha(G)$,
we denote the size of a maximum independent set of a graph $G$. The
independent kissing number $\zeta$ of a graph $G$ is defined as $max_{v\in
V}\\{\alpha(G[N(v)])\\}$.

##  3 Online Greedy Algorithms For Graphs

In this section, we discuss popularly known greedy online algorithms for MDS,
MIS and MCDS for graphs. We show how their performance depend on the
independent kissing number $\zeta$. Note that the algorithms need not know the
value of $\zeta$ in advance.

###  3.1 Greedy Algorithm for Dominating Set ($GDS$)

Suppose that, after observing first $t-1$ vertices, we have a solution set
${\cal A}_{t-1}$. Let $v_{t}$ be a new vertex.

$\bullet$

If $v_{t}$ is dominated by ${\cal A}_{t-1}$, then we set ${\cal A}_{t}={\cal
A}_{t-1}$.

$\bullet$

Otherwise, we will add $v_{t}$ into our solution set by doing ${\cal
A}_{t}={\cal A}_{t-1}\cup\\{v_{t}\\}$.

######  Observation 1.

The set of vertices returned by the $GDS$ algorithm are pairwise non-adjacent.
In other words, the solution set is always an independent set.

As a result of Observation 1, the $GDS$ algorithm achieves the same
competitive ratio for both MDS and MIDS problems.

#### Upper Bound of the Algorithm

Let $G$ be any graph with independent kissing number $\zeta$. Let ${\cal
A}_{t}$ be a set of vertices reported by our $GDS$ algorithm after receiving
first $t$ vertices $v^{t}=\\{v_{1},\ldots,v_{t}\\}$. Similarly, let ${\cal
O}_{t}$ be the set of vertices in the optimum set for $v^{t}$. Since ${\cal
O}_{t}$ also dominates ${\cal A}_{t}$, any vertex $A\in{\cal A}_{t}$ will
either belong to the optimal set ${\cal O}_{t}$ or will be the neighbour of a
vertex in ${\cal O}_{t}$. If ${\cal A}_{t}\cap{\cal O}_{t}\neq\emptyset$, then
remove all the common elements from ${\cal A}_{t}$ and ${\cal O}_{t}$
resulting, ${\cal A}^{\prime}_{t}\cap{\cal O}^{\prime}_{t}=\emptyset$
($\frac{|{\cal A}^{\prime}_{t}|}{|{\cal O}^{\prime}_{t}|}\leq M$ implies
$\frac{|{\cal A}_{t}|}{|{\cal O}_{t}|}\leq M$). Without loss of generality,
assume that ${\cal A}_{t}\cap{\cal O}_{t}=\emptyset$. Thus, each vertex
$A\in{\cal A}_{t}$ will be in the neighbour of at least a vertex in ${\cal
O}_{t}$. Note that all the vertices in ${\cal A}_{t}$ are pairwise non-
adjacent (Due to Observation 1). From the definition of independent kissing
number (Definition 1), we know that each vertex $O\in{\cal O}_{t}$ can have at
most $\zeta$ non-adjacent vertices of ${\cal A}_{t}$ in its neighbourhood.
Therefore, $|{\cal A}_{t}|\leq\zeta|{\cal O}_{t}|$, and our algorithm achieves
a competitive ratio of at most $\zeta$.

#### Lower Bound of the Problem

Let $v_{1},v_{2},\ldots,v_{\zeta}$ & $v_{\zeta+1}$ be the vertices coming one
by one to the online algorithm. Since $\zeta$ is the independent kissing
number of the graph under consideration, with an adaptive deterministic
adversary, we can choose vertices $v_{1},v_{2},\ldots,v_{\zeta}$ such that all
of them are pair-wise non-adjacent and can be dominated by a single vertex
$v_{\zeta+1}$. Thus, any online algorithm will report first $\zeta$ vertices
as dominating set, whereas the optimum dominating set contains only the last
vertex $v_{\zeta+1}$. Thus the lower bound on the competitive ratio for
minimum dominating set is $\zeta$. Therefore, we have the following.

######  Theorem 1.

For a graph $G$ with independent kissing number $\zeta$, the greedy dominating
set ($GDS$) algorithm is optimal and it achieves a competitive ratio of
$\zeta$.

###  3.2 Maximum Independent Set

Recall that the algorithm $GDS$ defined in Section 3.1, produces a dominating
set which is also an independent set for a graph $G$. Here, we prove that
$GDS$ yields a competitive ratio $\zeta$ matching the lower bound for the
maximum independent set problem as well.

######  Theorem 2.

There exists a deterministic online algorithm having competitive ratio at most
$\zeta$ for maximum independent set of a graph $G$ with independent kissing
number $\zeta$. This result is tight: the competitive ratio of any
deterministic online algorithm for this problem is at least $\zeta$.

Figure 2: Input instance of unit disks for maximum independent set. From each
cluster Alice will add Yellow colored objects as the input instance only if
Bob chooses Blue colored object.

###### Proof.

Let ${\cal A}_{i}$ be a set of vertices reported by our $GDS$ algorithm after
receiving first $i$ vertices $v^{i}=\\{v_{1},\ldots,v_{i}\\}$. Similarly, let
${\cal O}_{i}$ be the set of vertices in the optimum set for $v^{i}$. It is
easy to observe that $|{\cal A}_{i}|\leq|{\cal O}_{i}|$. Let $N_{{\cal
O}_{i}}(a_{i})$ be the set of vertices in ${\cal O}_{i}$ that are adjacent to
$a_{i}\in A_{i}$. Now, consider any vertex $o_{i}$ and $a_{i}$ from ${\cal
O}_{i}$ and $A_{i}$, respectively. By the definition of $\zeta$ (independent
kissing number), we can observe that $|N_{{\cal O}_{i}}(a_{i})|\leq\zeta$ (For
each $a_{i}$ there are at most $\zeta$ vertices from ${\cal O}_{i}$ that are
adjacent to $a_{i}$). We know, $A_{i}$ is a dominating set for ${\cal O}_{i}$,
so it is easy to observe that $\cup_{a_{i}\in A_{i}}N_{{\cal
O}_{i}}(a_{i})={\cal O}_{i}$. From above, we can conclude that the upper bound
of the proposed $GDS$ algorithm for maximum independent set of a graph $G$ has
a competitive ratio $\zeta$.

To proof the lower bound for maximum independent set, we can think of a game
played between two players: Alice and Bob. Here, Alice plays the role of the
adversary and Bob plays the role of the online algorithm. Alice presents the
vertices of a graph $G$ one by one to Bob, and Bob needs to decide whether to
consider that vertex in the independent set or not. Alice have to present
vertices in such a way that will force Bob to choose as less new vertices as
possible; but Bob needs to choose as many vertices as possible to win the
game. Let $\zeta$ be the independent kissing number of the graph under
consideration and $v_{i}$ is the $i^{th}$ vertex. Now, Alice presents $v_{i}$
to Bob; if Bob ignores it then Alice will present some $v_{i^{\prime}}$ to Bob
where, $v_{i^{\prime}}$ is far away from all previous vertices. So without
loss of generality, assume Bob chooses $v_{i}$ then Alice will present
$v_{i+1},\ldots,v_{i+\zeta}$ as the sequence of vertices coming one by one to
Bob such that all of them are pair-wise non-adjacent vertices but each of them
are adjacent to $v_{i}$ (See Figure 2). Since the independent kissing number
of the graph under consideration is $\zeta$, it is always possible to
construct such a sequence of vertices. Now, any optimal offline algorithm will
choose all these $\zeta$ vertices $v_{i+1},\ldots,v_{i+\zeta}$ in the
independent set and Bob will not be able to choose any of them. Therefore, the
lower bound on the competitive ratio for maximum independent set of graph $G$
in the online setup is $\zeta$. ∎

###  3.3 Greedy Algorithm for Connected Dominating Set ($GCDS$)

Eidenbenz [11] proposed that the following greedy algorithm for online
connected dominating set problem achieves $8+\epsilon$ competitive ratio for
unit disk graph. We generalize this for graphs with fixed independent kissing
number $\zeta$.

Suppose that, after observing first $t-1$ vertices $v_{1},\ldots,v_{t-1}$, we
have a solution set ${\cal A}_{t-1}$. Let $v_{t}$ be the new vertex.

  * $\bullet$

If $v_{t}$ is dominated by the set ${\cal A}_{t-1}$, then we set ${\cal
A}_{t-1}$ as the ${\cal A}_{t}$.

  * $\bullet$

Otherwise, we will add $v_{t}$ and one of its neighbour $v_{j}$ where
$j\in[t-1]$ into our solution set. In other words, we set ${\cal A}_{t}={\cal
A}_{t-1}\cup\\{v_{t},v_{j}\\}$.

######  Observation 2.

Whenever the size of the solution set is increased (excepting for the first
time when $v_{1}$ is inserted) the $GCDS$ algorithm adds two vertices $v_{t}$
and $v_{j}$ to the solution set, where $v_{t}$ is independent with ${\cal
A}_{t-1}$. So, instead of ${\cal A}_{t}$, if we maintain two disjoint sets
$I_{t}$ and $J_{t}$ such that we insert $v_{t}$ to $I_{t}$ and $v_{j}$ to
$J_{t}$, then $I_{t}$ is an independent set. Since $|I_{t}|=|J_{t}|+1$, we
have $|{\cal A}_{t}|=2|I_{t}|-1$, where $I_{t}$ is an independent set.

Let $G(V,E)$ be a graph with independent kissing number $\zeta$. Now, we
generalize a result by Wan et al. [27, Lemma 9] that is one of the main
ingredients for analysing the upper bound.

######  Lemma 1.

Let $\cal I$ and ${\cal O}$ be any independent set and minimum connected
dominating set, respectively, of a graph with independent kissing number
$\zeta$. Then $|{\cal I}|\leq(\zeta-1){|{\cal O}|}+1$.

###### Proof.

Let $T$ be any spanning tree of ${\cal O}$. Consider an arbitrary preorder
traversal of $T$ given by $v_{1},v_{2},\ldots,v_{{|{\cal O}|}}$. Let ${\cal
I}_{1}$ be the set of nodes in ${\cal I}$ that are adjacent to $v_{1}$. For
any, $2\leq i\leq{|{\cal O}|}$, let ${\cal I}_{i}$ be the set of nodes in
${\cal I}$ that are adjacent to $v_{i}$ but none of $v_{1},\ v_{2},\ldots,\
v_{i-1}$. Then ${\cal I}_{1},\ {\cal I}_{2},\ldots,\ {\cal I}_{{|{\cal O}|}}$
forms a partition of ${\cal I}$. As $v_{1}$ can be adjacent to at most $\zeta$
independent nodes (due to the definition of $\zeta$), $|{\cal
I}_{1}|\leq\zeta$. For any, $2\leq i\leq{|{\cal O}|}$, at least one node in
$v_{1},\ v_{2},\ldots,\ v_{i-1}$ is adjacent to $v_{i}$ but ${\cal I}_{i}$ is
adjacent to none of $v_{1},\ v_{2},\ldots,\ v_{i-1}$. So, $|{\cal
I}_{i}|\leq(\zeta-1)$ where $2\leq i\leq{|{\cal O}|}$. Thus, we have

$|{\cal I}|=\sum_{i=1}^{{|{\cal O}|}}|{\cal I}_{i}|\\\ ={\cal
I}_{1}+\sum_{i=2}^{{|{\cal O}|}}|{\cal I}_{i}|\\\ \leq\zeta+({|{\cal
O}|}-1)(\zeta-1)\\\ \leq(\zeta-1){|{\cal O}|}+1.$

Hence the lemma follows. ∎

######  Theorem 3.

For a graph with independent kissing number $\zeta$, the $GCDS$ algorithm
achieves the asymptotic competitive ratio $2(\zeta-1)$ and absolute
competitive ratio $min\\{2\zeta,2(\zeta-1)(1+\frac{1}{|{\cal A}_{t}|-1})\\}$
(i.e., $2(\zeta-1)+\epsilon$), where ${\cal A}_{t}$ is the solution returned
by the $GCDS$ algorithm.

###### Proof.

From Observation 2, we have $|{\cal A}_{t}|=2|I_{t}|-1\leq 2|I_{t}|$. On the
other hand, from Lemma 1, we have $|I_{t}|\leq(\zeta-1)|{\cal O}_{t}|+1$. As a
result, we get $|{\cal A}_{t}|\leq 2(\zeta-1)|{\cal O}_{t}|+2$. Therefore, the
asymptotic competitive ratio of the $GCDS$ algorithm is $2(\zeta-1)$.

By Observation 2, we have $|{\cal A}_{t}|=2|I_{t}|-1\leq 2|I_{t}|$, where
$I_{t}$ is an independent set. On the other hand, from Lemma 1, we have
$|{I_{t}}|\leq(\zeta-1){|{\cal O}_{t}|}+1\leq\zeta{|{\cal O}_{t}|}$ (the
second inequality follows from the fact that ${|{\cal O}_{t}|}\geq 1$). Thus,
the competitive ratio is: $\frac{|{\cal A}_{t}|}{{|{\cal
O}_{t}|}}\leq\frac{2|{I_{t}}|}{\frac{|{I_{t}}|}{\zeta}}=2\zeta$. Alternative
(tighter) analysis is:

$\frac{|{\cal A}_{t}|}{{|{\cal
O}_{t}|}}\leq\frac{2|{I_{t}}|-1}{\frac{|{I_{t}}|-1}{\zeta-1}}=2(\zeta-1)(1+\frac{1}{2|{I_{t}}|-2})=2(\zeta-1)(1+\frac{1}{|{{\cal
A}_{t}}|-1}).$

This completes the proof. ∎

#### Improved Bound for Unit Disk Graph

For unit disk graphs Funke et al. [13] presented $|I_{t}|\leq 3.453|{\cal
O}_{t}|+8.291$. Since $|{\cal A}_{t}|\leq 2|I_{t}|$ (from Observation 2)
therefore, $|{\cal A}_{t}|\leq 6.906|{\cal O}_{t}|+16.582$. Hence, we conclude
that the deterministic $GCDS$ algorithm obtains asymptotic competitive ratio
of at most $6.906$ for unit disk graphs.

##  4 Lower Bound of MCDS Problem for Translated Copies

Eidenbenz [11] proposed lower bound of $\frac{10}{3}$ for connected dominating
set of unit disks in the online setup by constructing an example. In this
section, we have generalized that idea for any translated convex objects in
$\mathbb{R}^{2}$.

First, we prove that for a family of translated convex objects, we can always
have optimal independent kissing configuration in standard form. To prove
this, we need the following definition and observation.

######  Definition 2 (Convex Distance $d_{C}$).

Let $p_{1},p_{2}$ be any two points in $\mathbb{R}^{2}$ and let $C$ be a
convex object. Then the convex distance function $d_{C}(p_{1},p_{2})$, induced
by $C$, is defined as the smallest $\lambda\geq 0$ such that
$p_{1},p_{2}\in\lambda C$, while the center of $C$ is at $p_{1}$. Let $O$ be
any object, then the point-to-object distance $d_{C}(p_{1},O)$ is defined as
$\min_{x\in O}d_{C}(p_{1},x)$.

######  Observation 3.

Let $O$ and $L$ be a convex object and a line, respectively. Let $x$ be any
point on $L$. If $x$ moves along the line $L$ from one end to another, then
the distance $d_{C}(x,O)$ first decreases monotonically until a minimum point
(or an interval of the same minimum value), and then it increases
monotonically. (Refer to Figure 3(c).)

######  Lemma 2.

There exists standard optimal independent kissing configuration for a family
of translated copies of a convex object in $\mathbb{R}^{2}$.

(a)

(b)

(c)

Figure 3: (a-b) Illustration of Lemma 2: Moving $\sigma_{2}$ along $L^{+}$,
(c) Illustration of Observation 3.

###### Proof.

To prove this, we will show that given any optimal independent kissing
configuration, we can transform it into a standard form. Consider an optimal
independent kissing configuration where $C$ is the core and $\cal I$ is the
independent set. Let $({\sigma}_{0}$, ${\sigma}_{1}$,…, ${\sigma}_{\zeta-1})$
be the anti-clockwise order of appearance of objects in $\cal I$ around the
core object $C$ in the configuration, where ${\sigma}_{i}\in{\cal I}$, $i\in
Z_{\zeta}$. Consider an object ${\sigma}_{i}\in{\cal I}$ that has non-empty
common interior with $C$. Let $c$ and $c_{i}$ be the center of the object $C$
and ${\sigma}_{i}$, respectively (see Figure 3(a-b).). Let $L$ be the line
obtained by extending the line segment $cc_{i}$ in both direction. Since the
objects ${\sigma}_{i}$ and ${\sigma}_{i-1}$ (resp., ${\sigma}_{i+1}$) are non-
touching and ${\sigma}_{i}$ intersects $C$, we have
$d_{C}(c_{i},{\sigma}_{i-1})>d_{C}(c,{\sigma}_{i+1})$ (resp.,
$d_{C}(c_{i},{\sigma}_{i+1})>d_{C}(c,{\sigma}_{i+1})$). Note that the
operation on index $i$ is modulo $\zeta$. Consider the half-line $L^{+}$ of
$L$ that has one end point at $c_{i}$ and that does not contain the point $c$.
Due to Observation 3, if $x$ moves along $L^{+}$ from $c_{i}$ then the
distance $d_{C}(x,{\sigma}_{i-1})$ (resp., $d_{C}(x,{\sigma}_{i+1})$)
monotonically increases. As a result, if we translate the object
${\sigma}_{i}$ by moving the center along $L^{+}$, the translated copy
${\sigma}_{i}^{\prime}$ never touches the object ${\sigma}_{i-1}$ (resp.,
${\sigma}_{i+1}$). Hence, we will be able to find a point $x$ on $L^{+}$ such
that the translated copy ${\sigma}_{i}^{\prime}$ centering on $x$ will touch
the boundary of $C$, but will not touch ${\sigma}_{i-1}$ and ${\sigma}_{i+1}$.
We replace the object ${\sigma}_{i}$ with ${\sigma}_{i}^{\prime}$ in the
independent kissing configuration. For each object $I\in{\cal I}$ that has
non-empty common interior with $C$, we follow the similar approach as above.
This ensures that all these $\zeta$ objects are mutually non-overlapping (but
touching) with $C$. Hence, the lemma follows. ∎

Now, we introduce some structural definitions.

######  Definition 3 (Path of cycles).

A graph $G(V,E)$ is said to be a _path of cycles_ of length $m$ and size $k$
if the following three properties are satisfied:

  * 1

(cardinality) $G$ has exactly $mk$ vertices and $mk+m-1$ edges;

  * 2

(cycle-partition) $V$ can be partitioned into $m$ disjoint sets
$V_{1},V_{2},\ldots V_{m}$ each having $k$ vertices such that each of the
induced subgraph $G[V_{i}]$ is a cycle, where $i\in[m]$;

  * 3

(head and tail) for each $i\in[m-1]$, there exists exactly one edge $(h,t)\in
E$ such that $h\in V_{i}$ and $t\in V_{i+1}$. We refer $h$ and $t$ as the
_head_ and _tail_ of $V_{i}$ and $V_{i+1}$, respectively. For $V_{1}$ (resp.,
$V_{m}$) any arbitrary vertex other than head (resp., tail) can be denoted as
tail (resp., head).

Refer to Figure 4 for an example of a path of cycles. Let
$V_{1},V_{2},\ldots,V_{m}$ be the cycle-partition of a path of cycles $G(V,E)$
(of length $m$ and size $k$) such that head of $V_{i}$ is adjacent to tail of
$V_{i+1}$, where $1\leq i<m$. Let $v_{0},v_{1},\ldots v_{(k-1)}$ be the clock-
wise order of vertices in a cycle $G[{V}_{i}]$. Let $v_{h}$ and $v_{t}$ be the
head and tail of the cycle $G[V_{i}]$. Now, we define the cyclone-order of
vertices in a cycle and a path of cycles.

Figure 4: Path of cycles and cyclone order: Head and tail of each cycle is
marked. Cyclone order is indicated by bold arrow.

######  Definition 4 (Cyclone-order of vertices in a cycle).

We define the cyclone-order of the vertices of a cycle $G[V_{i}]$ as the
clockwise enumeration of $h-t$ vertices $[v_{t},v_{h})$:
$v_{t},v_{t+1},\ldots,v_{h-1}$ followed by anti-clockwise enumeration of
remaining $k-h+t$ vertices $(v_{t},v_{h}]$: $v_{t-1},v_{t-2},\ldots,v_{h}$. We
denote the first $h-t$ length clock-wise sequence as _cw-part_ and the
remaining as _acw-part_ of a cyclone-order.

######  Definition 5 (Cyclone-order of vertices in a path of cycles).

The cyclone-order of the vertices of a path of cycle is defined as
$cyclone(V_{1})$, $cyclone(V_{2}),\ldots,cyclone(V_{m})$, where
$cyclone(V_{i})$ represents the cyclone-order of the vertices in $V_{i}$,
$i\in[m]$.

See Figure 4 for an illustration of cyclone order of vertices in a path of
cycles. Now, we prove an important property of cyclone-order traversal of
vertices in a path of cycles. This property plays an important role in the
lower bound construction. Proof of the following Lemma is similar to Lemma 10
in [11].

######  Lemma 3.

For a path $\cal P$ of cycles of size $k$ and length $m$, if the vertices are
enumerated in a cyclone order, then any deterministic online algorithm reports
CDS of size at least $(k-1)m-1$.

###### Proof.

Let $V_{1},V_{2},\ldots,V_{m}$ be the cycle-partition of a path of cycles
$G(V,E)$ (of length $m$ and size $k$) such that head of $V_{i}$ is adjacent to
tail of $V_{i+1}$, where $1\leq i<m$. Consider an input sequence of vertices
of $V_{i}$ where the vertices arrive in cyclone-order. First, let us consider
the cw-part of the sequence $[v_{t},v_{h})$: $v_{t},v_{t+1},\ldots,v_{h-1}$.
Any online algorithm will report at least first $h-t-1$ vertices as a CDS for
this sequence. Next, if we append the first $k-(h-t)-1$ vertices of acw-part
$(v_{t},v_{h})$: $v_{t-1},v_{t-2},\ldots,v_{h+1}$, then any online algorithm
will report at least $k-3$ objects as CDS in total. Now, if we append $v_{h}$
to the sequence, then any online algorithm will either add $v_{h-1}$ or
$v_{h+1}$ in the CDS. Therefore, for each individual cycle, any online
algorithm reports CDS of size at least $k-2$. Now, if we append the vertices
of $V_{i+1}$ in cyclone order, then to make a connected dominating set, the
algorithm needs to add $v_{h}$ of $V_{i}$. As a result, for each $1\leq i<m$,
any online algorithm will report $k-1$ vertices; for $V_{m}$ it will report
$k-2$. Hence the lemma follows. ∎

Now, we introduce the concept of C-block which is a basic structure for the
construction of lower bound.

######  Definition 6 (C-block).

Let $\cal S$ be a family of geometric objects. A set $\cal B$ of objects from
$\cal S$ is said to form a _C-block_ if following two conditions are
satisfied:

  * •

the geometric intersection graph of the objects in $\cal B$ is a cycle and

  * •

there exists an object $u(\notin{\cal B})$ in the family $\cal S$ that
intersects all the objects in $\cal B$.

We refer the object $u$ as the _core_ of the C-block $\cal B$. The _size_ of a
C-block is defined as the number of objects in $\cal B$.

######  Lemma 4.

There exists a C-block of size $2\zeta$ for a family of translated copies of a
convex object.

###### Proof.

The proof is by construction. Due to Lemma 2, we know that there exists a
standard optimal independent kissing configuration for a family of translated
copies of a convex object. Let $K$ be a standard independent kissing
configuration where $C$ is the core object and $\cal I$ is the independent
set. Let $({\sigma}_{0}$, ${\sigma}_{1}$,…, ${\sigma}_{\zeta-1})$ be the
clockwise order of appearance of objects in $\cal I$ around the core object
$C$ in the configuration, where ${\sigma}_{i}\in{\cal I}$,
$i\in\mathbb{Z}_{\zeta}$. Let us define a locus $\cal L$ that contains all
points $x\in\mathbb{R}^{2}$ such that $d_{C}(x,C)=1$. Note that the centers of
all the objects $\sigma_{i}\in{\cal I}$ lies on the locus $\cal L$. Now, for
each $i\in\mathbb{Z}_{\zeta}$, we make a copy $\sigma_{i}^{\prime}$ of
$\sigma_{i}$. We translate $\sigma_{i}^{\prime}$ around $C$ in clockwise
direction keeping the center of $\sigma_{i}^{\prime}$ lying on the locus $\cal
L$ until $\sigma_{i}^{\prime}$ touches the object $\sigma_{i+1}$. Note that
$\sigma_{i}^{\prime}$ also touches $\sigma_{i}$, otherwise $K$ is not an
optimal configuration since we can place an extra object in between
$\sigma_{i}$ and $\sigma_{i+1}$. It is easy to observe that, apart from these
two objects, $\sigma_{i}^{\prime}$ does not intersect any other objects in
${\cal I}$. In this way, we obtain a set ${\cal
I}^{\prime}=\\{{\sigma}_{0}^{\prime}$, ${\sigma}_{1}^{\prime}$,…,
${\sigma}_{\zeta-1}^{\prime}\\}$ of $\zeta$ objects. The method of
construction ensures that ${\cal I}^{\prime}$ is an independent set (and
${\cal I}^{\prime}$ together with $C$ is a standard optimal independent
kissing configuration). Now, consider the clock-wise order
$({\sigma}_{0},{\sigma}_{0}^{\prime},{\sigma}_{1},{\sigma}_{1}^{\prime},\ldots,{\sigma}_{\zeta-1},{\sigma}_{\zeta-1}^{\prime})$
of appearance of objects in $\cal I\cup{\cal I}^{\prime}$ around $C$. Here
each object is intersected by exactly two objects: its previous and next
object in the sequence. Therefore, $\cal I\cup{\cal I}^{\prime}$ is a C-block
of size $2\zeta$ where $C$ is the core object.

∎

Similar to the path of cycles, we define the following.

######  Definition 7 (Path of C-blocks).

A set $\cal P$ of C-blocks each of size $k$ from a family of geometric objects
is said to form a _path of C-blocks_ of size $k$ and length $m$ if the
geometric intersection graph of all the geometric objects in $\cal P$ is a
path of cycles of size $k$ and length $m$.

######  Lemma 5.

For any positive integer $m$, there exists a path of C-blocks of size $2\zeta$
and length $m$ for a family of translated copies of a convex object.

###### Proof.

Let ${\cal B}_{1},{\cal B}_{2},\ldots,{\cal B}_{m}$ be $m$ C-blocks, as in
Lemma 4. Let $H_{i}$ be the convex hull of all extreme points of objects in a
C-block ${\cal B}_{i}$, $i\in[m]$. Let us fix an $i\in[m-1]$. By translating
one of the convex-hulls around the other, we can always place two convex hulls
$H_{i}$ and $H_{i+1}$ such that the point of intersection is an extreme point
from both the hulls and common interior of $H_{i}$ and $H_{i+1}$ is empty. As
a result, we have an arrangement of two C-blocks ${\cal B}_{i}$ and ${\cal
B}_{i+1}$ where exactly one object from each block intersects with the other.
Let us denote the point of intersection of ${\cal B}_{i}$ and ${\cal B}_{i+1}$
as $x_{i}$. Let $L_{i}$ be a separation line passing through $x_{i}$ such that
${\cal B}_{i}$ and ${\cal B}_{i+1}$ are in two different sides of $L_{i}$. Let
$t_{1}$th object of ${\cal B}_{i}$ intersects $t_{2}$th object ${\cal
B}_{i+1}$ in this arrangement, where $t_{1},t_{2}(t_{1}\neq
t_{2})\in[2\zeta]$. If we apply the same arrangement for all $i\in[m-1]$ such
that $t_{1}$th object of ${\cal B}_{i}$ intersects $t_{2}$th object ${\cal
B}_{i+1}$, then all separation lines $\\{L_{i}|i\in[m-1]\\}$ will be parallel
to each other. This ensures that the geometric intersection graph of these
C-blocks is a path. Therefore, the claim follows. ∎

Now, we have the main result.

######  Theorem 4.

Let $\zeta$ be the independent kissing number of a family $\cal S$ of
translated copies of a convex object in $\mathbb{R}^{2}$. Then the competitive
ratio of every deterministic online algorithm for minimum connected dominating
set (MCDS) of $\cal S$ is at least $2(\zeta-1)$, if $opt_{cds}$ is one;
otherwise it is at least $\frac{2\zeta-1}{3}$.

###### Proof.

Consider a C-block $\cal B$ of size $2\zeta$ as in Lemma 4. Note that the
geometric intersection graph of objects in $\cal B$ is a a cycle. Consider the
input sequence for the objects in $\cal B$ in cyclone-order. Due to Lemma 3,
any online algorithm reports CDS of size $2\zeta-2$ for this sequence.
Whereas, all the objects in $\cal B$ can be dominated by a core object that we
append as the last object in the input sequence. Therefore, competitive ratio
is at least $2(\zeta-1)$, whereas $opt_{cds}$ is one.

For general case, consider a path $\cal P$ of C-blocks of size $2\zeta$ and
length $m$ as in Lemma 5. Here the geometric intersection graph of the objects
in $\cal P$ is a path of cycle (follows from Definition). Consider the input
sequence $S$ for the objects in $\cal P$ in cyclone-order. Due to Lemma 3, any
online algorithm reports CDS of size $(2\zeta-1)m-1$ for this sequence. Let
$\sigma\in{\cal P}$ be the last object in the sequence $S$. In other words,
$\sigma$ is the head of the last cycle in the cyclone-order. Now, we add an
object $\sigma^{*}$, from the same family of translated copies, to the input
sequence $S$ such that $\sigma^{*}$ touches only $\sigma$. As a result, any
deterministic algorithm will report at least $(2\zeta-1)$ objects as CDS from
the $m$th cycle also. At the end, we add $m$ core objects, one from each of
the C-block in $\cal P$ to the input sequence. For this input sequence, any
online algorithm reports at least $(2\zeta-1)m$ objects, whereas the size of
the optimum is $3m-1$ that consists of head, tail and core objects of each
C-block in $\cal P$, excepting tail from the first C-block. Hence, the result
follows. ∎

######  Remark 1.

For any family of arbitrary oriented convex objects in $\mathbb{R}^{2}$, if we
have a standard independent kissing configuration where the size of the
independent set is $\zeta^{\prime}$, then we can apply the above technique to
obtain a lower bound result ($\zeta$ will be replaced by $\zeta^{\prime}$) of
MCDS for that family.

##  5 Fixed Oriented Unit Hyper-cubes in $\mathbb{R}^{d}$

Throughout this section, if explicitly not mentioned, we use hyper-cube (in
short) to mean axis-parallel unit hyper-cube.

###  5.1 Independent Kissing Number

######  Lemma 6.

For a family of fixed oriented unit hyper-cubes in $\mathbb{R}^{d}$, the
independent kissing number is at most $2^{d}$, where $d$ is any positive
integer.

(a)

(b)

Figure 5: Neighbourhood of a cube in $\mathbb{R}^{3}$.

###### Proof.

Let $K$ be an optimal independent kissing configuration for axis parallel unit
hyper-cubes in $\mathbb{R}^{d}$. Let the core of the configuration be $u$.
Consider the neighbourhood $N(u)$ that contains all the centers of hypercubes
in $K\setminus\\{u\\}$. It is easy to observe that $N(u)$ is an axis-parallel
hyper-cube with side length 2 unit. Let us partition $N(u)$ into $2^{d}$
smaller symmetrical axis-parallel hyper-cubes each having unit side (refer to
Figure 5). If there exist two axis-parallel hyper-cubes $u_{1},u_{2}\in
K\setminus\\{u\\}$ such that their centers lie in the same unit sized smaller
hyper-cube of $N(u)$, then $u_{1}$ and $u_{2}$ will overlap. So, each smaller
hyper-cube can contain at most one centre corresponding to a hyper-cube in
$K\setminus\\{u\\}$. Since $N(u)$ has at most $2^{d}$ smaller hyper-cubes,
$|K\setminus\\{u\\}|\leq 2^{d}$. Therefore, the independent kissing number for
axis-parallel unit hyper-cubes in $\mathbb{R}^{d}$ is at most $2^{d}$. ∎

######  Lemma 7.

For a family of fixed oriented unit hyper-cubes in $\mathbb{R}^{d}$, the
independent kissing number is at least $2^{d}$, where $d$ is any positive
integer.

###### Proof.

Here, we give an explicit construction of an independent kissing configuration
$K$ where the size of the independent set is $2^{d}$. Let
$\sigma_{1},\sigma_{2},\ldots,\sigma_{2^{d}}$ & $\sigma_{2^{d}+1}$ be the
centres of $d$-dimensional axis parallel unit hyper-cubes of $K$. Let
$\sigma_{2^{d}+1}=(\frac{1}{2},\frac{1}{2},\ldots,\frac{1}{2}$), and
$p_{1},p_{2},\ldots,p_{2^{d}}\in\mathbb{R}^{d}$ be corner points of the
$d$-dimensional unit hyper-cube centred at $\sigma_{2^{d}+1}$. It is easy to
observe that each coordinate of $p_{i},i\in[2^{d}]$ is either 0 or 1. Let
$\epsilon$ be a positive constant satisfying $0<\epsilon<\frac{1}{2\sqrt{d}}$.
Let us consider

$\sigma_{i}(x_{j})=\begin{cases}-\epsilon,&\text{ if $p_{i}(x_{j})=0$}\\\
1+\epsilon,&\text{ if $p_{i}(x_{j})=1$,\quad\quad\quad for $i\in[2^{d}]$ \&
$j\in[d]$},\end{cases}$ (1)

where $\sigma_{i}(x_{j})$ and $p_{i}(x_{j})$ are the $j^{th}$ coordinate value
of $\sigma_{i}$ and $p_{i}$, respectively.

######  Claim 1.

All the hyper-cubes centred at $\sigma_{1},\sigma_{2},\ldots,\sigma_{2^{d}}$
are mutually non-touching and each of them are intersected by the hyper-cube
centred at $\sigma_{2^{d}+1}$.

###### Proof.

The distance between $p_{i}$ and $\sigma_{i}$ is $\sqrt{d}\epsilon$, $\forall$
$i\in[2^{d}]$. Since $\epsilon<\frac{1}{2\sqrt{d}}$, the corner point $p_{i}$
is contained in the unit hyper-cube centred at $\sigma_{i}$. Thus,
$\sigma_{2^{d}+1}$ intersects $\sigma_{i}$, $\forall$ $i\in[2^{d}]$. Consider,
any pair $\sigma_{i}$ and $\sigma_{j}$, for $i,j\in[2^{d}]$ and $i\neq j$.
Since $\sigma_{i}$ and $\sigma_{j}$ are distinct, the distance between
$\sigma_{i}$ and $\sigma_{j}$ is $(1+2\epsilon)$ under $L^{\infty}$ norm. This
implies that all the $d$-dimensional axis-parallel unit hyper-cubes centred at
$\sigma_{1},\sigma_{2},\ldots,\sigma_{2^{d}}$ are pair-wise non-touching. ∎

This completes the proof. ∎

######  Theorem 5.

The independent kissing number $\zeta$ for geometric intersection graph of
fixed oriented $d$-dimensional hyper-cubes is $2^{d}$, where $d$ is any
positive integer.

###  5.2 Lower Bound of MCDS

Figure 6: Path of PC-blocks for unit squares.

Throughout this subsection, we use $T(d)$ to denote $2^{d-2}$. Now, we
consider the MCDS problem. Similar to C-block, here, we define PC-block.

######  Definition 8 (PC-block).

Let $\cal S$ be a family of geometric objects. A set $\cal B$ of objects from
$\cal S$ is said to form a _PC-block_ of length $m$ and size $k$ if following
two conditions are satisfied:

  * •

the geometric intersection graph of the objects in $\cal B$ is a path of
cycles of length $m$ and size $k$, and

  * •

there exists an object $u(\notin{\cal B})$ in the family $\cal S$ that
intersects all the objects in $\cal B$.

We refer the object $u$ as the _core_ of the PC-block $\cal B$.

######  Lemma 8.

For a family of axis-parallel unit hyper-cubes in $\mathbb{R}^{d}$, there
exists a PC-block of length $2^{d-2}$ and size $8$, where $d\geq 2$ is an
integer.

###### Proof.

We prove this by induction. For $d=2$, the base case of the induction follows
from the construction in Figure 6. Here, the hyper-cubes centered at
$\sigma_{1},\sigma_{2},\ldots,\sigma_{8}$ forms a PC-block of length 1 and
size 8. The hyper-cube centered at $\sigma_{8m+2}$ is the core object of this
PC-block. Here, the sequence $\sigma_{1},\sigma_{2},\ldots,\sigma_{8}$ is a
cyclone-order of the hyper-cubes in the PC-block.

Let us assume that the induction hypothesis holds for $d-1$ dimension. Let
${\cal B}_{d-1}$ be a PC-block of length $2^{d-3}$ and size $8$ of axis
parallel unit hyper-cubes in $\mathbb{R}^{d-1}$. To construct a PC-block
${\cal B}_{d}$ in $\mathbb{R}^{d}$, we consider two copies $B_{1}$ and $B_{2}$
of ${\cal B}_{d-1}$ and append $d$th coordinate to each of their hyper-cubes.
Let $S_{d-1}:\sigma_{1}^{d-1},\sigma_{2}^{d-1},\ldots,\sigma_{T(d-1)}^{d-1}$
be a cyclone order of centers of unit hyper-cubes in ${\cal B}_{d-1}$. Now, we
define the cyclone-order of center
$S_{d}:\sigma_{1}^{d},\sigma_{2}^{d},\ldots,\sigma_{T(d)}^{d}$ for unit hyper-
cubes in ${\cal B}_{d}$ as follows. The first half of the sequence $S_{d}$ is
made from the cyclone-order $S_{d-1}$ with original order and the second half
is made from the reverse order of $S_{d-1}$. Now, we are going to define the
$d$th coordinate. Let $0<\epsilon<\frac{1}{8}$ be a small positive constant
and $f$ be any fixed real number. For the center $\sigma_{T(d-1)}^{d-1}$ of
$B_{1}$ and $B_{2}$, we append $f-(\frac{1}{2}-\epsilon)$ and
$f+(\frac{1}{2}-\epsilon)$, respectively, as the $d$th coordinate. For all
other centers in $B_{1}$ and $B_{2}$, we append $f-(\frac{1}{2}+2\epsilon)$
and $f+(\frac{1}{2}+2\epsilon)$, respectively, as the $d$th coordinate. This
ensures that only $\sigma_{T(d-1)}^{d-1}$ of $B_{1}$ and $B_{2}$ intersects
with each other. More formally, we have the following.

$\sigma_{i}^{d}(x_{j})=\begin{cases}f-(\frac{1}{2}+2\epsilon),&\text{ if $j=d$
and $i<T(d-1)$}\\\ f-(\frac{1}{2}-\epsilon),&\text{ if $j=d$ and
$i=T(d-1)$}\\\ f+(\frac{1}{2}-\epsilon),&\text{ if $j=d$ and $i=T(d-1)+1$}\\\
f+(\frac{1}{2}+2\epsilon),&\text{ if $j=d$ and $i>T(d-1)+1$}\\\
\sigma_{i}^{d-1}(x_{j}),&\text{if $j<d$ and $i\leq T(d-1)$}\\\
\sigma_{2T(d-1)-i+1}^{d-1}(x_{j}),&\text{if $j<d$ and $i\geq
T(d-1)+1$}.\par\end{cases}$ (2)

Here $\sigma_{i}^{d}(x_{j})$ is the $j^{th}$ coordinate value of
$\sigma_{i}^{d}$, where $i\in[T(d)]$ and $j\in[d]$.

This appending of the $d$th coordinate ensures the geometric intersection
graph of the hyper-cubes in $B_{i}$ ($i\in[2]$) remains a path of cycles of
length $2^{d-3}$ and size $8$. Additionally, the geometric intersection graph
of $B_{1}\cup B_{2}$ is a path of cycles of length $2^{d-2}$ and size $8$.

Now, to prove the lemma, we only need to prove the existence of a core hyper-
cube for ${\cal B}_{d}$. Let us assume that a $(d-1)$-dimensional unit hyper-
cube centred at $c^{d-1}$ dominates all hyper-cubes of ${\cal B}_{d-1}$. The
center $c^{d}$ of the core object is obtained by appending $f$ as the $d$th
coordinate to $c^{d-1}$. In other words, we have

$c^{d}(x_{j})=\begin{cases}f,&\text{ if $j=d$}\\\ c^{d-1}(x_{j}),&\text{ if
$j<d$}.\end{cases}$ (3)

Here $c^{d}(x_{j})$ is the $j^{th}$ coordinate value of $c^{d}$, where
$i\in[T(d)]$ and $j\in[d]$.

Figure 7: Construction of the cyclone-order $S_{d}$.

######  Claim 2.

The axis-parallel unit hyper-cube centered at $c^{d}$ dominates all the hyper-
cubes in ${\cal B}_{d}$.

###### Proof.

To prove the claim, we need to show that
$|{c^{d}(x_{j})-\sigma_{i}^{d}(x_{j})}|\leq 1$ for all $i\in[T(d)]$ and
$j\in[d]$. Since the $(d-1)$-dimensional axis-parallel hyper-cube centred at
$c^{d-1}$ dominates all the axis-parallel hyper-cubes centred in the sequence
$S_{d-1}$ (due to induction hypothesis), we have
$|{c^{d-1}(x_{j})-\sigma_{i}^{d-1}(x_{j})}|\leq 1$ for all $i\in[T(d-1)]$ and
$j\in[d-1]$. From Equation 2 and 3, we get
$|{c^{d}(x_{d})-\sigma_{i}^{d}(x_{d})}|\leq\frac{1}{2}+2\epsilon$. As a
result, $|{c^{d}(x_{j})-\sigma_{i}^{d}(x_{j})}|\leq 1$ for all $i\in[T(d)]$
and $j\in[d-1]$. Therefore, the claim holds. ∎

This completes the proof. ∎

######  Definition 9 (Path of PC-blocks).

A set $\cal P$ of PC-blocks from a family of geometric objects is said to form
a _path_ if following conditions are satisfied:

  * (a)

the geometric intersection graph of these PC-blocks is a path, and

  * (b)

if two PC-blocks are intersecting, then exactly one object from each block
intersects with the other.

The _length_ of a path $\cal P$ of PC-blocks is defined as the number of PC-
blocks in $\cal P$.

Now, we prove the following.

######  Lemma 9.

For a family of axis-parallel unit hyper-cubes in $\mathbb{R}^{d}$, there
exists a path of PC-block of length $m$ where each PC-block is of length
$2^{d-2}$ and size $8$, where $m\geq 1,d\geq 2$ are integers.

###### Proof.

For $d=2$, the example given in Figure 6 is a path of PC-blocks satisfying the
lemma. For $d>2$, we give an explicit construction.

First, we define each PC-block. Consider a PC-block ${\cal B}_{d}$ as defined
in Lemma 8. Let $S_{d}:\sigma_{1}^{d},\sigma_{2}^{d},\ldots,\sigma_{T(d)}^{d}$
be a cyclone-order of the centers of hyper-cubes in ${\cal B}_{d}$. Let
$c^{d}$ be the center of the core for the PC-block ${\cal B}_{d}$ with the
value of the $d$th coordinate $f$. Let us change the value of the $d$th
coordinate of $\sigma_{1}^{d}$ and $\sigma_{T(d)}^{d}$ as $f-(1-\epsilon)$ and
$f+(1-\epsilon)$, respectively. Note that, after changing this, the modified
hyper-cubes in ${\cal B}_{d}$ remains a PC-block. We denote this modified PC-
block as ${\cal B}(f)$.

Now, we define a path of PC-blocks where each PC-block is a translated copy of
${\cal B}(f)$. Consider translated copies ${\cal B}(f+t(3-2\epsilon))$, where
$1\leq t\leq m-1$. Note that only $\sigma_{1}^{d}$ of ${\cal
B}(f+t(3-2\epsilon))$ intersects $\sigma_{T(d)}^{d}$ of ${\cal
B}(f+(t-1)(3-2\epsilon))$. As a result, ${\cal B}(f)$, ${\cal
B}(f+(3-2\epsilon)),\ldots$, ${\cal B}(f+(m-1)(3-2\epsilon))$ forms a path of
PC-block of length $m$. Thus the lemma follows.

∎

######  Theorem 6.

The competitive ratio of every deterministic online algorithm for minimum
connected dominating set (MCDS) of $d$-dimensional unit hyper-cubes in the
online setup is at least $7\times 2^{d-2}-1$, if $opt_{cds}=1$; otherwise it
is at least $\frac{7\times 2^{d-2}}{3}$.

###### Proof.

Similar to the proof of Theorem 4, we can prove this theorem with the
following refinements.

  * •

Instead of C-block of size $2\zeta$, here we have PC-block of size $8$ and
length $2^{d-2}$ (due to Lemma 8).

  * •

Instead of path of C-block, we have path of PC-block (due to Lemma 9).

∎

##  6 Arbitrary Oriented Unit Hyper-cubes in $\mathbb{R}^{d}$

###  6.1 Independent Kissing Number

(a)

(b)

Figure 8: (a) An independent kissing configuration for arbitrary oriented unit
squares, (b) The optimal kissing configuration for squares.

First, we consider the arbitrary oriented unit squares in $\mathbb{R}^{2}$.
Youngs [29] proved that the kissing number for squares is 8. Later Klamkin
[20] proved that the Figure 8(b) is the unique optimal configuration for this.
Since in this configuration, the neighbours are touching, the independent
kissing number $\zeta$ for family of arbitrary oriented unit squares is
strictly less than eight. In Figure 8(a), we give an example of independent
kissing configuration for arbitrary oriented unit squares where size of the
independent set is six. Therefore, we raise the following question.

######  Problem 1.

What is the independent kissing number for geometric intersection graph of
arbitrary oriented squares: six or seven?

Now, we give a lower bound for the general case.

######  Lemma 10.

The value of independent kissing number $\zeta$ for geometric intersection
graph of arbitrary oriented $d$-dimensional unit hyper-cubes is at least
$6\times 2^{d-2}$, where $d\geq 2$ is an integer.

###### Proof.

We prove this by induction on $d$. For $d=2$, the base case of the induction,
consider the independent kissing configuration given in Figure 8(a) where size
of the independent set is 6.

Let us assume that the induction hypothesis holds for $d-1$ dimension. Let
$K_{d-1}$ be an independent kissing configuration where size of the
independent set is $M(d-1)=6\times 2^{d-3}$ for $(d-1)$-dimensional unit
hyper-cubes. Let the core hyper-cube in $K_{d-1}$ is centered at $c^{d-1}$,
and other hyper-cubes are centred at
$\sigma_{1}^{d-1},\sigma_{2}^{d-1},\ldots,\sigma_{M(d-1)}^{d-1}$. To construct
independent kissing configuration $K_{d}$, we take two copies independent set
from $K_{d-1}$ and append $d$th coordinate to each of them. We append
$-(\frac{1}{2}+\epsilon)$ as the $d$th coordinate to all the centers of the
first copy, whereas we append $-(\frac{1}{2}+\epsilon)$ to the other. More
formally,

$\sigma_{i}^{d}(x_{j})=\begin{cases}\sigma_{i}^{d-1}(x_{j}),&\text{ if $j<d$
and $i\leq M(d)$}\\\ \frac{1}{2}+\epsilon,&\text{ if $j=d$ and $i\leq
M(d-1)$}\\\ -(\frac{1}{2}+\epsilon),&\text{ if $j=d$ and
$i>M(d-1)$.}\end{cases}$ (4)

The center $c^{d}$ is obtained by appending $0$ as the $d$th coordinate to
$c^{d-1}$, and the hyper-cube centered at $c^{d}$ is axis parallel in every
dimension except first two coordinates. Therefore, we have.

$c^{d}(x_{j})=\begin{cases}$0$,&\text{ if $j=d$}\\\ c^{d-1}(x_{j}),&\text{ if
$j<d$.}\end{cases}$ (5)

Here, all the $d$-dimensional unit hyper-cubes centred at
$\sigma_{1}^{d},\sigma_{2}^{d},\ldots,\sigma_{M(d)}^{d}$ are mutually non-
touching and all of them can be dominated by the unit hyper cube centred at
$c^{d}$. It is straightforward to see that the value of $M(d)=2M(d-1)$, where
$M(d-1)=6\times 2^{d-3}$. Hence the lemma follows. ∎

Now, we raise following question.

######  Problem 2.

What is the independent kissing number $\zeta$ for geometric intersection
graph of arbitrary oriented $d$-dimensional unit hyper-cubes?

###  6.2 Lower Bound of MCDS

Figure 9: Path of PC-blocks for arbitrary oriented unit squares.

######  Lemma 11.

For a family of arbitrary oriented unit hyper-cubes in $\mathbb{R}^{d}$, there
exists a PC-block of length $2^{d-2}$ and size $12$, where $d\geq 2$ is an
integer.

###### Proof.

The proof of this lemma is similar to Lemma 8. For $d$=2, the base of the
induction is followed from Figure 9 where we have PC-block of length 1 and
size 12. Note that the core hyper-cube of the PC-block is arbitrary oriented
only.

The PC-block in higher dimension is constructed in a similar way to Lemma 8
where all the hyper-cubes are axis-parallel. Similar way, we define the core
hyper-cube of the PC-block in higher dimension. The only difference is that
this core hyper-cube is also axis-parallel, except the first two coordinates.
∎

Similar to Lemma 9, using Figure 9 instead of Figure 6, we can prove the
following.

######  Lemma 12.

For a family of arbitrary oriented unit hyper-cubes in $\mathbb{R}^{d}$, there
exists a path of PC-block of length $m$ where each PC-block is of length
$2^{d-2}$ and size $12$, where $m\geq 1,d\geq 2$ are integers.

Now, similar to Theorem 6, we have the following lower bound result.

######  Theorem 7.

The competitive ratio of every deterministic online algorithm for minimum
connected dominating set (MCDS) of $d$-dimensional arbitrary oriented unit
hyper-cubes in the online setup is at least $11\times 2^{d-2}-1$, if
$opt_{cds}=1$; otherwise it is at least $\frac{11\times 2^{d-2}}{3}$.

##  7 Congruent Balls in $\mathbb{R}^{3}$

###  7.1 Independent Kissing Number

First, we are going to present a lower bound.

######  Lemma 13.

The independent kissing number for geometric intersection graph of unit balls
in $\mathbb{R}^{3}$ is at least 12.

###### Proof.

Let $\epsilon>0$ (in particular, one can choose $\epsilon$=$0.001$), and
$e$=$2+\epsilon$ be the length of each edge of a regular icosahedron $C$.
Choose corner points of $C$ as the centre
$\sigma_{1},\sigma_{2},\ldots,\sigma_{12}$ of the unit balls (having unit
radius). Since the edge length of the icosahedron $C$ is greater than 2, so
all of these balls are non-touching. It is a well-known fact that if a regular
icosahedron has edge length $e$, then the radius $R$ of the circumscribed ball
is $R$=$e\sin(\frac{2\pi}{5})$. For our case, it is easy to see that $R<2$ for
the icosahedron $C$. Thus all the unit balls centred at
$\sigma_{1},\sigma_{2},\ldots,\sigma_{12}$ can be dominated by a unit ball
whose center $\sigma_{13}$ coincides with the centre of the icosahedron $C$.
This implies that the lower bound of $\zeta$ for unit balls is 12. ∎

Since the kissing number for balls in $\mathbb{R}^{3}$ is 12 [5, 26], we have
the following.

######  Theorem 8.

The independent kissing number for geometric intersection graph of unit balls
in $\mathbb{R}^{3}$ is 12.

###  7.2 Lower Bound of MCDS

######  Theorem 9.

The competitive ratio of every deterministic online algorithm for minimum
connected dominating set (MCDS) of unit balls is at least 17, if $opt_{cds}$
is one; otherwise it is at least $6$.

Figure 10: Regular Icosahedron.

###### Proof.

Refer to Figure 10. Let the given regular icosahedron has edge length same as
in Lemma 13. Recall that in this icosahedron, all the unit balls centred at
the vertices are pair-wise non-touching and all of them are intersected by the
unit ball $\rho$ centred at the center $c$ of the icosahedron. Consider any
edge $a,b$ of the icosahedron. Let $m_{a,b}$ be a point obtained by shooting a
ray from $c$ to the midpoint of $ab$ and extending it upto distance $R$ from
$c$. If we place a unit ball centred at $m_{a,b}$ then it is intersected by
the unit ball $\rho$. Consider the set of corners
$\sigma_{1},\sigma_{2},\ldots,\sigma_{10}$. In a similar fashion, we can place
balls in each edge of $i,i+1$ of the icosahedron, where $i\in[9]$. Note that
in this way, we have 19 balls whose geometric intersection graph forms a path
and each of these balls are dominated by the unit ball $\rho$. We refer these
set of 19 balls as a _P-block_ and the unit ball $\rho$ as the core of this
P-block. Now consider the sequence of unit balls centred at
$\sigma_{1},m_{1,2},\sigma_{2},m_{2,3},\ldots,\sigma_{9},m_{9,10},\sigma_{10}$
that appears according to the path. For this sequence of input, any online
algorithm requires at least $17$ unit balls to form a connected dominating
set. Therefore, if $opt_{cds}=1$, then the lower bound is $17$. For the
general case, we can form a path of P-blocks of length $m>2$ (similar to
Definition 9). Consider the enumeration of unit balls according to the order
they appear in the path of P-blocks followed by the $m$ core balls. For this
input sequence, any online algorithm will report CDS of size at least $19m-2$,
whereas the size of the optimum is $3m-1$. Thus, the theorem follows. ∎

##  8 Fixed Oriented Unit Triangles

In this section, we are going to refer an equilateral triangle as an unit
triangle. Observe that the neighbourhood of an unit triangle would be a
hexagon as shown in Figure 11(a).

###  8.1 Independent Kissing Number

(a)

(b)

(c)

Figure 11: (a) The boundary of the neighbourhood of a triangle (in blue) is
marked blue, (b) The neighbourhood $N(\sigma_{o})$ partitioned into 6
symmetrical triangles, (c) The point $p$ coincides with the point $o$.

(a)

(b)

Figure 12: (a) $\ell,{\ell}^{\prime}$ and $m$ be the points of intersection of
the line $L$ with line segments $xy,de$ and $uv$, respectively, (b) The point
$p$ lie inside the $\Delta ode$.

######  Lemma 14.

The value of independent kissing number $\zeta$ for geometric intersection
graph of fixed oriented unit triangles is at most $6$.

###### Proof.

Let $K$ be an optimal independent kissing configuration for unit triangles.
Let the core of the configuration be the triangle $\sigma_{o}$ centered at
$o$. Consider the neighbourhood $N(\sigma_{o})$ that contains all the centers
of triangles in $K\setminus\\{\sigma_{o}\\}$.

Let us partition the neighbourhood $N(\sigma_{o})$, denoted by the hexagon
$abcdef$, into six sub-regions each consisting of an equilateral triangle with
unit side as shown in the Figure 11(b). We will show that each sub-region can
contain at most one triangle that belongs to $K\setminus\\{\sigma_{o}\\}$.
Now, we are going to prove this for the triangular sub-region $\Delta ode$
(proof for all other triangular sub-regions will be similar). To prove this,
it is enough to show that if we put an equilateral triangle $\sigma_{p}\in
K\setminus\\{\sigma\\}$ centred at any point $p\in\Delta ode$, $N(\sigma_{p})$
will cover the entire triangular sub-region $\Delta ode$. We denote the
hexagon $N(\sigma_{p})$ by $uvwxyz$.

  * (I)

The point $p$ coincides with the point $o$. It is easy to observe that
$N(\sigma_{p})$ is entirely covering $\Delta ode$ (see Figure 11(c)).

  * (II)

The point $p$ lies on the line $od$ or $oe$. Without loss of generality,
assume that $p$ lies on the line $od$. One way to view this is as follows:
initially, as in case I, the point $p$ coincides with the point $o$; next, we
move the point $p$ along the line $od$ towards the point $d$ (until it reaches
its new destination). We can alternatively visualize this as follows: instead
of moving the point $p$ on $od$ towards $d$, fixing the point $p$ and its
neighbourhood $N(\sigma_{p})$, we are moving the $\Delta ode$ from its initial
position such that the point $o$ always lies on the line $pu$ and $o$ moves
towards $u$. Since $pu$ and $yz$ are parallel and are of same length, $e$ will
move along the line $yz$ towards $z$ and when $o$ reaches $u$ the $\Delta ode$
is moved to the position of $\Delta upz$. Hence $N(\sigma_{p})$ completely
covers the $\Delta ode$.

  * (III)

The point $p$ lies inside the $\Delta ode$. Let $L$ be the line obtained by
extending the line segment $op$ in both direction. Let $\ell,{\ell}^{\prime}$
and $m$ be the points of intersection of the line $L$ with line segments
$xy,de$ and $uv$, respectively (see Figure 12(a)). One way to visualize the
situation is as follows: initially, as in case I, the point $p$ coincides with
the point $o$; next, we move the point $p$ along the line $L$ towards the
point ${\ell}^{\prime}$ (until it reaches its new destination). We can
alternatively visualize this as follows: instead of moving $p$, we fix the the
point $p$ and its neighbourhood $N(\sigma_{p})$; we move the $\Delta ode$ from
its initial position $\Delta pxy$ such that the point $o$ moves along the line
$L$ towards the point $m$. Observe that, when $o$ reaches the boundary $uv$,
the point $p$ coincides with the point ${\ell}^{\prime}$ (see Figure 12(b)).
Thus the $\Delta ode$ is always contained in the neighbourhood
$N(\sigma_{p})$. This completes the proof.

∎

Figure 13: An independent kissing configuration for unit triangles.

In Figure 13, we have constructed an example of independent kissing
configuration for unit triangles where size of the independent set is five.
Thus, we raise the following question.

######  Problem 3.

What is the independent kissing number for geometric intersection graph of
fixed oriented unit triangles- five or six?

Figure 14: Input instance of triangles for connected dominating set.

###  8.2 Lower Bound of MCDS

Since the lower bound of independent kissing number for translates of unit
triangle is 5, using Theorem 4 we have the lower bound of MCDS problem for
unit triangles is at least 8 if $opt_{cds}$ is 1; otherwise it is 3. Here, we
have constructed an example (Figure 14) of a path of C-blocks for unit
triangles of length $m$ and size 11. Thus, similar to the proof of Theorem 4,
we can prove the following.

######  Theorem 10.

The competitive ratio of every deterministic online algorithm for minimum
connected dominating set (MCDS) of triangles is at least $9$, if $opt_{cds}$
is one; otherwise it is at least $\frac{10}{3}$.

##  9 Unit Regular $k$-gon ($k\geq 5$)

In this section, we consider translated copies of a regular polygon as a set
of input to the online algorithm.

###  9.1 Fixed Oriented

(a)

(b)

(c)

Figure 15: Illustration of Lemma 15: An independent kissing configuration for
(a) pentagon, (b) hexagon, and (c) $k$-gon, $k\geq 7$, respectively.

######  Lemma 15.

The value of independent kissing number $\zeta$ for geometric intersection
graph of $k$-regular polygon is at least $5$, where $k\geq 5$.

###### Proof.

For $k=5$ and $6$, refer to Figure 15, where we have constructed examples of
independent kissing configuration having the independent set of size five. For
$k\geq 7$, we have the following proof. Consider a circle $C$ of radius $1.78$
centred at $\sigma_{6}$ (see Figure 15(c)). Let us inscribe a pentagon of
largest radius inside $C$. Let $\sigma_{1},\sigma_{2},\ldots,\sigma_{5}$ be
the five corners of this pentagon. Observe that
$dist(\sigma_{i},\sigma_{j})=2\times 1.78\sin(\pi/5)>2$, where $i,j\in[5]$ and
$i\neq j$. Therefore, all the regular $k$-gons (having circum-radius $1$)
centred at $\sigma_{1},\sigma_{2},\ldots,\sigma_{5}$ are pair-wise non-
touching.

Let $R$ and $r$ be the circum-radius and in-circle radius of a regular
$k$-gon, respectively. It is easy to observe that the relation between $R$ and
$r$ is $r=R\cos({\frac{\pi}{k}})$. Clearly, $r$ is the minimum distance from
the center to any edge of regular $k$-gon. For $k\geq 7$, the minimum distance
from the center to the edge of a regular $k$-gon (having circum-radius $1$) is
$\cos{\frac{\pi}{k}}$ which is at least $\cos{\frac{\pi}{7}}$ i.e., approx
0.9. Since, the $dist(\sigma_{i},\sigma_{6})$ is less than $1.8$ for all
$i\in[5]$, the regular $k$-gon centred at $\sigma_{6}$ intersects all the
regular $k$-gon centred at $\sigma_{1},\sigma_{2},\ldots,\sigma_{5}$. Hence, 5
is the lower bound. ∎

On the other hand, the kissing number for regular $k$-gon ($k\geq 5$) is 6 [5,
26]. Thus, we have the following question.

######  Problem 4.

What is the independent kissing number for geometric intersection graph of
fixed oriented $k$-gon ($k\geq 5$): five or six?

###  9.2 Arbitrary Oriented

From Figure 16, we can observe that the independent kissing number for
$k$-regular polygon ($5\leq k\leq 10$) is at least 6. Zhao and Xu [30] proved
that the kissing number of $k$-regular polygon ($k\geq 5)$ is 6. As a result,
the independent kissing number for $k$-regular polygon ($5\leq k\leq 10$) is
exactly 6. Since independent kissing number of unit disks is $5$. Therefore,
we raise the following question:

######  Problem 5.

What is the minimum value of $k$ for which the geometric intersection graph of
arbitrary oriented $k$-gon has the independent kissing number 5?

(a)

(b)

(c)

(d)

(e)

(f)

Figure 16:  Independent kissing configuration for (a) pentagon (b) hexagon (c)
septagon (d) octagon (e) nonagon (f) decagon.

##  10 Conclusion

In this paper, we define independent kissing number $\zeta$ of a graph $G$ as
$max_{v\in V}\\{\alpha(G[N(v)])\\}$. The value of $\zeta$ for geometric
objects like fixed oriented squares, unit disks and fixed oriented
$d$-dimensional hyper-cubes are 4, 5 and $2^{d}$, respectively; whereas the
value of $\zeta$ for fixed oriented triangles, regular $k$-gons and arbitrary
oriented squares belongs to $\\{5,6\\},\\{5,6\\}$ and $\\{6,7\\}$,
respectively. We show that for graphs with independent kissing number $\zeta$,
the well known online greedy algorithm is optimal for minimum dominating-set,
minimum independent dominating set and maximum independent set problems, and
it achieves a competitive ratio of $\zeta$. For geometric intersection graph,
the well-known greedy algorithm $GCDS$ for MCDS achieves the asymptotic
competitive ratio at most $2(\zeta-1)$; whereas the competitive ratio of every
deterministic online algorithm for MCDS for translates of a convex object is
at least $2(\zeta$-1), if $opt_{cds}$ is one; otherwise it is at least
$\frac{2(\zeta-1)+1}{3}$. As an implication, it would be interesting
combinatorial problem to know for which other graph classes the independent
kissing number is constant.

(a)

(b)

Figure 17: (a) Set of unit disks, and (b)the corresponding complement graph.

Competitive ratio preserving reduction from the maximum independent set to the
maximum clique for general graphs is known [3, Thm 7.3.3]. As a result, the
lower bound for maximum clique is at least the lower bound of maximum
independent set problem for general graphs. But we cannot apply this simple
approach to graphs having independent kissing number $\zeta$ because the
independent kissing number may not be bounded for the complement graph $G_{C}$
of a graph $G$. For example, one can observe that $\zeta$ is unbounded (i.e.,
equal to the number of vertices $n$) for the complement graph of an unit disk
graph (see Figure 17). Whether one can obtain better result for the online
maximum clique problem for geometric intersection graphs remains as an open
question.

### Acknowledgement

The authors wish to thank an anonymous reviewer for referring to the article
[13] that helps to improve the state of the art upper bound of the MCDS
problem for unit disk graph in the online setup.

## References

  * [1] Piotr Berman and Toshihiro Fujito.  On approximation properties of the independent set problem for low degree graphs.  Theory Comput. Syst., 32(2):115–132, 1999.
  * [2] Allan Borodin and Ran El-Yaniv.  Online computation and competitive analysis. Cambridge University Press, 1998.
  * [3] Allan Borodin and Denis Pankratov.  Online Algorithms.  url: http://www.cs.toronto.edu/ bor/2420s19/papers/draft-ch1-8.pdf, DRAFT: March 14, 2019.
  * [4] Joan Boyar, Stephan J. Eidenbenz, Lene M. Favrholdt, Michal Kotrbcík, and Kim S. Larsen.  Online dominating set.  Algorithmica, 81(5):1938–1964, 2019.
  * [5] Peter Brass, William O. J. Moser, and János Pach.  Research problems in discrete geometry.  Springer, 2005.
  * [6] Timothy M. Chan and Sariel Har-Peled.  Approximation algorithms for maximum independent set of pseudo-disks.  Discret. Comput. Geom., 48(2):373–392, 2012.
  * [7] Marek Chrobak, Christoph Dürr, Aleksander Fabijan, and Bengt J. Nilsson.  Online clique clustering.  Algorithmica, 82(4):938–965, 2020.
  * [8] Kenneth L. Clarkson and Kasturi R. Varadarajan.  Improved approximation algorithms for geometric set cover.  Discrete & Computational Geometry, 37(1):43–58, 2007.
  * [9] Minati De and Abhiruk Lahiri.  Geometric dominating set and set cover via local search.  CoRR, abs/1605.02499, 2016.
  * [10] Adrian Dumitrescu, Anirban Ghosh, and Csaba D. Tóth.  Online unit covering in Euclidean space.  Theor. Comput. Sci., 809:218–230, 2020.
  * [11] Stephan Eidenbenz.  Online dominating set and variations on restricted graph classes.  Technical Report No 380, ETH Library, 2002.
  * [12] Hans Eriksson.  Mbone: The multicast backbone.  Communications of the ACM, 37(8):54–60, 1994.
  * [13] S. Funke, A. Kesselman, U. Meyer, and M. Segal.  A simple improved distributed algorithm for minimum cds in unit disk graphs.  In WiMob’2005), IEEE International Conference on Wireless And Mobile Computing, Networking And Communications, 2005., volume 2, pages 220–223 Vol. 2, 2005.
  * [14] Michael R. Garey and David S. Johnson.  Computers and Intractability; A Guide to the Theory of NP-Completeness.
  * [15] Oliver Göbel, Martin Hoefer, Thomas Kesselheim, Thomas Schleiden, and Berthold Vöcking.  Online independent set beyond the worst-case: Secretaries, prophets, and periods.  In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II, volume 8573 of Lecture Notes in Computer Science, pages 508–519. Springer, 2014.
  * [16] Sudipto Guha and Samir Khuller.  Approximation algorithms for connected dominating sets.  Algorithmica, 20(4):374–387, 1998.
  * [17] Magnús M. Halldórsson, Kazuo Iwama, Shuichi Miyazaki, and Shiro Taketomi.  Online independent sets.  Theor. Comput. Sci., 289(2):953–962, 2002.
  * [18] Sariel Har-Peled and Kent Quanrud.  Approximation algorithms for polynomial-expansion and low-density graphs.  In Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, pages 717–728, 2015.
  * [19] Gow-Hsing King and Wen-Guey Tzeng.  On-line algorithms for the dominating set problem.  Inf. Process. Lett., 61(1):11–14, 1997.
  * [20] M. S. Klamkin, T. Lewis, and A. Liu.  The kissing number of the square.  Mathematics Magazine, 68(2):128–133, 1995.
  * [21] Koji M. Kobayashi.  Improved bounds for online dominating sets of trees.  In Yoshio Okamoto and Takeshi Tokuyama, editors, 28th International Symposium on Algorithms and Computation, ISAAC 2017, December 9-12, 2017, Phuket, Thailand, volume 92 of LIPIcs, pages 52:1–52:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
  * [22] John Leech.  The problem of the thirteen spheres.  The Mathematical Gazette, 40(331):22–23, 1956.
  * [23] Christoph Lenzen and Roger Wattenhofer.  Minimum dominating set approximation in graphs of bounded arboricity.  In Distributed Computing, 24th International Symposium, DISC 2010, Cambridge, MA, USA, September 13-15, 2010. Proceedings, pages 510–524, 2010.
  * [24] Richard J. Lipton and Andrew Tomkins.  Online interval scheduling.  In Daniel Dominic Sleator, editor, Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, Arlington, Virginia, USA, pages 302–311. ACM/SIAM, 1994.
  * [25] CL Liu.  Introduction to combinatorial mathematics (1968).  McGraw-Hill, New York, UBKA math, 9:69.
  * [26] K. Schütte and B.L. van der Waerden.  Das problem der dreizehn kugeln.  Mathematische Annalen, 125:325–334, 1952.
  * [27] Peng-Jun Wan, Khaled M. Alzoubi, and Ophir Frieder.  Distributed construction of connected dominating set in wireless ad hoc networks.  Mob. Networks Appl., 9(2):141–149, 2004.
  * [28] Yuli Ye and Allan Borodin.  Elimination graphs.  ACM Trans. Algorithms, 8(2):14:1–14:23, 2012.
  * [29] J. W. T. Youngs.  A lemma on squares.  Amer. Math. Monthly, 46:20–22, 1939.
  * [30] Likuan Zhao.  The kissing number of the regular polygon.  Discrete Mathematics, 188(1):293–296, 1998.
  * [31] Likuan Zhao and Junqin Xu.  The kissing number of the regular pentagon.  Discrete Mathematics, 252:293–298, 05 2002.