Re: [boost] GSoC2010 Sweepline Algorithm

Subject: Re: [boost] GSoC2010 Sweepline Algorithm
From: Andriy Sydorchuk (sydorchuk.andriy_at_[hidden])
Date: 2010-04-06 19:04:25

>
> 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)?

-- 
Best regards,
Andrii Sydorchuk