×

Streaming algorithms for extent problems in high dimensions. (English) Zbl 1314.68392

Summary: We present (single-pass) streaming algorithms for maintaining extent measures of a stream \(S\) of \(n\) points in \(\mathbb{R} ^{d}\). We focus on designing streaming algorithms whose working space is polynomial in \(d\) (poly(\(d\))) and sub-linear in \(n\). For the problems of computing diameter, width and minimum enclosing ball of \(S\), we obtain lower bounds on the worst-case approximation ratio of any streaming algorithm that uses poly(\(d\)) space. On the positive side, we introduce the notion of blurred ball cover and use it for answering approximate farthest-point queries and maintaining approximate minimum enclosing ball and diameter of \(S\). We describe a streaming algorithm for maintaining a blurred ball cover whose working space is linear in \(d\) and independent of \(n\).

MSC:

68W25 Approximation algorithms
68Q25 Analysis of algorithms and problem complexity
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Agarwal, P.K., Har-Peled, S., Varadarajan, K.R.: Approximating extent measures of points. J. ACM 51, 606-635 (2004) · Zbl 1204.68240 · doi:10.1145/1008731.1008736
[2] Agarwal, P. K.; Har-Peled, S.; Varadarajan, K. R.; Goodman, J. (ed.); Pach, J. (ed.); Welzl, E. (ed.), Geometric approximation via coresets, 1-30 (2005), Cambridge · Zbl 1123.68141
[3] Agarwal, P.K., Matoušek, J., Suri, S.: Farthest neighbors, maximum spanning trees and related problems in higher dimensions. Comput. Geom. 1, 189-201 (1992) · Zbl 0769.68037 · doi:10.1016/0925-7721(92)90001-9
[4] Agarwal, P. K.; Yu, H., A space-optimal data-stream algorithm for coresets in the plane, 1-10 (2007) · Zbl 1209.68573
[5] Aggarwal, C.: Data Streams: Models and Algorithms. Springer, Berlin (2007) · Zbl 1126.68033 · doi:10.1007/978-0-387-47534-9
[6] Alon, N., Matias, Y., Szegedy, M.: The space complexity of approximating the frequency moments. J. Comput. Syst. Sci. 58, 137-147 (1999) · Zbl 0938.68153 · doi:10.1006/jcss.1997.1545
[7] Andoni, A.; Croitoru, D.; Patrascu, M., Hardness of nearest neighbor under L-infinity, 424-433 (2008)
[8] Ball, K., An elementary introduction to modern convex geometry, No. 31, 1-58 (1997) · Zbl 0901.52002
[9] Bădoiu, M., Clarkson, K.L.: Optimal core-sets for balls. Comput. Geom. 40, 14-22 (2008) · Zbl 1138.68056 · doi:10.1016/j.comgeo.2007.04.002
[10] Bădoiu, M.; Har-Peled, S.; Indyk, P., Approximate clustering via core-sets, 250-257 (2002) · Zbl 1192.68871
[11] Chan, T.M.: Approximating the diameter, width, smallest enclosing cylinder, and minimum-width annulus. Int. J. Comput. Geom. Appl. 12, 67-85 (2002) · Zbl 1152.68659 · doi:10.1142/S0218195902000748
[12] Chan, T.M.: Faster core-set constructions and data-stream algorithms in fixed dimensions. Comput. Geom. 35, 20-35 (2006) · Zbl 1103.65064 · doi:10.1016/j.comgeo.2005.10.002
[13] Chan, T. M.; Pathak, V., Streaming and dynamic algorithms for minimum enclosing balls in high dimensions, 195-206 (2011) · Zbl 1342.68356 · doi:10.1007/978-3-642-22300-6_17
[14] Chazelle, B., Edelsbrunner, H., Grigni, M., Guibas, L., Sharir, M., Welzl, E.: Improved bounds on weak ε-nets for convex sets. Discrete Comput. Geom. 13, 1-15 (1995) · Zbl 0822.68110 · doi:10.1007/BF02574025
[15] Chazelle, B., Matoušek, J.: On linear-time deterministic algorithms for optimization problems in fixed dimension. J. Algorithms 21, 579-597 (1996) · Zbl 0864.68040 · doi:10.1006/jagm.1996.0060
[16] Clarkson, K.L.: Las Vegas algorithms for linear and integer programming when the dimension is small. J. ACM 42, 488-499 (1995) · Zbl 0885.65063 · doi:10.1145/201019.201036
[17] Clarkson, K. L., Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm, 922-931 (2008) · Zbl 1192.90142
[18] Clarkson, K.L., Shor, P.W.: Applications of random sampling in computational geometry, II. Discrete Comput. Geom. 2, 195-222 (1987) · Zbl 0615.68037 · doi:10.1007/BF02187879
[19] Clarkson, K. L.; Woodruff, D. P., Numerical linear algebra in the streaming model, 205-214 (2009) · Zbl 1304.65138 · doi:10.1145/1536414.1536445
[20] Gärtner, B.; Jaggi, M., Coresets for polytope distance, 33-42 (2009) · Zbl 1380.68396 · doi:10.1145/1542362.1542370
[21] Goel, A.; Indyk, P.; Varadarajan, K., Reductions among high dimensional proximity problems, 769-778 (2001) · Zbl 0988.65022
[22] Har-Peled, S.; Varadarajan, K. R., Projective clustering in high dimensions using core-sets, 312-318 (2003) · Zbl 1414.68124
[23] Indyk, P., Better algorithms for high-dimensional proximity problems via asymmetric embeddings, 539-545 (2003) · Zbl 1092.68691
[24] Kumar, P., Mitchell, J.S.B., Yildirim, E.A.: Approximate minimum enclosing balls in high dimensions using core-sets. ACM J. Exp. Algorithmics 8, 1.1 (2003) · Zbl 1083.68138
[25] Kumar, P., Yildirim, E.A.: Minimum-volume enclosing ellipsoids and core sets. J. Optim. Theory Appl. 126, 1-21 (2005) · Zbl 1093.90039 · doi:10.1007/s10957-005-2653-6
[26] Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, Cambridge (1997) · Zbl 0869.68048 · doi:10.1016/S0065-2458(08)60342-3
[27] Matoušek, J., Sharir, M., Welzl, E.: A subexponential bound for linear programming. Algorithmica 16, 498-516 (1996) · Zbl 0857.68119 · doi:10.1007/BF01940877
[28] Muthukrishnan, S.: Data Streams: Algorithms and Applications. Now Publishers, Hanover (2005) · Zbl 1128.68025
[29] Ramos, E.A.: An optimal deterministic algorithm for computing the diameter of a three-dimensional point set. Discrete Comput. Geom. 26, 233-244 (2001) · Zbl 0992.68229 · doi:10.1007/s00454-001-0029-8
[30] Zarrabi-Zadeh, H.; Chan, T., A simple streaming algorithm for minimum enclosing balls, 139-142 (2006)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.