Affiliations: [a] Dept. of Computer Science and Engineering, National Institute of Technology, Durgapur - 713209, India. sanjibsadhu411@gmail.com | [b] Advanced Computing and Microelectronics Unit, Indian Statistical Institute, Kolkata - 700108, India. sasanka@isical.ac.in | [c] Dept. of Computer Science, BITS Pilani, Hyderabad Campus, Telangana - 500078, India. soumen2004@gmail.com | [d] School of Computer Science, Carleton University, Ottawa - ON K1S-5B6, Canada. anil@scs.carleton.ca | [e] Advanced Computing and Microelectronics Unit, Indian Statistical Institute, Kolkata - 700108, India. nandysc@isical.ac.in
Correspondence:
[*]
Address for correspondence: Dept. of Comp. Sci. and Eng., National Institute of Technology, Durgapur-713209, India.
Note: [†] Supported by NSERC.
Note: [‡] Part of the work was done while this author was visiting Carleton University in Fall 2015.
Abstract: In this paper, we consider the dynamic version of covering the convex hull of a point set P in ℝ2 by two congruent disks of minimum size. Here, the points can be added or deleted in the set P, and the objective is to maintain a data structure that, at any instant of time, can efficiently report two disks of minimum size whose union completely covers the boundary of the convex hull of the point set P. We show that maintaining a linear size data structure, we can report a radius r satisfying r ≤ 2ropt at any query time, where ropt is the optimum solution at that instant of time. For each insertion or deletion of a point in P, the update time of our data structure is O(log n). Our algorithm can be tailored to work in the restricted streaming model where only insertions are allowed, using constant work-space. The problem studied in this paper has novelty in two ways: (i) it computes the covering of the convex hull of a point set P, which has lot of surveillance related applications, but not studied in the literature, and (ii) it also considers the dynamic version of the problem. In the dynamic setup, the extent measure problems are studied very little, and in particular, the k-center problem is not at all studied for any k ≥ 2.
