Boost logo

Boost :

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

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
   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
   What about input of the Medial Axis problem?

Andrii Sydorchuk

Boost list run by bdawes at, gregod at, cpdaniel at, john at