A sublinear but simple dynamic convex hull algorithm?

Question

I need to solve the problem of a dynamic convex hull algorithm, i.e. maintain the convex hull of two-dimensional points, where I can add and remove points.

The naive approach is clearly O(N) ; whenever one of the N points is added / removed, we combine 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 a complex algorithm with the crazy time frames that would be required for implementation. Even the oldest efficient algorithm due to Overmars and Leeuween, which O(log^2 N) seems too complicated. (As usual, most of the algorithms described in such works have many dependencies in terms of structures / algorithms from other reference documents)

I am looking for something simpler, not necessarily new, that is better than linear in the worst case (like O(sqrt N) ). Finally, I do not mind if time is amortized. Any ideas?

(By simple, I mean first of all that does not require more than a few hundred lines of code.)

Answer 1

I think what you are looking for does not exist. The Overmars and vanLeeuwen algorithms are not so complex, and this is in a sense necessary. First, change the problem to keeping the upper case and lower case separate. Secondly, build each one by division and subjugation, but keep the intermediate tree structures so that you know the shells of 1/2 sets, 1/4 sets, etc. Now, when you delete a point, you reprogram only your ancestors in the tree. When you add a point, you will find out which sheet it joins, and again recounted up to the root.

I think that if you ignore the details in your article and simply follow this high-level sketch and implement all the steps in the most senseless way, it will not be complicated and will be sublinear.

---

M.H. Overmars and J. Van Leuven. Maintenance of configurations in the plane. J. Comput. Syst. Sci., 23: 166-204, 1981.

Answer 2

As for Professor O'Rourke, who knows much more than ever about computational geometry, I don’t see how the “meaningless” implementation of OvL (i.e., the lack of equilibrium) can be sublinear in the worst case.

Fortunately, since 1981 we have achieved some success in data structures. In particular, since a sufficient guarantee is sufficient, splay trees (1985) are suitable for storing both convex hulls and a merge tree. Austern et al. (2003) suggested a good way to separate the maintenance of additional fields that would be required from complex balancing operations, so you can write complex details once.

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

Answer 3

I assume that there are only N data points, and a complex shell is defined by M-points.

It should be much easier (and less expensive) to maintain a convex hull than to build it in the first place.

Delete 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's an easy way to test it out of my head. Create a triangulation of the inside of the body. A complex shell defined using M points can be triangulated into triangles M-2. Then check if the point is 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 do not see how any of this service can be O (N)