<p>The data structure I was looking for is called a <strong>parametric heap</strong>. That is, a heap in which each key is a linear function (a line) instead of a fixed key. The <code>query(x)</code> operation described above corresponds to a <code>find-min(x)</code> operation in a parametric heap. There is a related data structure, called a <strong>kinetic heap</strong>, which is a parametric heap where the parameter, time, only progresses forwards. In other words, once we have a <code>find-min</code>($t_1$) query, we are allowed to ask <code>find-min</code>($t_2$) only if $t_2 \geq t_1$.</p>

<p>As observed by "someone", the parametric heap problem can be reduced to dynamic planar convex hull via point-line duality. </p>

<p>Most of the papers that solve this problem use a semi-dynamic "deletions only" data structure, and then use a dynamization technique of Bentley and Saxe to transform their data structure to also support insertions. (<a href="http://www.sciencedirect.com/science/article/pii/0196677480900152" rel="nofollow">J. L. Bentley and J. B. Saxe, Decomposable searching problems. I: Static-to-dynamic transformation</a>) See also <a href="http://compgeom.cs.uiuc.edu/~jeffe/teaching/datastructures/notes/01-statictodynamic.pdf" rel="nofollow">J$\epsilon$ffe's lecture notes</a> for an overview on how this type of transformation works. </p>

<p>The classic result in this area is due to Overmars and van Leeuwen, <a href="http://www.sciencedirect.com/science/article/pii/002200008190012X" rel="nofollow">Maintenance of configurations in the plane</a>, which achieves $O(\log n)$ query time and $O(\log^2 n)$ (worst case) update time. If we wanted to implement a solution to this problem, this is the version to go with.</p>

<p>However, there have subsequently been several theoretical improvements to the classical result.
At FOCS 99, Chan's paper </p>

<ul>
<li><a href="http://dl.acm.org/citation.cfm?id=363652" rel="nofollow">Dynamic planar convex hull operations in near-logarithmic amortized time</a> </li>
</ul>

<p>gave a data structure with $O(\log^{1+\epsilon} n)$ amortized time for updates.</p>

<p>Later, the following authors (independently) improve the time bounds  to $O(\log n \log \log n)$ for deletions and $O(\log n \log \log \log n)$ for insertions.</p>

<ul>
<li>Brodal and Jacob <a href="http://www.madalgo.au.dk/~gerth/papers/focs02.pdf" rel="nofollow">Dynamic Planar Convex Hull</a> at FOCS 2002</li>
<li><p>Kaplan , Tarjan, and Tsioutsiouliklis <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.18.9174" rel="nofollow">Faster Kinetic Heaps and Their Use in Broadcast Scheduling</a> at SODA 2001</p>

<p>All of the above citations support <code>find-min</code> queries in $O(\log n)$ time. </p></li>
</ul>

<p>Recently, Brodal and Jacob have further improved their results to support updates in $O(\log n)$ amortized time. Their results are quite complicated, and I have only been able to find the full version of their <a href="http://pwgrp1.inf.ethz.ch/Current/DPCH/Journal/topdown.pdf" rel="nofollow">paper in draft form</a>, however, the result is also detailed in <a href="http://www.brics.dk/DS/Ref/BRICS-DS-Ref/BRICS-DS-Ref.html#BRICS-DS-02-3" rel="nofollow">Jacob's Ph.D. Dissertation</a>.</p>

<p>Recently, <a href="http://www.cs.uwaterloo.ca/~tmchan/env_3_11.pdf" rel="nofollow">Chan</a> gave other results related to dynamic planar convex hull queries, including "A fully dynamic data structure for maintaining a set of n points in the plane so that we can find the edges of the convex hull intersecting a query line".</p>

<p>On a word-RAM, <a href="http://people.csail.mit.edu/mip/papers/dynhull/paper.pdf" rel="nofollow">Demaine and Pătraşcu</a> show that the optimal query time is $\Theta(\log n / \log \log n)$, and depending on the type of query (zero or one dimensional vs two dimensional), give update times of $O(\log n \log \log n)$ or $O(\log^2 n)$.</p>

