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(log(1/ε)+log log n) 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/ε) log 2(n)) bits of storage.

Additional Metadata
Citation
Bose, P, Devroye, L. (Luc), & Morin, P. (2003). Succinct data structures for approximating convex functions with applications.