<p>Dorit Dor and Uri Zwick ("Selecting the Median", SODA 1995, pp 28-37) use <strong>green factories</strong> and analyze their amortized production costs.</p>

CC BY-SA 3.0
2016-06-20T14:53:39.433Z
Thank you!  "Green factories" makes more sense than "green forests".
Geoffrey Irving
CC BY-SA 3.0
2016-06-20T08:44:05.700Z
2016-06-20T08:44:05.700Z
Gamow
<p>I have a vague memory of a series of papers working to reduce the constant factor in the number of comparisons for deterministic linear time median finding, using increasingly elaborate (but interesting!) techniques to do so.  </p>

<p>In particular, I remember one of the papers using the term "green forests" for a data structure storing information from previous comparisons (in an attempt to reuse them and avoid future comparisons).</p>

<p>Does this ring any bells?  "median finding green forests" turns out to be a terrible search term.</p>

<reference-request><selection>
Median finding with "green forests"?
Geoffrey Irving
# Median finding with "green forests"?

(Asked by: username_0 on 2016-06-20)

I have a vague memory of a series of papers working to reduce the constant factor in the number of comparisons for deterministic linear time median finding, using increasingly elaborate (but interesting!) techniques to do so.

In particular, I remember one of the papers using the term "green forests" for a data structure storing information from previous comparisons (in an attempt to reuse them and avoid future comparisons).

Does this ring any bells? "median finding green forests" turns out to be a terrible search term.

**Tags:** reference-request, selection


---

## 1 answers

### Answer by username_1 on 2016-06-20. Score: 8 | Accepted answer

Dorit Dor and Uri Zwick ("Selecting the Median", SODA 1995, pp 28-37) use **green factories** and analyze their amortized production costs.

> **Comments:**
> **username_0**: Thank you!  "Green factories" makes more sense than "green forests".  

---

