Extending pseudosegment arrangements to pseudoline arrangements by subdivision
An arrangement of pseudosegments is a finite family of bounded curves in the plane, any two meeting in at most one point; an arrangement of pseudolines is a family of curves unbounded in both directions, any two meeting in at most one point. A pseudosegment arrangement is extendible if its curves can be extended to the curves of a pseudoline arrangement. Not every pseudosegment arrangement is extendible, but each becomes extendible once enough intersection points are made vertices, cutting the curves through them into shorter pseudosegments.
Chan proved that $O(n \log n)$ such cuts always suffice for $n$ pseudosegments.
Problem. In the worst case over arrangements of $n$ pseudosegments, how many intersection points must be turned into vertices to make the arrangement extendible to a pseudoline arrangement, as a function of $n$?
Source: Origin uncertain; perhaps Chan (2000), Agarwal, Aronov, Chan and Sharir (1998), or Aronov, who posed it at the Fall Workshop on Computational Geometry 2001; Problem 34 of The Open Problems Project (Demaine, Mitchell and O'Rourke).
Imported from topp.openproblem.net.
Classification
- Primary
- MG — Metric Geometry
- Secondary
- CO
- Keywords
- pseudoline arrangements, pseudosegments, The Open Problems Project
References
@inproceedings{chan2000,
author = {Chan, Timothy M.},
title = {On Levels in Arrangements of Curves},
booktitle = {Proc. 41st Annu. IEEE Sympos. Found. Comput. Sci.},
year = {2000},
pages = {219--227},
}
@article{agarwal1998,
author = {Agarwal, P. K. and Aronov, Boris and Chan, T. M. and Sharir, Micha},
title = {On Levels in Arrangements of Lines, Segments, Planes, and Triangles},
journal = {Discrete Comput. Geom.},
volume = {19},
year = {1998},
pages = {315--331},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-01083, "Extending pseudosegment arrangements to pseudoline arrangements by subdivision", clopen.solutions.