Balancing expression dags for more efficient lazy adaptive evaluation
arXiv:1710.045763 citationsh-index: 2
AI Analysis
For robust geometric computing, this work provides a more efficient lazy adaptive evaluation method, though it is an incremental improvement.
This paper restructures arithmetic expression dags by balancing consecutive additions or multiplications, achieving asymptotic improvement in running time confirmed experimentally.
Arithmetic expression dags are widely applied in robust geometric computing. In this paper we restructure expression dags by balancing consecutive additions or multiplications. We predict an asymptotic improvement in running time and experimentally confirm the theoretical results. Finally, we discuss some pitfalls of the approach resulting from changes in evaluation order.