next up previous
Next: Problem 35: Freeze-Tag: Optimal Up: The Open Problems Project Previous: Problem 33: Sum of


Problem 34: 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.

Origin
Perhaps [Cha00a], [AACS98], or Boris Aronov?
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.

Bibliography

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.


next up previous
Next: Problem 35: Freeze-Tag: Optimal Up: The Open Problems Project Previous: Problem 33: Sum of
The Open Problems Project - December 04, 2015