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

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2016-02-25T21:52:54.337Z
2016-02-26T01:27:07.217Z
2016-02-26T01:27:07.217Z
David Eppstein
<p>I was wondering if there is any literature on the following problem:</p>

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

<ol>
<li>Insert a new function $f$</li>
<li>Given $k$, query the minimum value of $f(k)$ where $f \in S$</li>
<li>Given $k$, remove an element $f$ where $f(k)$ is equal to the minimum value of $g(k)$ where $g \in S$</li>
</ol>

<p>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)?</p>

CC BY-SA 3.0
2016-02-25T19:22:45.293Z
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.
Kaveh
<ds.data-structures><cg.comp-geom>
Generalized Priority Queues
S. Pek
# Generalized Priority Queues

(Asked by: username_0 on 2016-02-25)

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)?

**Tags:** ds.data-structures, cg.comp-geom

> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2016-02-25. Score: 9 | Accepted answer

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.


---

