Clustering Geometrically-Modeled Points in the Aggregated Uncertainty Model

• Autorzy: Keikha Vahideh , Aghamolaei Sepideh , Mohades Ali , Ghodsi Mohammad

Identyfikatory

DOI

10.3233/FI-2021-2097

• Języki publikacji: EN

Abstrakty

EN

The k -center problem is to choose a subset of size k from a set of n points such that the maximum distance from each point to its nearest center is minimized. Let Q = {Q 1 , . . . , Q n } be a set of polygons or segments in the region-based uncertainty model, in which each Q i is an uncertain point, where the exact locations of the points in Q i are unknown. The geometric objects such as segments and polygons can be models of a point set. We define the uncertain version of the k -center problem as a generalization in which the objective is to find k points from Q to cover the remaining regions of Q with minimum or maximum radius of the cluster to cover at least one or all exact instances of each Q i , respectively. We modify the region-based model to allow multiple points to be chosen from a region, and call the resulting model the aggregated uncertainty model . All these problems contain the point version as a special case, so they are all NP-hard with a lower bound 1.822 for the approximation factor. We give approximation algorithms for uncertain k -center of a set of segments and polygons. We also have implemented some of our algorithms on a data-set to show our theoretical performance guarantees can be achieved in practice.

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 184, nr 3
• Strony: 205--231
• Opis fizyczny: Bibliogr. 48 poz., rys., tab., wykr.

Twórcy

autor

Keikha Vahideh

autor

Aghamolaei Sepideh

autor

Mohades Ali

autor

Ghodsi Mohammad

Bibliografia

