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?
-- Best, Andrii Sydorchuk
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk