3D Snap Rounding

Wed, Jun 19, 2019 12:30 CEST

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})\). But for a use it's already too much. One hope is to design a lazy algorithm that only makes this heavy algorithm where it is needed.