• [1] Vazirani VV. Approximation algorithms. Springer Science & Business Media, 2013. doi:10.1007/978-3-662-04565-7.
• [2] Feder T, Greene D. Optimal algorithms for approximate clustering. In: Proc. 20th Annu. ACM Sympos. Theory Comput. ACM, 1988 pp. 434-444. doi:10.1145/62212.62255.
• [3] Salesin D, Stolfi J, Guibas L. Epsilon geometry: building robust algorithms from imprecise computations. In: Proc. 5th Annu. ACM Sympos. Comput. Geom. ACM, 1989 pp. 208-217. doi:10.1145/73833.73857.
• [4] Löffler M. Data imprecision in computational geometry. Ph.D. thesis, Utrecht Univesity, 2009.
• [5] Cormode G, McGregor A. Approximation algorithms for clustering uncertain data. In: Proc. 27th ACM SIGMOD-SIGACT-SIGAI Sympos. Princ. Database Syst. ACM, 2008 pp. 191-200. doi:10.1145/1376916.1376944.
• [6] Suri S, Verbeek K, Yıldız H. On the most likely convex hull of uncertain points. In: Proc. 21st Annu. European Sympos. Algorithms. Springer, 2013 pp. 791-802. doi:10.1007/978-3-642-40450-4_67.
• [7] Agarwal PK, Procopiuc CM, Varadarajan KR. Approximation algorithms for a k-line center. Algorithmica, 2005. 42(3-4):221-230. doi:10.1007/s00453-005-1166-x.
• [8] Sadhu S, Roy S, Nandy SC, Roy S. Linear time algorithm to cover and hit a set of line segments optimally by two axis-parallel squares. Theoret. Comput. Sci., 2019. 769:63-74. doi:10.1016/j.tcs.2018.10.013.
• [9] Du H, Xu Y. An approximation algorithm for k-center problem on a convex polygon. J. Comb. Optim., 2014. 27(3):504-518. doi:10.1007/s10878-012-9532-5.
• [10] Basappa M, Jallu RK, Das GK. Constrained k-center problem on a convex polygon. In: Proc. 15th Int. Conf. on Comput. Sci. Appl. Springer, 2015 pp. 209-222. doi:10.1007/978-3-319-21407-8_16.
• [11] Edalat A, Lieutier A, Kashe E. The convex hull in a new model of computation. In: Proc. 13th Canad. Conf. Computat. Geom. 2001.
• [12] Löffler M, van Kreveld M. Largest and smallest convex hulls for imprecise points. Algorithmica, 2010. 56(2):235-269. doi:10.1007/s00453-008-9174-2.
• [13] Löffler M, van Kreveld M. Largest bounding box, smallest diameter, and related problems on imprecise points. Comput. Geom., 2010. 43(4):419-433. doi:10.1016/j.comgeo.2009.03.007.
• [14] Keikha V, Löffler M, Mohades A. Largest and Smallest Area Triangles on Imprecise Points. arXiv preprint arXiv:1712.08911, 2017. doi:10.1016/j.comgeo.2020.101742.
• [15] Mukhopadhyay A, Kumar C, Greene E, Bhattacharya B. On intersecting a set of parallel line segments with a convex polygon of minimum area. Inform. Process. Lett., 2008. 105(2):58-64. doi:10.1016/j.ipl.2007.08.029.
• [16] Rappaport D. Minimum polygon transversals of line segments. Int. J. of Comput. Geom. Appl., 1995. 5(03):243-256.
• [17] Boissonnat JD, Lazard S. Convex hulls of bounded curvature. 1996.
• [18] Huang L, Li J. Stochastic k-center and j-flat-center problems. In: Proc. 28th ACM-SIAM Sympos. Discrete Algorithms. SIAM, 2017 pp. 110-129. doi:10.1137/1.9781611974782.8.
• [19] Wang H, Zhang J. One-dimensional k-center on uncertain data. Theoret. Comput. Sci., 2015. 602:114-124. doi:10.1007/978-3-319-08783-2_10.
• [20] Wang H, Zhang J. Computing the Rectilinear Center of Uncertain Points in the Plane. Int. J. of Comput. Geom. Appl., 2018. 28(03):271-288. doi:10.1142/S0218195918500073.
• [21] Khelifa B, Haffaf H, Madjid M, Llewellyn-Jones D. Monitoring connectivity in wireless sensor networks. In: 2009 IEEE Symposium on Computers and Communications. IEEE, 2009 pp. 507-512. doi:10.1109/ISCC.2009.5202236.
• [22] Kloder S, Hutchinson S. Barrier coverage for variable bounded-range line-of-sight guards. In: Proceedings 2007 IEEE International Conference on Robotics and Automation. IEEE, 2007 pp. 391-396. doi:10.1109/ROBOT.2007.363818.
• [23] Bopardikar SD, Bullo F, Hespanha JP. On discrete-time pursuit-evasion games with sensing limitations. IEEE Transactions on Robotics, 2008. 24(6):1429-1439. doi:10.1109/TRO.2008.2006721.
• [24] Gonzalez TF. Handbook of approximation algorithms and metaheuristics. Chapman and Hall/CRC, 2007. ISBN:978-1-58488-550-4.
• [25] Megiddo N. Linear-time algorithms for linear programming in R3 and related problems. SIAM J. Comput., 1983. 12(4):759-776.
• [26] Abellanas M, Hurtado F, Ramos PA. Structural tolerance and Delaunay triangulation. Inform. Process. Lett., 1999. 71(5-6):221-227. doi:10.1016/S0020-0190(99)00107-6.
• [27] Agarwal PK, Kumar N, Sintos S, Suri S. Range-max queries on uncertain data. J. Comput. Systems Sci., 2018. 94:118-134. doi:10.1016/j.jcss.2017.09.006.
• [28] Xue J, Li Y, Janardan R. On the expected diameter, width, and complexity of a stochastic convex hull. Comput. Geom., 2019. 82:16-31. 10. doi:1016/j.comgeo.2019.04.002.
• [29] Khanban A, Edalat A. Computing Delaunay triangulation with imprecise input data. 2003.
• [30] Davari MJ, Edalat A, Lieutier A. The convex hull of finitely generable subsets and its predicate transformer. In: 34th Annu. ACM/IEEE Symp. on Log. in Comput. Sci. IEEE, 2019 pp. 1-14. doi:10.1109/LICS.2019.8785680.
• [31] Kazemi MR, Mohades A, Khanteimouri P. On approximability of minimum color-spanning ball in high dimensions. Discrete Appl. Math., 2019. 279:188-191. doi:10.1016/j.dam.2019.10.016.
• [32] Abellanas M, Hurtado F, Icking C, Klein R, Langetepe E, Ma L, Palop B, Sacrist´an V. Smallest colorspanning objects. In: Proc. 9th Annu. European Sympos. Algorithms. Springer, 2001 pp. 278-289. doi:10.1007/3-540-44676-1_23.
• [33] Huttenlocher DP, Kedem K, Sharir M. The upper envelope of Voronoi surfaces and its applications. Discrete Comput. Geom., 1993. 9(3):267-291. doi:10.1007/BF02189323.
• [34] Sharir M, Agarwal PK. Davenport-Schinzel sequences and their geometric applications. Cambridge university press, 1995. ISBN:9780521470254.
• [35] Bandyapadhyay S, Inamdar T, Pai S, Varadarajan K. A Constant Approximation for Colorful k-Center. In: Proc. 27th Annu. European Sympos. Algorithms. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. doi:10.4230/LIPIcs.ESA.2019.12.
• [36] Har-Peled S. Geometric Approximation Algorithms. 2005.
• [37] Clarkson KL, Varadarajan K. Improved approximation algorithms for geometric set cover. In: Proceedings of the twenty-first annual symposium on Computational geometry. 2005 pp. 135-141. doi:10.1007/s00454-006-1273-8.
• [38] Agarwal PK, Pan J. Near-linear algorithms for geometric hitting sets and set covers. In: Proc. 30th Annu. ACM Sympos. Comput. Geom. ACM, 2014 pp. 271-279. doi:10.1145/2582112.2582152.
• [39] Agarwal PK, Pan J. Near-linear algorithms for geometric hitting sets and set covers. Discrete & Computational Geometry, 2020. 63(2):460-482. doi:10.1007/s00454-019-00099-6.
• [40] Bus N, Garg S, Mustafa NH, Ray S. Tighter estimates for -nets for disks. Comput. Geom., 2016. 53:27-35. doi:10.1016/j.comgeo.2015.12.002.
• [41] Mustafa NH, Ray S. Improved results on geometric hitting set problems. Discrete Comput. Geom., 2010. 44(4):883-895. doi:10.1007/s00454-010-9285-9.
• [42] Durocher S, Fraser R. Duality for geometric set cover and geometric hitting set problems on pseudodisks. In: Proc. 27th Canad. Conf. Computat. Geom. 2015 pp. 8-16.
• [43] Buchin K, Chun J, Löffler M, Markovic A, Meulemans W, Okamoto Y, Shiitada T. Folding free-space diagrams: Computing the Fr´echet distance between 1-dimensional curves (multimedia contribution). In:Proc. 33rd Annu. ACM Sympos. Comput. Geom. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2017. doi:10.4230/LIPIcs.SoCG.2017.64.
• [44] Malkomes G, Kusner MJ, Chen W, Weinberger KQ, Moseley B. Fast distributed k-center clustering with outliers on massive data. In: Advances in Neural Information Processing Systems. 2015 pp. 1063-1071.ID:9666048.
• [45] Cho E, Myers SA, Leskovec J. Friendship and mobility: user movement in location-based social networks. In: Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining. 2011 pp. 1082-1090. doi:10.1145/2020408.2020579.
• [46] Leskovec J, Krevl A. SNAP Datasets: Stanford Large Network Dataset Collection. http://snap.stanford.edu/data, 2014
• [47] Ceccarello M, Pietracaprina A, Pucci G. Solving kcenter Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially. Proc. of the VLDB Endow., 2019. 12(7):766-778. doi:10.14778/3317315.3317319.
• [48] Aghamolaei S, Ghodsi M. A Composable Coreset for k-Center in Doubling Metrics. In: Conference on Computational Geometry (CCCG 2018). 2018 p. 165. arXiv:1902.01896 [cs.DS].

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023). (PL)