CC BY-SA 3.0
2012-04-03T01:57:22.330Z
Oh. No. All these results are very complicated. The original paper of Overmars/Van Leuven (see http://en.wikipedia.org/wiki/Dynamic_convex_hull) is still a gem and can be easily implemented. It is log^2 for some operations. But it is worst case.
Sariel Har-Peled
CC BY-SA 3.0
2012-04-03T02:08:01.800Z
I thought Riko Jacob's thesis had a full version of the proof ? But I agree with Sariel that you should stick to Overmars/Van Leuven
Suresh Venkat
CC BY-SA 3.0
2012-04-03T02:22:53.583Z
@SureshVenkat Why should I stick to Overmars / Van Leuven?
Joe
CC BY-SA 3.0
2012-04-03T02:29:28.890Z
I guess it depends on what you need the algorithm for.
Suresh Venkat
CC BY-SA 3.0
2012-04-03T06:00:46.900Z
On a word-ram, we can get even faster query time: http://people.csail.mit.edu/mip/papers/dynhull/paper.pdf
Joe
CC BY-SA 3.0
2012-04-03T07:08:54.850Z
@Joe: Are you trying to prove something, or write code?  If you need a proof, just cite Chan, Brodel and Jacob, and Kaplan et al.  But if you need actual working code, it's probably best to stick to Overmars and van Leeuwen.  Large constants (and coding time) will overwhelm any asymptotic speedups from the later algorithms.
Jeffε
CC BY-SA 3.0
2012-04-03T19:08:50.450Z
@JɛﬀE Good point. I think other comments may have assumed that I wanted to write code. Obviously it hardly ever pays off to add lots of complication to save a log factor in practice. I want to prove something. I have another problem I started thinking about which basically reduced to the dynamic envelop problem. I wanted to know what the best theoretical results were, and if there was any room for improving them, but my initial literature search didn't have the right keywords. Still, Overmars / Van Leuven is apparently the classical result, so I'll edit my answer to include it.
Joe
CC BY-SA 3.0
2016-01-08T06:46:13.340Z
How exactly do you use the solution to a dynamic convex hull to answer queries about the upper envelope of a set of lines? Some explanation would be very helpful.
Rushil Paul
CC BY-SA 3.0
2016-01-09T07:59:55.833Z
@rushil the short answer is point-line duality. It's not really in scope to explain in a comment. But you can ask a fresh question on cs.stackexhange or here on cstheory if your question is research level
Joe
CC BY-SA 3.0
2012-04-03T00:30:59.183Z
2012-04-03T19:33:30.443Z
2012-04-03T19:33:30.443Z
Joe
<p>"someone" is right.  Timothy Chan's paper "Dynamic Planar Convex Hull Operations in
Near-Logarithmic Amortized Time" appears to solve the problem with insertions/deletions taking $O(\log ^{1+\epsilon}n)$ <strong>amortized</strong> time, and queries taking $O(\log n)$ time.  He solves your problem which is dual to the convex hull problem.</p>

CC BY-SA 3.0
2012-03-29T19:20:07.887Z
Oops, never mind.  It appears you've found a more recent result that I think trumps this.
James King
CC BY-SA 3.0
2012-03-29T19:17:05.813Z
2012-03-29T19:17:05.813Z
James King
<p>There are easy algorithms to calculate the upper envelope of an arrangement of lines in the plane. See e.g. section 2.3 in the survey
<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.126.6346&amp;rep=rep1&amp;type=pdf">Davenport-Schinzel sequences and their geometric applications</a>.</p>

<p>Are there any known algorithms / data structures for the dynamic version of the same problem? That is, we want to maintain the upper envelope of a set of lines in the plane under the following operations:</p>

<ul>
<li>insert$(\ell$): adds line $\ell$ to the set</li>
<li>delete$(\ell)$: removes line $\ell$ from the set</li>
<li>query$(x)$: return the line with $x$ coordinate in the upper envelope. In other words, return the line in the set which is first hit by a vertical downward ray from the point $(x, \infty)$.</li>
</ul>

CC BY-SA 3.0
2012-03-29T18:41:43.553Z
For lines, point-line duality should translate this to a problem about dynamic convex hulls, which is well studied.
someone
CC BY-SA 3.0
2012-03-29T19:14:15.070Z
@someone thanks for your helpful comment! Following that line of reasoning quickly led me to the following reference, which discusses parametric heaps, which appear to be the data structures I'm looking for. http://www.madalgo.au.dk/~gerth/papers/focs02.pdf
Joe
CC BY-SA 3.0
2012-03-29T19:27:13.137Z
See also http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.18.9174 and the references therein.
Joe
CC BY-SA 3.0
2012-04-02T08:55:17.090Z
@Joe: I'm not sure about the etiquette but I think you should make an answer and accept it, to help future readers of this question.
Max
<ds.algorithms><reference-request><ds.data-structures><cg.comp-geom>
Dynamic Upper Envelope of lines in the plane
Joe
# Dynamic Upper Envelope of lines in the plane

(Asked by: username_0 on 2012-03-29)

There are easy algorithms to calculate the upper envelope of an arrangement of lines in the plane. See e.g. section 2.3 in the survey
[Davenport-Schinzel sequences and their geometric applications](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.126.6346&rep=rep1&type=pdf).

Are there any known algorithms / data structures for the dynamic version of the same problem? That is, we want to maintain the upper envelope of a set of lines in the plane under the following operations:

* insert$(\ell$): adds line $\ell$ to the set
* delete$(\ell)$: removes line $\ell$ from the set
* query$(x)$: return the line with $x$ coordinate in the upper envelope. In other words, return the line in the set which is first hit by a vertical downward ray from the point $(x, \infty)$.

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

> **Comments:**
> **username_1**: For lines, point-line duality should translate this to a problem about dynamic convex hulls, which is well studied.  
> **username_0**: @username_1 thanks for your helpful comment! Following that line of reasoning quickly led me to the following reference, which discusses parametric heaps, which appear to be the data structures I'm looking for. http://www.madalgo.au.dk/~gerth/papers/focs02.pdf  
> **username_0**: See also http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.18.9174 and the references therein.  
> **username_2**: @username_0: I'm not sure about the etiquette but I think you should make an answer and accept it, to help future readers of this question.  

---

## 2 answers

### Answer by username_0 on 2012-04-03. Score: 3 | Accepted answer

The data structure I was looking for is called a **parametric heap**. That is, a heap in which each key is a linear function (a line) instead of a fixed key. The `query(x)` operation described above corresponds to a `find-min(x)` operation in a parametric heap. There is a related data structure, called a **kinetic heap**, which is a parametric heap where the parameter, time, only progresses forwards. In other words, once we have a `find-min`($t\_1$) query, we are allowed to ask `find-min`($t\_2$) only if $t\_2 \geq t\_1$.

As observed by "username_1", the parametric heap problem can be reduced to dynamic planar convex hull via point-line duality.

Most of the papers that solve this problem use a semi-dynamic "deletions only" data structure, and then use a dynamization technique of Bentley and Saxe to transform their data structure to also support insertions. ([J. L. Bentley and J. B. Saxe, Decomposable searching problems. I: Static-to-dynamic transformation](http://www.sciencedirect.com/science/article/pii/0196677480900152)) See also [J$\epsilon$ffe's lecture notes](http://compgeom.cs.uiuc.edu/~jeffe/teaching/datastructures/notes/01-statictodynamic.pdf) for an overview on how this type of transformation works.

The classic result in this area is due to Overmars and van Leeuwen, [Maintenance of configurations in the plane](http://www.sciencedirect.com/science/article/pii/002200008190012X), which achieves $O(\log n)$ query time and $O(\log^2 n)$ (worst case) update time. If we wanted to implement a solution to this problem, this is the version to go with.

However, there have subsequently been several theoretical improvements to the classical result.
At FOCS 99, Chan's paper

* [Dynamic planar convex hull operations in near-logarithmic amortized time](http://dl.acm.org/citation.cfm?id=363652)

gave a data structure with $O(\log^{1+\epsilon} n)$ amortized time for updates.

Later, the following authors (independently) improve the time bounds to $O(\log n \log \log n)$ for deletions and $O(\log n \log \log \log n)$ for insertions.

* Brodal and Jacob [Dynamic Planar Convex Hull](http://www.madalgo.au.dk/~gerth/papers/focs02.pdf) at FOCS 2002
* Kaplan , Tarjan, and Tsioutsiouliklis [Faster Kinetic Heaps and Their Use in Broadcast Scheduling](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.18.9174) at SODA 2001

  All of the above citations support `find-min` queries in $O(\log n)$ time.

Recently, Brodal and Jacob have further improved their results to support updates in $O(\log n)$ amortized time. Their results are quite complicated, and I have only been able to find the full version of their [paper in draft form](http://pwgrp1.inf.ethz.ch/Current/DPCH/Journal/topdown.pdf), however, the result is also detailed in [Jacob's Ph.D. Dissertation](http://www.brics.dk/DS/Ref/BRICS-DS-Ref/BRICS-DS-Ref.html#BRICS-DS-02-3).

Recently, [Chan](http://www.cs.uwaterloo.ca/~tmchan/env_3_11.pdf) gave other results related to dynamic planar convex hull queries, including "A fully dynamic data structure for maintaining a set of n points in the plane so that we can find the edges of the convex hull intersecting a query line".

On a word-RAM, [Demaine and Pătraşcu](http://people.csail.mit.edu/mip/papers/dynhull/paper.pdf) show that the optimal query time is $\Theta(\log n / \log \log n)$, and depending on the type of query (zero or one dimensional vs two dimensional), give update times of $O(\log n \log \log n)$ or $O(\log^2 n)$.

> **Comments:**
> **username_3**: Oh. No. All these results are very complicated. The original paper of Overmars/Van Leuven (see http://en.wikipedia.org/wiki/Dynamic_convex_hull) is still a gem and can be easily implemented. It is log^2 for some operations. But it is worst case.  
> **username_4**: I thought Riko Jacob's thesis had a full version of the proof ? But I agree with Sariel that you should stick to Overmars/Van Leuven  
> **username_0**: @SureshVenkat Why should I stick to Overmars / Van Leuven?  
> **username_4**: I guess it depends on what you need the algorithm for.  
> **username_0**: On a word-ram, we can get even faster query time: http://people.csail.mit.edu/mip/papers/dynhull/paper.pdf  
> **username_5**: @username_0: Are you trying to prove something, or write code?  If you need a proof, just cite Chan, Brodel and Jacob, and Kaplan et al.  But if you need actual working code, it's probably best to stick to Overmars and van Leeuwen.  Large constants (and coding time) will overwhelm any asymptotic speedups from the later algorithms.  
> **username_0**: @JɛﬀE Good point. I think other comments may have assumed that I wanted to write code. Obviously it hardly ever pays off to add lots of complication to save a log factor in practice. I want to prove something. I have another problem I started thinking about which basically reduced to the dynamic envelop problem. I wanted to know what the best theoretical results were, and if there was any room for improving them, but my initial literature search didn't have the right keywords. Still, Overmars / Van Leuven is apparently the classical result, so I'll edit my answer to include it.  
> **username_6**: How exactly do you use the solution to a dynamic convex hull to answer queries about the upper envelope of a set of lines? Some explanation would be very helpful.  
> **username_0**: @rushil the short answer is point-line duality. It's not really in scope to explain in a comment. But you can ask a fresh question on cs.stackexhange or here on cstheory if your question is research level  

---

### Answer by username_7 on 2012-03-29. Score: 5

"username_1" is right. Timothy Chan's paper "Dynamic Planar Convex Hull Operations in
Near-Logarithmic Amortized Time" appears to solve the problem with insertions/deletions taking $O(\log ^{1+\epsilon}n)$ **amortized** time, and queries taking $O(\log n)$ time. He solves your problem which is dual to the convex hull problem.

> **Comments:**
> **username_7**: Oops, never mind.  It appears you've found a more recent result that I think trumps this.  

---

