Given a set of points P in L_2 , the classic Unit Covering (UC) problem asks to compute the minimum number of unit disks (possibly intersecting) required to cover the points in P, along with a placement of the disks. In this paper, we study an online version of UC in L_2, which we call as Online Unit Covering (OUC) in L_2, or, simply Online Unit Covering (OUC). In OUC, the points arrive online sequentially. Once a point p arrives, a decision needs to be taken - either assign p to a previously placed disk (if possible) or place a new disk to cover p since none of the previously placed disks can cover p. In this setup, once a disk is placed, its placement cannot be altered in future.  We show that competitive ratio of an optimal deterministic online algorithm for OUC is at least 3 and at most 5. 
Given a set of points P in the plane , the classic Unit Covering (UC) problem asks to compute the minimum number of unit disks (possibly intersecting) required to cover the points in P, along with a placement of the disks. In this paper, we study an online version of UC in L_2, which we call as Online Unit Covering (OUC) in L_2, or, simply Online Unit Covering (OUC). In OUC, the points arrive online sequentially. Once a point p arrives, a decision needs to be taken - either assign p to a previously placed disk (if possible) or place a new disk to cover p since none of the previously placed disks can cover p. In this setup, once a disk is placed, its placement cannot be altered in future. Also, the points remain at their places forever. We show that competitive ratio of an optimal deterministic online algorithm for OUC is at least 3 and at most 5. Furthermore, we show that for the input point sequences which are subsets of the infinite square or hexagonal lattices, competitive ratio of an optimal deterministic online algorithm for OUC is at least 2.5 and at most 3. The lower bounds derived in this paper are independent of computational complexity.
R
L_2
the plane
A
Also, the points remain at their places forever.
A
Furthermore, we show that for the input point sequences which are subsets of the infinite square or hexagonal lattices, competitive ratio of an optimal deterministic online algorithm for OUC is at least 2.5 and at most 3. The lower bounds derived in this paper are independent of computational complexity.