Numerical stability of algorithms for line arrangements
- 1 January 1991
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 334-341
- https://doi.org/10.1145/109648.109685
Abstract
We analyze the behavior of two line arrangement algorithms,a sweepline algorithm and an incremental algorithm, in approximatearithmetic. The algorithms have running timesO(n2log n) and O(n2) respectively. We show that each ofthese algorithms can be implemented to have O(nffl) relativeerror. This means that each algorithm produces anarrangement realized by a set of pseudolines so that eachpseudoline differs from the corresponding line relatively byat most O(nffl). We also show...Keywords
This publication has 0 references indexed in Scilit: