Two-center of the Convex Hull of a Point Set : Dynamic Model, and Restricted Streaming Model

• Autorzy: Sadhu Sanjib , Roy Sasanka , Nandi Soumen , Maheshwari Anil , Nandy Subhas C.

Identyfikatory

DOI

10.3233/FI-2019-1757

• Języki publikacji: EN

Abstrakty

EN

In this paper, we consider the dynamic version of covering the convex hull of a point set P in ℝ² 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_opt at any query time, where r_opt 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.

Słowa kluczowe

EN

approximation algorithm; computational geometry; dynamic setup; lower bound; two-center problem

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2019
• Tom: Vol. 164, nr 1
• Strony: 119--138
• Opis fizyczny: Bibliogr. 25 poz., rys.

Twórcy

autor

Sadhu Sanjib

• Dept. of Computer Science and Engineering, National Institute of Technology, Durgapur - 713209, India

autor

Roy Sasanka

• Advanced Computing and Microelectronics Unit, Indian Statistical Institute, Kolkata - 700108, India

autor

Nandi Soumen

• Dept. of Computer Science, BITS Pilani, Hyderabad Campus, Telangana - 500078, India

autor

Maheshwari Anil

• School of Computer Science, Carleton University, Ottawa - ON K1S-5B6, Canada

autor

Nandy Subhas C.

• Advanced Computing and Microelectronics Unit, Indian Statistical Institute, Kolkata - 700108, India

Bibliografia

• [1] Marchetti-Spaccamela A. The p center problem in the plane is NP complete. In: In Proc. 19th Allerton Conf. Commun. Control Comput. 1981 pp. 31-40.
• [2] Bespamyatnikh S, Kirkpatrick DG. Rectilinear 2-center problems. In: Proceedings of the 11th Canadian Conference on Computational Geometry (CCCG). 1999 pp. 68-71.
• [3] Chan TM. More planar two-center algorithms. 1999. 13(3):189-198. URL https://doi.org/10.1016/S0925-7721(99)00019-X.
• [4] Eppstein D. Faster construction of planar two-centers. In: 8th ACM-SIAM Symposium On Discrete Algorithms (SODA). 1997 pp. 131-138. ISBN:0-89871-390-0.
• [5] Hershberger J. A fast algorithm for the two-center decision problem. Information Processing Letters (Elsevier), 1993. 47(1):23-29. URL https://doi.org/10.1016/0020-0190(93)90153-Z.
• [6] Jaromczyk JW, Kowaluk M. An efficient algorithm for the euclidean two-center problem. In: Mehlhorn K (ed.), Symposium on Computational Geometry. ACM, 1994 pp. 303-311. doi:10.1145/177424.178038.
• [7] Katz MJ, Kedem K, Segal M. Discrete rectilinear 2-center problems. Comput. Geom., 2000. 15(4):203-214. URL https://doi.org/10.1016/S0925-7721(99)00052-8.
• [8] Sharir M. A near-linear algorithm for the planar 2-center problem. Discrete & Computational Geometry, 1997. 18(2):125-134. doi:10.1007/PL00009311.
• [9] Plesnik J. A heuristic for the p-center problem in graphs. Discrete Applied Mathematics, 1987. 17:263-268. URL https://doi.org/10.1016/0166-218X(87)90029-1.
• [10] Agarwal PK, Sharir M, Welzl E. The discrete 2-center problem. In: Discrete and Computational Geometry, volume 20(3). Springer US, 1998 pp. 238-255. doi:10.1007/PL00009387.
• [11] Kim SK, Shin CS. Efficient algorithms for two-center problems for a convex polygon. In: 6th Annual International Conference, COCOON 2000 Sydney, Australia. Springer Berlin Heidelberg, 2000 pp. 299-309. doi:10.1007/3-540-44968-X_30.
• [12] Agarwal PK, Har-Peled S, Varadarajan KR. Approximating extent measures of points. J. ACM, 2004. 51(4):606-635. doi:10.1145/1008731.1008736.
• [13] Zarrabi-Zadeh H. Core-preserving algorithms. In: CCCG. 2008 pp. 159-162.
• [14] Charikar M, Chekuri C, Feder T, Motwani R. Incremental clustering and dynamic information retrieval. SIAM J. Comput., 2004. 33(6):1417-1440. URL https://doi.org/10.1137/S0097539702418498.
• [15] McCutchen RM, Khuller S. Streaming algorithms for k-center clustering with outliers and with anonymity. In: Approximation, Randomization and Combinatoral Optimization. Algorithms and Techniques, volume 5171. 2008 pp. 165-178. doi:10.1007/978-3-540-85363-3_14.
• [16] Guha S. Tight results for clustering and summarizing data streams. In: 12th International Conference on Database Theory, ACM International Conference Proceeding Series. 2009 pp. 268-275. URL http://repository.upenn.edu/cis_papers.
• [17] Ahn HK, Kim HS, Kim SS, Son W. Computing k Centers over streaming data for small k. Int. J. Comput. Geometry Appl., 2014. 24(2):107-124. URL https://doi.org/10.1142/S0218195914500058.
• [18] Kim SS, Ahn HK. An improved data stream algorithm for clustering. Computational Geometry: Theory and Applications, 2015. 48(9):635-645. URL https://doi.org/10.1016/j.comgeo.2015.06.003.
• [19] Andoni A, Nguyen HL. Width of points in the streaming model. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012. 2012 pp. 447-452.
• [20] Chan TM, Pathak V. Streaming and dynamic algorithms for minimum enclosing balls in high dimensions. Computational Geometry: Theory and Applications, 2014. 47(2):240-247. URL https://doi.org/10.1016/j.comgeo.2013.05.007.
• [21] Chan TM. Dynamic Coresets. Discrete & Computational Geometry, 2009. 42(3):469-488. doi: 10.1007/s00454-009-9165-3.
• [22] Chan TM. Dynamic Streaming Algorithms for Epsilon-Kernels. In: 32nd International Symposium on Computational Geometry, SoCG 2016, June 14-18, 2016, Boston, MA, USA. 2016 pp. 27:1-27:11. doi:10.4230/LIPIcs.SoCG.2016.27.
• [23] Poon CK, Zhu B. Streaming with minimum space: An algorithm for covering by two congruent balls. Theor. Comput. Sci., 2013. 507:72-82. doi:10.1016/j.tcs.2013.02.004.
• [24] Brodal GS, Jacob R. Dynamic Planar Convex Hull. In: 43rd Symposium on Foundations of Computer Science (FOCS 2002), 16-19 November 2002, Vancouver, BC, Canada, Proceedings. 2002 pp. 617-626. ISBN:0-7695-1822-2.
• [25] Chan TM. Dynamic planar convex hull operations in near-logarithmaic amortized time. J. ACM, 2001. 48(1):1-12. doi:10.1145/363647.363652.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).