Extending Pseudosegment Arrangements by Subdivision

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

A pseudosegment arrangement consists of $n$ finite planar curves with at most one intersection for each pair. A pseudoline arrangement consists of curves extending to infinity in both directions with at most one intersection for each pair. A subdivision turns selected intersection points into endpoints, splitting the incident pseudosegments. An extension continues the resulting pieces into pseudolines while preserving the arrangement of the pieces.

Statement recorded in the supplied source.

Determine, as a function of $n$, the worst-case minimum number of intersections that must be selected as subdivision vertices to make a pseudosegment arrangement extendible to a pseudoline arrangement. [S2]

Short English statement

Determine, as a function of $n$, the worst-case minimum number of intersections that must be selected as subdivision vertices to make a pseudosegment arrangement extendible to a pseudoline arrangement.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 5500034 (AMR-054-0034). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Erik D. Demaine, Joseph S. B. Mitchell and Joseph O'Rourke (editors), The Open Problems Project, maintained original source, Problem 34, Statement and complete Partial/Related Results. https://github.com/edemaine/topp/blob/main/Problems/P.000034.