TY - GEN

T1 - Numerical stability of algorithms for line arrangements

AU - Fortune, Steven

AU - Milenkovic, Victor

N1 - Publisher Copyright:
© 1991 ACM.

PY - 1991/6/1

Y1 - 1991/6/1

N2 - We analyze the behavior of two line arrangement algorithms, a sweepline algorithm and an incremental algorithm, in approximate arithmetic. The algorithms have running times O(n2 log n) and O(n2) respectively. We show that each of these algorithms can be implemented to have O(n∈) relative error. This means that each algorithm produces an arrangement realized by a set of pseudolines so that each pseudoline differs from the corresponding line relatively by at most O(n∈). We also show that there is a line arrangement algorithm with O(n2 log n) running time and O(∈) relative error.

AB - We analyze the behavior of two line arrangement algorithms, a sweepline algorithm and an incremental algorithm, in approximate arithmetic. The algorithms have running times O(n2 log n) and O(n2) respectively. We show that each of these algorithms can be implemented to have O(n∈) relative error. This means that each algorithm produces an arrangement realized by a set of pseudolines so that each pseudoline differs from the corresponding line relatively by at most O(n∈). We also show that there is a line arrangement algorithm with O(n2 log n) running time and O(∈) relative error.

UR - http://www.scopus.com/inward/record.url?scp=85054986507&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85054986507&partnerID=8YFLogxK

U2 - 10.1145/109648.109685

DO - 10.1145/109648.109685

M3 - Conference contribution

AN - SCOPUS:85054986507

SN - 0897914260

T3 - Proceedings of the Annual Symposium on Computational Geometry

SP - 334

EP - 341

BT - Proceedings of the Annual Symposium on Computational Geometry

PB - Association for Computing Machinery

T2 - 7th Annual Symposium on Computational Geometry, SCG 1991

Y2 - 10 June 1991 through 12 June 1991

ER -