Dynamic Algorithm

I have created this blog account long time back.

But never found time and energy to jot down my thoughts.

Recently Sam-da(Sambuddha Roy, My colleague at IRL) suggested me to write a blog on the problems that I am working on.

Hence, the effort starts. :)

Today I will talk about Dynamic Geometric Algorithms(DGA). I need to do a literature survey whether there exists any algorithms like this. But first, let's start from scratch.

So, what is this DGA? Generally, all the geometric algorithms that I have studied are for static points. I didnot find any algorithm that discusses the same when the points are moving. So, my question is given n moving points, how will their convex hull(CH) or Voronoi Diagram(VD) or Ham-Sandwich cut will change? It appears that for Ham Sandwich cut things are simple. But I am not too sure about VD and CH.

SO, these are the open problems to me now:

1. Given start position of n moving points can we do some precomputation so that at t=T for any given point we can say which point is its closest?

2. Given start position of n moving points can we do some precomputation so that at t=T we can say which points are on the convex hull?

I have to think more on this domain of dynamic algorithms.

Your suggestion and algorithms are welcome.

Signing off,

AK