The complexity of the outer face in arrangements of random segments

Noga Alon, Dan Halperin, Oren Nechushtan, Micha Sharir

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08
Pages69-78
Number of pages10
DOIs
StatePublished - Dec 12 2008
Externally publishedYes
Event24th Annual Symposium on Computational Geometry, SCG'08 - College Park, MD, United States
Duration: Jun 9 2008Jun 11 2008

Publication series

NameProceedings of the Annual Symposium on Computational Geometry

Other

Other24th Annual Symposium on Computational Geometry, SCG'08
CountryUnited States
CityCollege Park, MD
Period6/9/086/11/08

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Keywords

  • Algorithms
  • Theory

Fingerprint Dive into the research topics of 'The complexity of the outer face in arrangements of random segments'. Together they form a unique fingerprint.

  • Cite this

    Alon, N., Halperin, D., Nechushtan, O., & Sharir, M. (2008). The complexity of the outer face in arrangements of random segments. In Proceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08 (pp. 69-78). (Proceedings of the Annual Symposium on Computational Geometry). https://doi.org/10.1145/1377676.1377689