The complexity of the outer face in arrangements of random segments

Noga Alon; Dan Halperin; Oren Nechushtan; Micha Sharir

doi:10.1145/1377676.1377689

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 proceeding › Conference 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 language	English (US)
Title of host publication	Proceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08
Pages	69-78
Number of pages	10
DOIs	https://doi.org/10.1145/1377676.1377689
State	Published - 2008
Externally published	Yes
Event	24th Annual Symposium on Computational Geometry, SCG'08 - College Park, MD, United States Duration: Jun 9 2008 → Jun 11 2008

Publication series

Name	Proceedings of the Annual Symposium on Computational Geometry

Other

Other	24th Annual Symposium on Computational Geometry, SCG'08
Country/Territory	United States
City	College Park, MD
Period	6/9/08 → 6/11/08

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Geometry and Topology
Computational Mathematics

Keywords

Algorithms
Theory

Access to Document

10.1145/1377676.1377689

Cite this

@inproceedings{49956f2e4bf348a7927073773ae3044e,

title = "The complexity of the outer face in arrangements of random segments",

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.",

keywords = "Algorithms, Theory",

author = "Noga Alon and Dan Halperin and Oren Nechushtan and Micha Sharir",

year = "2008",

doi = "10.1145/1377676.1377689",

language = "English (US)",

isbn = "9781605580715",

series = "Proceedings of the Annual Symposium on Computational Geometry",

pages = "69--78",

booktitle = "Proceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08",

note = "24th Annual Symposium on Computational Geometry, SCG'08 ; Conference date: 09-06-2008 Through 11-06-2008",

}

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. Proceedings of the Annual Symposium on Computational Geometry, pp. 69-78, 24th Annual Symposium on Computational Geometry, SCG'08, College Park, MD, United States, 6/9/08. https://doi.org/10.1145/1377676.1377689

The complexity of the outer face in arrangements of random segments. / Alon, Noga; Halperin, Dan; Nechushtan, Oren et al.
Proceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08. 2008. p. 69-78 (Proceedings of the Annual Symposium on Computational Geometry).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 -

The complexity of the outer face in arrangements of random segments

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this