Time Complexity Question

[zigui-ps]

1. In my knowledge, the time complexity of Fortune's Sweepline algorithm is O(n log n). This algorithm uses a balanced binary search tree(BBST) to insert/delete parabola and to do a binary search in O(log n).

I found that this code uses a linked list, instead of BBST. The linked list makes this code O(n^2), and it means this code will take lots of time to calculate Voronoi Diagram in specific inputs.

Generator of test input is here.

#!/usr/bin/ruby
n = 1000000
n.times do |i|
    puts "%d %d" % [(i+1), -(i+1)]
    puts "%d %d" % [-(i+1), -(i+1)]
end

You can check that your program is almost stopped at this part or this part.

2. Actually, an implementation used linked list will work well in the average case.

[JCash]

What is the actual question? ;)

I think you have a good point here.

I was inspired by many implementations, and one is of course original reference implementation by Steven Fortune. His page is down currently, but I found this version (with well documented changes), and here it uses a linked list as well.

Yes, the linked list is usually the part that takes the most time currently. I've worked hard to optimize the rest of the code, but the wavefront traversal is painful. So far, I've been reluctant to replace the current implementation holding the wavefront, but it might be time to start thinking about it.

My main concerns though are that it will lose too much speed for the smaller, average case with random points (which is why I wrote this library).

I'll try your test example later, and also compare it with the other frameworks I usually test against (e.g. boost)

[zigui-ps]

Oh, I can't believe that Steven Fortune's implementation is O(n^2) with a linked list. If it is true, then this must be the reason that Steven Fortune's code is unavailable.

The question is that I want to check performance when input is generated by my code.

[JCash]

Well, check the link I posted. (And no, it's not the reason why his site is down)

The question is that I want to check performance when input is generated by my code.

Hmm, not sure what you mean here? Do you wish to profile the code?

Edit: Stevens site seems to be up again: https://9p.io/who/sjf/voronoi.tar

[zigui-ps]

Yes. I want to see the Voronoi Diagram code's running time of implementations (including yours). It can be helpful to know the time complexity of these implementations. Additionally, If you run with that input, your code run in almost 10~100 thousand seconds. But O(n log n) implementation with BBST will run in few seconds.

The average-case analysis versus the worst-case analysis is one of the hot topics in real-world algorithms. IMO, mentioning that this code is using a linked list since it can take lots of time in specific cases will be helpful for users.

[JCash]

Yeah, it's a good idea to mention it in the readme.

Do you happen to have any links to other implementations that use BST's? I'd enjoy having it both for researching the topic and also include them in the benchmark tests.

[zigui-ps]

I found 4 implementations that use BST.

1. Jacquesh's implementation. It uses BST without balancing.
2. Dkotsur's implementation. It uses an AVL Tree.
3. Pvigier's implementation. It uses a Red-Black Tree.
4. My implementation. It uses a Splay tree.