Generalized Priority Queues 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:


Insert a new function $f$
Given $k$, query the minimum value of $f(k)$ where $f \in S$
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)?
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.