Back to Search
Start Over
Two-center of the Convex Hull of a Point Set: Dynamic Model, and Restricted Streaming Model.
- Source :
- Fundamenta Informaticae; 2019, Vol. 164 Issue 1, p119-138, 20p
- Publication Year :
- 2019
-
Abstract
- In this paper, we consider the dynamic version of covering the convex hull of a point set P in R<superscript>2</superscript> 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 ≤ 2r<subscript>opt</subscript> at any query time, where r<subscript>opt</subscript> 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. [ABSTRACT FROM AUTHOR]
- Subjects :
- POINT set theory
CONVEX bodies
DATA structures
PHYSICAL constants
PROBLEM solving
Subjects
Details
- Language :
- English
- ISSN :
- 01692968
- Volume :
- 164
- Issue :
- 1
- Database :
- Complementary Index
- Journal :
- Fundamenta Informaticae
- Publication Type :
- Academic Journal
- Accession number :
- 134189494
- Full Text :
- https://doi.org/10.3233/FI-2019-1757