Next: Problem 35: Freeze-Tag: Optimal Strategies for Awakening a Swarm of Robots
Previous: Problem 33: Sum of Square Roots
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.
Open.
Chan [Cha00a] has proved an upper bound of O(n \log n).
Posed by Boris Aronov during the open problem session at the Fall Workshop on Computational Geometry, Brooklyn, NY, Nov. 2–3, 2001.
combinatorial geometry
E. Demaine, 20 Nov. 2001.
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.
Timothy M. Chan. On levels in arrangements of curves. In Proc. 41th Annu. IEEE Sympos. Found. Comput. Sci., pages 219–227, 2000.