Moving to exact predicates on top of floating point numbers would be a big speed boost. CGAL does this.