Visibility Graphs of Points, Segments and Polygons — Problem 37

Definitions and mathematical statement

Let $P$ be a simple polygon. Under the vertex-visibility interpretation, its visibility graph $G=(V,E)$ has one vertex for each vertex of $P$, and two distinct vertices are adjacent when the segment joining them is contained in the closed polygonal region $P$. Let $C$ be the Hamiltonian cycle listing these vertices in their order along the boundary of $P$. The input consists of $(G,C)$, promised to arise from such a polygon; polygon coordinates are not specified as part of the input.

Under this interpretation, a hidden vertex set is a set $H\subseteq V$ whose distinct members are pairwise nonadjacent: \[ \forall u,v\in H,\qquad u\ne v\Longrightarrow \{u,v\}\notin E. \] Define \[ \alpha(G)=\max\left\{|H|:H\subseteq V,\ H\text{ is a hidden vertex set}\right\}. \] The displayed source problem asks: given any such pair $(G,C)$, determine a hidden vertex set $H$ with $|H|=\alpha(G)$.

The supplied record additionally asks for an approximation algorithm for computing a maximum hidden set of a visibility graph. It does not specify an approximation guarantee, a running-time requirement, or whether this additional request retains the simple-polygon promise and the supplied boundary cycle. These qualifications remain unresolved. The source excerpt also does not define hidden sets or its visibility convention; the formulation above explicitly uses independent sets of polygon vertices and visibility within the closed polygon. A target involving arbitrary points of the polygon would require a different formulation.

Short English statement

Given a simple polygon's vertex-visibility graph together with its boundary order, find a largest collection of mutually invisible vertices. The record also requests an approximation algorithm, but leaves its guarantee and precise input class unspecified. The interpretation of hidden sets and boundary visibility requires source confirmation.

Sources

• Local UnsolvedMath registry, permanent ID $800563$, source problem code catalogue entry, title "Visibility Graphs of Points, Segments and Polygons --- Problem 37." The registry attributes the problem to Ghosh and Goswami, with proposed year 2010, and labels it open; this label is supplied source data, not an independently verified assessment.
• Ghosh and Goswami, Unsolved Problems in Visibility Graphs of Points, Segments and Polygons (2010), Problem 37. Supplied source URL: https://arxiv.org/abs/1012.5187. The background records access on 2026-10-16 and extraction method arxiv_latex; these are supplied provenance details, not a claim of independent access or verification.
• Supplied upstream revision: d371ee917ac9647fbb06cd6fc529deec6f3dda82. The registry record was updated on 2026-10-16.