Re: [boost] GSoC2010 Sweepline Algorithm

Subject: Re: [boost] GSoC2010 Sweepline Algorithm
From: Thomas Klimpel (Thomas.Klimpel_at_[hidden])
Date: 2010-03-31 06:35:33

Andriy Sydorchuk wrote:
> Basically fast and robust Sweepline Algorithm requires implementation
> of next data structure:
> 1) Event Queue (priority queue).
> 2) Sweep Line (self-balancing binary search tree).
> 3) Output datastructures (voronoi vertices, triangulation edges, etc.).

These are intersting technical questions. I guess the most important thing to do is "writing the proposal for GSoC". But you are certainly right that a good understanding of the technical details helps writing a good proposal (and helps deciding whether you want to work on this problem at all).

> Based on that I got next questions:
> 
>    - Which kind of self-balancing binary trees is better for that kind
>      of approach?
>    I am thinking about Red-Black Trees in prefer to AVL trees,
>    as sweepline algorithm requires more adding and deletion operations.
>    And AVL trees are better for look up operations.

Most implementations I have seen so far simply tried to keep the implementation effort manageable, and made use of existing stl containers, using suitable custom comparison functors.

>    - STL library includes two generic implementations of self-balancing
>    binary trees (red-black): map, set.

Indeed.

>    I am quite new with Boost library, but probably there are some more
>    specific self-balancing binary tree implementations there?

Boost.Intrusive could also be intersting to look at.

>    - For Voronoi diagram and delaunay triangulation input data is set
>      of points.
>    What about input of the Medial Axis problem?

Strictly speaking, a single polygon (with potential holes). However, the actual input is often a polygonal domain (= set of non-overlapping polygons), and the output is normally equivalent to computing the medial axis for each polygon of the polygonal domain separately.

Regards,
Thomas