I was wondering if there is any literature on the following problem:

Maintain a set $S$ where each element is a function from $\mathbb{R}$ to $\mathbb{R}$ supporting the following operations:

  1. Insert a new function $f$
  2. Given $k$, query the minimum value of $f(k)$ where $f \in S$
  3. Given $k$, remove an element $f$ where $f(k)$ is equal to the minimum value of $g(k)$ where $g \in S$

Are there restricted classes of functions where we can query and update in $o(|S|)$ time? Are there faster solutions when we restrict to operations (1) and (2)?

  • $\begingroup$ An arbitrary function over reals (or even natural numbers) is an infinite object, you cannot store it. If you have finite functions then simply make one heap for each $k$ and augment them with bidirectional links between nodes of each function. $\endgroup$ – Kaveh Feb 25 '16 at 19:22

You will need to make some assumptions about what kinds of functions are allowed to get anywhere with this.

The version of the problem where the elements of $S$ are linear functions from $\mathbb{R}$ to $\mathbb{R}$ has been studied, in a projectively dual form: if you think of each linear function $y=ax+b$ as being coordinatized by the pair of parameters $(a,b)$, and reinterpret that pair as the Cartesian coordinates of a point, then finding the minimizer for a given $x$ becomes the problem of minimizing a linear function over a dynamic set of two-dimensional points. This can be handled in polylog time per update by a dynamic convex hull data structure, such as the one by Overmars and van Leeuwen 1981 or its more recent improvements by Timothy Chan.

Piecewise-linear functions can be handled by using a weight-balanced segment tree on the set of breakpoints of the functions to replace each query on a set of piecewise-linear functions by logarithmically many queries on subsets of linear functions. This duality approach can also be generalized to higher degree polynomials instead of linear functions but at the expense of turning the problem into a range searching problem in more than two dimensions, for which the time per update will be significantly higher.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.