[boost] GSoC2010 Sweepline Algorithm

Subject: [boost] GSoC2010 Sweepline Algorithm
From: Andriy Sydorchuk (sydorchuk.andriy_at_[hidden])
Date: 2010-03-30 18:58:12

Hi, Boost Community!

I am interested in participation in GSoC 2010.
The project I liked the most is the generic implementation of Sweepline
Algorithm.

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

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.
   - STL library includes two generic implementations of self-balancing
   binary trees (red-black): map, set.
   I am quite new with Boost library, but probably there are some more
   specific self-balancing binary tree implementations there?
   - For Voronoi diagram and delaunay triangulation input data is set of
   points.
   What about input of the Medial Axis problem?

-- 
Best,
Andrii Sydorchuk