Visibility Graphs of Points, Segments and Polygons — Problem 43

Definitions and mathematical statement

The supplied source asks for an asymptotically tight bound on the number of bits used by an optimal covering set of a visibility graph, together with a polynomial-time construction attaining that bound. The excerpt does not define a covering set, specify the class of visibility graphs, or specify how covering sets are encoded. These omissions prevent a complete mathematical formulation.

The optimization target can be described conditionally as follows. Once the intended instance class and representations have been specified, let $I$ denote an instance representing a visibility graph, let $\mathcal{C}(I)$ denote its admissible covering sets, and let $\ell_I(C)\in{\mathbb{Z}}_{\geq 0}$ denote the number of bits in the prescribed representation of $C\in\mathcal{C}(I)$. For instances with $\mathcal{C}(I)\neq\varnothing$, define \[ b(I)=\min_{C\in\mathcal{C}(I)}\ell_I(C). \] The requested tasks are to determine a tight asymptotic bound for this optimum, with respect to the intended size parameter, and to construct an admissible covering set attaining that bound in polynomial time. This is a formulation schema: the supplied excerpt does not determine $\mathcal{C}(I)$, $\ell_I$, the size parameter, or the computational input representation. It also does not specify whether the asymptotic bound concerns each instance or the worst case over instances of a given size. No particular choices for these missing specifications are asserted here.

Short English statement

Problem 43 asks how many bits an optimal covering set of a visibility graph requires, up to asymptotic order, and asks for a polynomial-time construction matching that bound. The supplied excerpt leaves the covering-set definition, graph class, encoding, size parameter, and computational model unspecified; these require clarification before the problem has a precise complete statement.

Sources

• Supplied local UnsolvedMath registry record: permanent ID $800569$, source problem code catalogue entry, title Visibility Graphs of Points, Segments and Polygons --- Problem 43. Upstream revision: d371ee917ac9647fbb06cd6fc529deec6f3dda82.
• Ghosh and Goswami, Unsolved Problems in Visibility Graphs of Points, Segments and Polygons (2010), Problem 43. Supplied source link: https://arxiv.org/abs/1012.5187. The record attributes the problem to Ghosh and Goswami and gives the proposed year as 2010.
• The supplied provenance records access on 2026-10-16 and extraction by arxiv_latex. These are supplied provenance details; no independent source visit or verification is asserted. The registry labels the problem open; that label is supplied curation, not an independently verified assessment of its mathematical status.