Speakers: Leo Valque

Many computational geometry algorithms require greater accuracy for output than for input. So, to send or use the output, we often need to round it off. If this is done naively, intersections can occur during rounding. An algorithm from Devillers, Lenhart, Lazard was presented last year to solve this problem. The worst case of this algorithm is \(O(n^15)\). An implementation of this algorithm shows that on average, it is \(O(n \sqrt{n})\).