This is a cross-post from stackoverflow. 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.

  • 2
    $\begingroup$ cstheory.stackexchange.com is not for homework help, so I voted to close the question as off topic. But good luck! $\endgroup$ – Tsuyoshi Ito Jan 2 '12 at 22:51
  • 3
    $\begingroup$ Even if this is a homework question, my answer essentially was - go and read the book. So no damage done... $\endgroup$ – Sariel Har-Peled Jan 2 '12 at 23:45
  • $\begingroup$ @Sariel: I agree. My previous comment was not to blame you, just in case. $\endgroup$ – Tsuyoshi Ito Jan 3 '12 at 0:32
  • $\begingroup$ This question might have been suited for the upcoming Computer Science Stack Exchange. So, if you like to have a place for questions like this one, please go ahead and help this proposal to take off! $\endgroup$ – Raphael Jan 4 '12 at 12:10

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.


Not the answer you're looking for? Browse other questions tagged or ask your own question.