**Next:** Problem 35: Freeze-Tag: Optimal Strategies for Awakening a Swarm of Robots

**Previous:** Problem 33: Sum of Square Roots

- Statement
How many intersections among an arrangement of pseudosegments in the plane must be added as vertices to allow the pseudosegment arrangment to be extended to a pseudoline arrangement?

An

*arrangement of pseudosegments*in the plane is a family of finite-length planar curves such that every two curves intersect in at most one point. An*arrangement of pseudolines*in the plane is a family of planar curves that extend to infinity on both ends such that every two curves intersect in at most one point. Only some pseudosegment arrangements can be*extended*to pseudoline arrangements. However, if we allow turning intersection points into vertices of the arrangement, thereby subdividing the segments, then it is always possible to make a pseudosegment arrangement extendible. The question is how many such vertices must be added in the worst-case in terms of the number n of pseudosegments.- Origin
- Status/Conjectures
Open.

- Partial and Related Results
Chan [Cha00a] has proved an upper bound of O(n \log n).

- Appearances
Posed by Boris Aronov during the open problem session at the Fall Workshop on Computational Geometry, Brooklyn, NY, Nov. 2–3, 2001.

- Categories
combinatorial geometry

- Entry Revision History
E. Demaine, 20 Nov. 2001.

- [AACS98]
P. K. Agarwal, Boris Aronov, T. M. Chan, and Micha Sharir. On levels in arrangements of lines, segments, planes, and triangles.

*Discrete Comput. Geom.*, 19:315–331, 1998.- [Cha00a]
Timothy M. Chan. On levels in arrangements of curves. In

*Proc. 41th Annu. IEEE Sympos. Found. Comput. Sci.*, pages 219–227, 2000.