Sublinear but simple Dynamic Convex Hull algorithm?

I think what you seek does not exist. The Overmars and vanLeeuwen algorithm is not that complicated, and it seems in some sense necessary. First, change the problem to maintaining the upper hull and the lower hull separately.

Second, construct each by divide-and-conquer, but retain the intermediate tree structures, so that you know the hulls of the 1/2-sets, the 1/4-sets, etc. Now, when you delete a point, you recompute only its ancestors in the tree. When you add a point, you find out to which leaf it joins, and again recomputed upwards to the root.

Up vote 6 down vote favorite 4 share g+ share fb share tw.

I need to solve dynamic convex hull algorithm problem, i.e. Maintaining the convex hull of 2D points, where I can add and delete points. The naive approach is clearly O(N); whenever one of the N points is added/deleted, we recompute the convex hull from scratch.

However, I cannot afford linear time, so I am looking for a sublinear algorithm. So far, I have found a bunch of paper all of which describe some sophisticated algorithm with crazy time bounds which would take ages to implement. Even the oldest efficient algorithm, due to Overmars and Leeuween, which is O(log^2 N) seems way too complicated.

(As usual, most of algorithms described in such papers have tons of dependencies in terms of structures/algorithms from other, referenced papers) I am looking for something simpler, not necessarily novel, which performs better than linear in the worst case (e.g. O(sqrt N)). Finally, I don't mind if the time is amortized. Any ideas?

(By simple, I primarily mean something that does not require more than a few hundred lines of code. ) algorithm dynamic complexity computational-geometry convex-hull link|improve this question asked Feb 23 at 9:26leden1,068313 77% accept rate.

1 I would not say the linear complexity solution is naive as finding the convex hull of N points in linear time is naive. In fact I do not know such algorithm that can solve the problem even for a single set in linear time. – izomorphius Feb 23 at 12:56 izo is correct: There is a Omega( n log n ) lower bound (under the most common computational model).

– Joseph O'Rourke Feb 23 at 22:04 By O(N), I mean the cost per operation. The naive approach is maintaining the points sorted and doing Graham scan in O(N) in each step (after each removal/insertion). – leden Feb 24 at 6:25.

I think what you seek does not exist. The Overmars and vanLeeuwen algorithm is not that complicated, and it seems in some sense necessary. First, change the problem to maintaining the upper hull and the lower hull separately.

Second, construct each by divide-and-conquer, but retain the intermediate tree structures, so that you know the hulls of the 1/2-sets, the 1/4-sets, etc. Now, when you delete a point, you recompute only its ancestors in the tree. When you add a point, you find out to which leaf it joins, and again recomputed upwards to the root. I think if you ignore the details in their paper, and just follow this high-level sketch, and implement all the steps in the most mindless manner, it will not be complicated, and will be sublinear.

M. H. Overmars and J.

Van Leeuwen. Maintenance of configurations in the plane. J.

Comput. Syst. Sci.

, 23:166-204, 1981.

Also In addition to your answer, in many cases understanding papers details is harder than their implementation. – Saeed Amiri Feb 23 at 19:31.

With respect to Prof. O'Rourke, who knows far more than I ever will about computational geometry, I don't see how a "mindless" implementation of OvL (i.e. , one lacking rebalancing) could be sublinear in the worst case. Fortunately, we've made some advances in data structures since 1981.

In particular, since an amortized guarantee is enough, splay trees (1985) are appropriate for storing both convex hulls and the merge tree. Austern et al. (2003) proposed a nice way to separate the maintenance of the extra fields that will be required from the complex balancing operations, so you can write the tricky parts once.

The main difficulty in implementing splay trees is the splay operation, and even that is much simpler than, say, inserting into a red-black tree. Once splay works, splay trees are easy to split and join. To split, splay the node you want to split after and cut its right child.

To join, splay the rightmost node of the first tree and make the second tree the right child of that node.

– leden Feb 23 at 16:45 Yes, I stand corrected: Rebalancing would be necessary, else a bad sequence will turn the tree into a path. One could still defer rebalancing until needed, but also one could use, as you say, splay trees. – Joseph O'Rourke Feb 23 at 22:03.

I am assuming that there are N data points in total and the complex hull is defined by M points. It should be far easier (and less expensive) to maintain a Convex Hull than to build it in the first place. Removing an existing data point 1/ If the data point in not one of the M points defining the convex hull then it won’t affect the hull so just remove it.

2/ If it is part of the convex hull then you need to adjust the hull – more on that below in point 4 Adding a new data point. 3/ If a data point is inside the complex hull then it will not affect the hull. Here is a simple way to test this off the top of my head.

Create a triangulation of the interior of the hull. A complex hull defined using M points can be triangulated into M-2 triangles. Then test if the point lies in one of the triangles.

4/ if a data point is outside the hull then it will become part of the hull. However, it is only affecting a local area of the hull and it is straightforward to find the new hull in a few steps. If you have already build the hull then it should be clear to you how to adjust a local part of it.

I don’t see how any of this maintenance can be O(N).

Observe that a removal can cause O(N) points on the hull to be removed from the hull. The same is with insertion, which can cause O(N) new points to become a part of the hull. – leden Feb 24 at 6:30.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.