caa a22 4500 445804246 CHVBK 20180317145152.0 cr unu---uuuuu 170323e20110501xx s 000 0 eng 10.1007/s00453-010-9392-2 doi (NATIONALLICENCE)springer-10.1007/s00453-010-9392-2 Zarrabi-Zadeh Hamid School of Computer Science, University of Waterloo, N2L 3G1, Waterloo, Ontario, Canada aut An Almost Space-Optimal Streaming Algorithm forCoresets inFixed Dimensions [Elektronische Daten] [Hamid Zarrabi-Zadeh] We present a new streaming algorithm for maintaining an ε-kernel of a point set in ℝd using O((1/ε (d−1)/2)log (1/ε)) space. The space used by our algorithm is optimal up to a small logarithmic factor. This significantly improves (for any fixed dimension d ≥3) the best previous algorithm for this problem that uses O(1/ε d−(3/2)) space, presented by Agarwal and Yu. Our algorithm immediately improves the space complexity of the previous streaming algorithms for a number of fundamental geometric optimization problems in fixed dimensions, including width, minimum-volume bounding box, minimum-radius enclosing cylinder, minimum-width enclosing annulus, etc. Springer Science+Business Media, LLC, 2010 Approximation algorithms nationallicence Data streams nationallicence Geometric optimization problems nationallicence Coresets nationallicence Algorithmica Springer-Verlag 60/1(2011-05-01), 46-59 0178-4617 60:1<46 2011 60 453 https://doi.org/10.1007/s00453-010-9392-2 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-010-9392-2 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Zarrabi-Zadeh Hamid School of Computer Science, University of Waterloo, N2L 3G1, Waterloo, Ontario, Canada aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 60/1(2011-05-01), 46-59 0178-4617 60:1<46 2011 60 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer