Re: [Boost-users] [Polygon] Test among 3 libraries

Subject: Re: [Boost-users] [Polygon] Test among 3 libraries
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2010-09-10 19:45:28

Angus Johnson wrote:
>>   There is a pretty significant difference between making the
>> sub-optimal sweepline algorithm numerically robust and the optimal
>> tree based sweepline algorithm numerically robust, so you might want
>> to step back and decide whether you are looking to improve the
>> robustness of your current algorithm or to improve the algorithm
>> then come back to robustness.     
> 
> I believe my current algorithm (which very closely adhers to Vatti's
> data structure) is close to maximally efficient. The data structure at
> least doesn't need touching but no doubt the implementation can
> always be improved.

Your empirical measurement of y = 1E-08x^1.4821 scaling is almost the exact scaling factor of 1.5 I would expect a sub-optimal sweepline algorithm to exhibit for the test case you described.  Like I said, O(n log n) corresponds to scaling factor of less than 1.1.  1.48 is equivalent to an algorithmic complexity of O(n * sqrt(n)).  1.5 is a lot slower than 1.05 once you get over one million (like 500X slower) so this is a big issue.  No matter how efficient your implementation it can't compete with an more optimal algorithm on larger tests cases.  The data structure used for delivering the sorted sequence of edges to the sweepline is less important than the data structre used for the active edge list (which should be a tree and not a list).  Please read the references of my boostcon paper http://www.boost.org/doc/libs/1_44_0/libs/polygon/doc/GTL_boostcon2009.pdf, in particular Ruud, B. Building a Mutable Set, 2003. Retrieved March 3, 2009, from Dr. Dobb's Portal: http://www.ddj.com/cpp/184401664 gives a clear description of how to use the std set or map to implement the sweepline data structure.

Regards,
Luke