TY - GEN

T1 - The complexity of the outer face in arrangements of random segments

AU - Alon, Noga

AU - Halperin, Dan

AU - Nechushtan, Oren

AU - Sharir, Micha

PY - 2008

Y1 - 2008

N2 - We investigate the complexity of the outer face in arrangements of line segments of a fixed length ℓ in the plane, drawn uniformly at random within a square. We derive upper bounds on the expected complexity of the outer face, and establish a certain phase transition phenomenon during which the expected complexity of the outer face drops sharply as a function of the total number of segments. In particular we show that up till the phase transition the complexity of the outer face is almost linear in n, and that after the phase transition, the complexity of the outer face is roughly proportional to √n. Our study is motivated by the analysis of a practical point-location algorithm (so-called walk-along-a-line point-location algorithm) and indeed, it explains experimental observations of the behavior of the algorithm on arrangements of random segments.

AB - We investigate the complexity of the outer face in arrangements of line segments of a fixed length ℓ in the plane, drawn uniformly at random within a square. We derive upper bounds on the expected complexity of the outer face, and establish a certain phase transition phenomenon during which the expected complexity of the outer face drops sharply as a function of the total number of segments. In particular we show that up till the phase transition the complexity of the outer face is almost linear in n, and that after the phase transition, the complexity of the outer face is roughly proportional to √n. Our study is motivated by the analysis of a practical point-location algorithm (so-called walk-along-a-line point-location algorithm) and indeed, it explains experimental observations of the behavior of the algorithm on arrangements of random segments.

KW - Algorithms

KW - Theory

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

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

U2 - 10.1145/1377676.1377689

DO - 10.1145/1377676.1377689

M3 - Conference contribution

AN - SCOPUS:57349187571

SN - 9781605580715

T3 - Proceedings of the Annual Symposium on Computational Geometry

SP - 69

EP - 78

BT - Proceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08

T2 - 24th Annual Symposium on Computational Geometry, SCG'08

Y2 - 9 June 2008 through 11 June 2008

ER -