Id: palomar/PALOMAR-2026-11-09-000004 Url: https://github.com/RBarish-UTokyo/OrthogonalArtGalleryProblem-BoundaryPointVariant-ExistsR-Lean4/tree/2a85b75f31661e89d545efdb3c6e2d3c3e54aa09 Json: https://data.palomar-registry.org/entries/PALOMAR-2026-11-09-000004-v1.json Repo: https://github.com/RBarish-UTokyo/OrthogonalArtGalleryProblem-BoundaryPointVariant-ExistsR-Lean4 Tags: cs.CG, cs.CC, msc:68U05, msc:68Q17, msc:14P10, msc:68V20 Score: 0 Title: The orthogonal boundary-point art gallery problem is ∃ℝ-complete, in Lean 4 Trust: high Domain: cs.CG Source: palomar Authors: Robert D. Barish Reviews: 0 Subject: cs.CG Category: research Comments: 0 Disputed: false Division: cs Mentions: 0 Verified: true Discussed: 0 Published: 2026-11-09 Formalized: true Formalizes: title=The Orthogonal Art Gallery Problem is ∃ℝ-complete identifier= relationship=formalizes Formalizes: title=The Art Gallery Problem is ∃ℝ-complete identifier= relationship=formalizes Page: https://delphi.science/r/palomar/PALOMAR-2026-11-09-000004 A Lean 4 formalization of material in a forthcoming manuscript entitled "The Orthogonal Art Gallery Problem is ∃ℝ-complete". A Lean 4 and Mathlib proof, for an explicit single-tape Turing machine model, that deciding whether an orthogonal simple polygon (every edge horizontal or vertical) with rational corners can be guarded by g points of its boundary, which together must see the whole closed polygon (the boundary-point variant), is ∃ℝ-complete under polynomial-time many-one reductions. The orthogonal point-point and point-boundary variants are the subject of the author's earlier entry…