Re: [boost] GSoC2010 Sweepline Algorithm

Subject: Re: [boost] GSoC2010 Sweepline Algorithm
From: Thomas Klimpel (Thomas.Klimpel_at_[hidden])
Date: 2010-04-12 14:47:58

Fernando Cacciola wrote:
> Hi Luke,
> 
> > I for some reason had in my mind a veronoi diagram -> medial axis ->
> > straight skeleton progression of algorithm.
> 
> In fact, Aichholzer's original paper specially argues how the straight
> skeleton cosntruction cannot be derived as a voronoi-diagram-like algorithm
> because of the non-locality of the interactions caused by reflex vertices.

I'm not sure that it is impossible to use a modification of Fortune's algorithm for the straight skeleton construction, all I admitted was that a straightforward application of the sweepline paradigm would not work (and that there would be no "beach line" that clearly marks the parts of the construction that are already finished and won't change anymore when the "sweep line" advances).

Especially when using Fortune's algorithm, the reflex vertices could be brought in with a larger angle (such that one of the sides would be parallel to the sweepline), and then shrunk down to the real angle. Of course, this process would make the "beach line" go backwards, and discart some part of the already existing construction. This is not nice, and probably also destroys the prof O(n log(n)) complexity of the algorithm. However, it would still use the sweepline paradigm, and would be identical to Fortune's algorithm in case the polygon is convex.

Regards,
Thomas