Formally Certifying the Vertex Set of a Polyhedron Faster than Informal Enumeration

Xavier Allamigeon, Yazid Id-Sahra, Pierre-Yves Strub

arXivarxiv/2610.11913Oct 8, 2026cs.LOscore 0

The computation of the vertices of a polyhedron described by a system of linear inequalities is a central problem in polyhedral computation. It is a fundamental step in the conversion between H-representations, by linear inequalities, and V-representations, by vertices and extreme rays. This operation plays an important role both in the study of polyhedra and their combinatorics in mathematics and in applications to software and system verification. We present a certificate-based approach for formally verifying the computation of the vertices of a polyhedron. Given an informally computed…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2610.11913
curl -X POST /api/v1/records/arxiv/2610.11913/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.11913/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'