Extending Pseudosegment Arrangements by Subdivision

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.

Author	Date Published
Perhaps [2], [1], or Boris Aronov?	unknown

Partial Results:

Chan [2] has proved an upper bound of \(O(n\log n)\).

Related Problems:

References:

[1] 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.

[2] Timothy M. Chan. On levels in arrangements of curves. In Proc. 41th Annu. IEEE Sympos. Found. Comput. Sci., pages 219–227, 2000.

[3] The Open Problems Project, Erik D. Demaine, Joseph S. B. Mitchell, Joseph O’Rourke https://topp.openproblem.net/

Keywords:

Combinatorial Geometry; pseudosegments; pseudolines