Verified Polygon Intersection: Formally Verifying Computational Geometry with Lean 4 and AI
The verified-polygon-intersection project provides the first formally verified implementation of an intersection algorithm for multipolygons. By leveraging the Lean 4 proof assistant, the project ensures that the intersection of two multipolygons—defined as the intersection of their interior point sets—is mathematically guaranteed to be correct for all possible input configurations, eliminating the risks associated with rare edge cases in computational geometry.
Formal Verification of Multipolygon Intersection
Multipolygon intersection is a standard requirement for vector graphics editors, but it is notoriously difficult to verify through classical testing. Because the set of interior points for any polygon is infinite and the number of possible input configurations is limitless, traditional test suites cannot exhaustively prove correctness.
The Challenge of Edge Cases
Computational geometry is plagued by "special configurations" that introduce significant algorithmic complexity. For example, when intersecting a cross with a square containing a hole, the algorithm must partition and order segments into closed boundary components. This process is not always unique and relies on non-trivial mathematical properties, such as Eulerian cycles, to ensure a valid multipolygon is produced in every case.
The Lean 4 Approach
This project uses Lean 4 to formally describe the intersection specification and verify the algorithm. The core guarantee is that the interior sets of the output multipolygon satisfy the intersection equality of the input sets. This level of rigor is computationally expensive to prove; for instance, proving that the definition of "inside" (based on ray-casting parity) is independent of the ray's direction required thousands of lines of Lean code.
The Role of AI Agents in Formal Proofs
Correctness in this project is derived from the Lean checker and human review of a small specification, not from the LLM. The human reviewer only needs to examine 87 lines of simple Lean specification across three files (DataStructures.lean, Defs.lean, and MultipolygonIntersectionAlgorithmWithPreconditionCheck.lean) and run the Lean checker to verify the implementation.
Evolution of AI Capabilities
The author observed a dramatic shift in the ability of AI agents to handle formal verification across different model versions:
- Claude Opus 4.5/4.6: Could handle non-trivial proofs only when provided with a perfectly rigorous, step-by-step sketch by the human user.
- Claude Opus 4.7: Could take larger steps and autonomously extract a verified algorithm from a theorem, though it still required human hints for Eulerian circuits and tricky special cases.
- Claude Opus 4.8 (Ultracode mode): Demonstrated the ability to formulate and execute large proof strategies autonomously. It successfully reproved the main polygon intersection theorem from scratch without hints and handled complex special cases involving overlapping segments that had defeated previous versions.
Trade-offs of AI-Generated Verified Code
While AI agents can successfully navigate formal proofs, the author noted a drawback: the resulting code tends to be slower or ignores practical performance considerations. This is attributed to the difficulty of formal verification, which pushes the AI toward simpler, more provable code rather than optimized, high-performance implementations.
Technical Implementation and Verification
Building and Checking
The project requires elan and uses Lean version v4.15.0. Users can verify all proofs using lake build. To ensure the AI did not introduce unwanted axioms, the project allows inspecting dependencies for the correctness theorem. The implementation currently depends only on trusted axioms: propext, Classical.choice, and Quot.sound.
Web Integration
A web demo is available, built around the verified core. The project uses a build script (build.sh) that utilizes emscripten, zstd, and wasm-opt to compile the verified Lean code into a WebAssembly bundle.
Comparison to Related Work
This project extends beyond previous efforts in the field. For example, Di Vito and Hocking (NASA Formal Methods 2021) verified a polygon merge algorithm in PVS, which combined two overlapping simple polygons into a single outer boundary without holes. The verified-polygon-intersection project specifically addresses the more complex problem of multipolygon intersection, including the handling of holes and complex interior sets.