8
$\begingroup$

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.

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)$.
$\endgroup$
  • 6
    $\begingroup$ For lines, point-line duality should translate this to a problem about dynamic convex hulls, which is well studied. $\endgroup$ – someone Mar 29 '12 at 18:41
  • 2
    $\begingroup$ @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. madalgo.au.dk/~gerth/papers/focs02.pdf $\endgroup$ – Joe Mar 29 '12 at 19:14
  • 3
    $\begingroup$ See also citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.18.9174 and the references therein. $\endgroup$ – Joe Mar 29 '12 at 19:27
  • 1
    $\begingroup$ @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. $\endgroup$ – Max Apr 2 '12 at 8:55
5
$\begingroup$

"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)$ amortized time, and queries taking $O(\log n)$ time. He solves your problem which is dual to the convex hull problem.

$\endgroup$
  • 1
    $\begingroup$ Oops, never mind. It appears you've found a more recent result that I think trumps this. $\endgroup$ – James King Mar 29 '12 at 19:20
3
$\begingroup$

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 "someone", 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) See also J$\epsilon$ffe's lecture notes 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, 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

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.

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, however, the result is also detailed in Jacob's Ph.D. Dissertation.

Recently, Chan 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 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)$.

$\endgroup$
  • 3
    $\begingroup$ Oh. No. All these results are very complicated. The original paper of Overmars/Van Leuven (see 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. $\endgroup$ – Sariel Har-Peled Apr 3 '12 at 1:57
  • 1
    $\begingroup$ 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 $\endgroup$ – Suresh Venkat Apr 3 '12 at 2:08
  • $\begingroup$ @SureshVenkat Why should I stick to Overmars / Van Leuven? $\endgroup$ – Joe Apr 3 '12 at 2:22
  • $\begingroup$ I guess it depends on what you need the algorithm for. $\endgroup$ – Suresh Venkat Apr 3 '12 at 2:29
  • $\begingroup$ On a word-ram, we can get even faster query time: people.csail.mit.edu/mip/papers/dynhull/paper.pdf $\endgroup$ – Joe Apr 3 '12 at 6:00

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.