Re: [boost] GSoC2010 Sweepline Algorithm

Subject: Re: [boost] GSoC2010 Sweepline Algorithm
From: Thomas Klimpel (Thomas.Klimpel_at_[hidden])
Date: 2010-04-09 17:01:12

Andriy Sydorchuk wrote:
> Well lets consider that I know "current virtual construction", but it
> is not so clear how to update it with moving further. For example how we
> should deal with edges that are not visible yet but have influence on the
> "current virtual construction". In the sweepline implementation for voronoi
> diagram our "current virtual construction" lies above the sweepline
> datastructure (union of arcs) and it is mathematically proven that it won't change
> with further algorithm execution.

I didn't mean to deliver a complete algorithm description, I just gave a detailed answer to the question "Are you sure that any of them can be solved with sweepline?". The short answer would have just been "Yes", because I can be sure that they can be solved with sweepline, even if this would not be true.

> For example how we should deal with edges that are not visible
> yet but have influence on the "current virtual construction".

I know that you wrote "for example", so you are probably not especially interested in an answer to this specific question, because the question only serves to illustrate your point that a detailed algorithm description would be handy, but I will answer anyway.

The sweepline algorithm for the Voronoi diagram is called Fortune's algorithm. In Fortune's algorithm, there is both a "beach line" and a "sweep line". (The "beach line" is the set of points that have the same distance to the "sweep line" as the minimum distance to the points left of the "sweep line".) 
1) The "current virtual construction" left of the "beach line" is already finished, so no points or edges left of the "sweep line" have any influence on it, even when the "sweep line" will move further to the right.
2) The "current virtual construction" right of the "beach line" and left of the "sweep line" is still empty, but this property isn't too important. But I guess it will also be satisfied by the sweepline algorithm for "straight skeleton" and "Medial Axis".
3) No points right of the "sweep line" have any influence on the "current virtual construction". This is the important property of any sweepline algorithm.

So, the answer to the question is that edges that are not visible yet means edges that are right of the current sweepline position. By These edges don't have any influence on the "current virtual construction", by definition of the "current virtual construction".

The analogon to the "beach line" for the "straight skeleton" or the "Medial Axis" should be fairly obvious. Other details of the algorithm might be less obvious, but none of these details will pose any fundamental difficulty for the sweepline paradigm.

Regards,
Thomas