Visibility Graphs of Points, Segments and Polygons — Problem 32

Definitions and mathematical statement

The supplied source asks: "Design an algorithm for testing Necessary Condition 4 in polynomial time." However, the supplied record does not reproduce Necessary Condition 4 or specify its input objects, hypotheses, or encoding. Consequently, the intended decision problem cannot be stated precisely from this record alone.

A conditional specification of the requested task is as follows. Let $\mathcal I$ denote the intended class of admissible inputs, let $\operatorname{enc}(x)$ denote the intended finite encoding of $x\in\mathcal I$, and let $C_4(x)$ mean that $x$ satisfies the source's Necessary Condition 4. These are placeholders for missing source definitions, not additional assumptions about the intended problem. Once those definitions and the computational model are supplied, construct an algorithm $A$ and a polynomial bound $p$ such that, for every $x\in\mathcal I$, the algorithm returns a value in $\{0,1\}$ satisfying \[ A(\operatorname{enc}(x))=1\quad\Longleftrightarrow\quad C_4(x), \] and terminates within $p(|\operatorname{enc}(x)|)$ computational steps. The content of $C_4$, the domain $\mathcal I$, and the representation and computational conventions remain unresolved.

Short English statement

Construct a polynomial-time test for the condition called Necessary Condition 4 in the cited survey. The supplied record omits that condition and its input specifications, so only a conditional description of the requested algorithm is possible.

Sources

• Local UnsolvedMath registry: permanent ID $800558$, source code catalogue entry, titled "Visibility Graphs of Points, Segments and Polygons --- Problem 32." The record attributes the problem to Ghosh and Goswami, with proposed year 2010.
• Ghosh and Goswami, Unsolved Problems in Visibility Graphs of Points, Segments and Polygons (2010), Problem 32. Supplied source URL: https://arxiv.org/abs/1012.5187. The record reports extraction by arxiv_latex and access on 2026-10-16; these are supplied provenance statements, not independently verified access.
• The local record labels the problem "open." This is a supplied registry classification, not an independently verified assessment of its mathematical or literature status.