Abstract
We study data structures for providing ε-approximations of convex functions whose slopes are bounded. Since the queries are efficient in these structures requiring only \(O\left(\log(1/\varepsilon)+\log\log n\right)\) time, we explore different applications of such data structures to efficiently solve problems in clustering and facility location. Our data structures are succinct using only O((1/ε)log2(n)) bits of storage. We show that this is optimal by providing a matching lower bound showing that any data structure providing such an ε-approximation requires at least Ω((1/ε)log2(n)) bits of storage.
This research was partly supported by NSERC.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Agarwal, P.K., Har-Peled, S.: Maintaining the approximate extent measures of moving points. In: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 148–157 (2001)
Bajaj, C.: The algebraic degree of geometric optimization problems. Discrete & Computational Geometry 3, 177–191 (1988)
Bose, P., Maheshwari, A., Morin, P.: Fast approximations for sums of distances, clustering and the Fermat-Weber problem. Computational Geometry: Theory and Apllications 24, 135–146 (2002)
Hoeffding, W.: Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association 58, 13–30 (1963)
Indyk, P.: Sublinear time algorithms for metric space problems. In: Proceedings of the 31st ACM Symposium on Theory of Computing (STOC 1999) (1999)
Indyk, P.: Algorithmic applications of low-distortion geometric embeddings. In: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, pp. 10–33 (2001)
Kleinberg, J.: Two algorithms for nearest neighbour search in high dimensions. In: Proceedings of the 29th ACM Symposium on Theory of Computing (STOC 1997), pp. 599–608 (1997)
Mitrinovic, D.S.: Analytic Inequalities. Springer, New York (1970)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bose, P., Devroye, L., Morin, P. (2003). Succinct Data Structures for Approximating Convex Functions with Applications. In: Akiyama, J., Kano, M. (eds) Discrete and Computational Geometry. JCDCG 2002. Lecture Notes in Computer Science, vol 2866. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-44400-8_10
Download citation
DOI: https://doi.org/10.1007/978-3-540-44400-8_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20776-4
Online ISBN: 978-3-540-44400-8
eBook Packages: Springer Book Archive