Re: [boost] GSoC2010 Sweepline Algorithm

Subject: Re: [boost] GSoC2010 Sweepline Algorithm
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2010-04-06 20:41:02

Andriy Sydorchuk wrote:
>> That's what I thought.  Why not use a point plus implicit parabola
>> above and below as your sweepline element instead of point pair and
>> implicit parabolas between?  That way instead of two points your
>> element contains only one and inserting a new point doesn't require
>> the removal of any elements.
> 
> 
> The reason is I read such kind of approach in this book:
> "Computational Geometry: Algorithms and Applicatoins" by* *Mark de
> Berg. 
> 
> 
> Quota (page 156): "The beach line is represented by a balanced binary
> search tree T; it is the status structure. Its leaves correspond to
> the arcs of the beach line - which is x-monotone - in an ordered
> manner; the leftmost leaf represents the leftmost arc, the next leaf
> represents the second leftmost arc, and so on. Each leaf L stores the
> site that defines the arc it represents. The internal nodes of T
> represent the breakpoint on the beach line. A breakpoint is stored at
> an internal node by an ordered tuple of sites (pi, pj), where pi
> defines the parabola left of the breakpoint and pj defines the
> parabola to the right". 
> I simplified this approach to be used without leaves, in this case all
> elements of the map will be the same structures.
> 
> Why not use a point...
> 
> Do you mean intersection point of above and below parabolas, or just
> site point?
> If the answer is intersection point, you may skip next questions.
> In case our element contains only one point, how would you implement
> insertion operation? For example we insert new element, how do we
> compare new element with elements from sweep line (we only know site
> point corresponding to the element, it seems to me that this
> information is not enough)?

I see now that your element is actually a bisector of two sites, the moving point at which two parabolas intersect that traces line segments of the veronoi diagram as the sweepline advances.

Regards,
Luke