{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"verified":true,"discussed":0,"published":"2026-11-09","reactions":{},"formalized":true,"formalizes":[{"title":"The Orthogonal Art Gallery Problem is ∃ℝ-complete","identifier":"","relationship":"formalizes"},{"title":"The Art Gallery Problem is ∃ℝ-complete","identifier":"","relationship":"formalizes"}]}