<p>Well. If you can do it with linked list, then just modify it into skip-list. Just make every node in higher level list point to its original node in the bottom list. Viola, you have what you want...</p>

<p>If you are still not convinced - read a good description of a sweeping algorithm (the book by Mark de Berg, Otfried Cheong, Marc van Kreveld and Mark Overmars is a good starting point). Then go back to your problem - and everything should be clear. It is really no more than a slightly modified implementation of a sweeping algorithm.</p>

CC BY-SA 3.0
2012-01-02T21:16:05.307Z
2012-01-02T21:16:05.307Z
Sariel Har-Peled
<p><em>This is a cross-post from <a href="https://stackoverflow.com/questions/8688251/fortunes-algorithm-beach-line-data-structure">stackoverflow</a>. I did not recieve a good answer, I guess it is because the question is more theoretical.</em></p>

<p>I have to implement Fortunes algorithm for constructing Voronoi diagrams.</p>

<p>Important part of the algorithm is a data structure called "Beach Line Data Structure".</p>

<p>It is a binary balanced tree, similar to AVL, but different in a way that data is stored only on the leafs (there are other differences, but are unimportant for the question).</p>

<p>I am not sure how to implement it. Obviously using AVL "as is" will not work because when balancing AVL tree leaf node can become inner node and vice versa.</p>

<p>I also tried to look at some other known data structures at wikipedia, but none suits the needs. I have seen some implementations that do this with a linked list, but this is not good because searching linked list is O(n), and it needs to be O(log n) for the algorithm to be efficient. </p>

<p>I would like to take a look at a description of such data structure. I have no problem in implementing, but inventing a new structure of balanced tree is too much for me.</p>

CC BY-SA 3.0
2012-01-02T22:51:44.220Z
cstheory.stackexchange.com is not for homework help, so I voted to close the question as off topic.  But good luck!
Tsuyoshi Ito
CC BY-SA 3.0
2012-01-02T23:45:52.840Z
Even if this is a homework question, my answer essentially was - go and read the book. So no damage done...
Sariel Har-Peled
CC BY-SA 3.0
2012-01-03T00:32:33.087Z
@Sariel: I agree.  My previous comment was not to blame you, just in case.
Tsuyoshi Ito
CC BY-SA 3.0
2012-01-04T12:10:10.447Z
This question might have been suited for the upcoming [Computer Science Stack Exchange](http://area51.stackexchange.com/proposals/35636/computer-science-non-programming?referrer=pdx8p7tVWqozXN85c5ibxQ2). So, if you like to have a place for questions like this one, please go ahead and help this proposal to take off!
Raphael
<ds.algorithms><ds.data-structures>
Fortunes Algorithm - Beach Line Data Structure
Artium
# Fortunes Algorithm - Beach Line Data Structure

(Asked by: username_0 on 2012-01-02)

*This is a cross-post from [stackoverflow](https://stackoverflow.com/questions/8688251/fortunes-algorithm-beach-line-data-structure). I did not recieve a good answer, I guess it is because the question is more theoretical.*

I have to implement Fortunes algorithm for constructing Voronoi diagrams.

Important part of the algorithm is a data structure called "Beach Line Data Structure".

It is a binary balanced tree, similar to AVL, but different in a way that data is stored only on the leafs (there are other differences, but are unimportant for the question).

I am not sure how to implement it. Obviously using AVL "as is" will not work because when balancing AVL tree leaf node can become inner node and vice versa.

I also tried to look at some other known data structures at wikipedia, but none suits the needs. I have seen some implementations that do this with a linked list, but this is not good because searching linked list is O(n), and it needs to be O(log n) for the algorithm to be efficient.

I would like to take a look at a description of such data structure. I have no problem in implementing, but inventing a new structure of balanced tree is too much for me.

**Tags:** ds.algorithms, ds.data-structures
> **Comments:**
> **username_1**: cstheory.stackexchange.com is not for homework help, so I voted to close the question as off topic.  But good luck!  
> **username_2**: Even if this is a homework question, my answer essentially was - go and read the book. So no damage done...  
> **username_1**: @Sariel: I agree.  My previous comment was not to blame you, just in case.  
> **username_3**: This question might have been suited for the upcoming [Computer Science Stack Exchange](http://area51.stackexchange.com/proposals/35636/computer-science-non-programming?referrer=pdx8p7tVWqozXN85c5ibxQ2). So, if you like to have a place for questions like this one, please go ahead and help this proposal to take off!  

---

## 1 answers

### Answer by username_2 on 2012-01-02. Score: 5

Well. If you can do it with linked list, then just modify it into skip-list. Just make every node in higher level list point to its original node in the bottom list. Viola, you have what you want...

If you are still not convinced - read a good description of a sweeping algorithm (the book by Mark de Berg, Otfried Cheong, Marc van Kreveld and Mark Overmars is a good starting point). Then go back to your problem - and everything should be clear. It is really no more than a slightly modified implementation of a sweeping algorithm.


---

