Formalizing Convex Hulls Algorithms

Formalisation d'algorithmes d'enveloppes convexes

David Pichardie (1) , Yves Bertot (2)

1 Lande - Logiciel : ANalyse et DEveloppement
2 MARELLE - Mathematical, Reasoning and Software

We study the development of formally proved algorithms for computational geometry. The result of this work is a formal description of the basic principles that make convex hull algorithms work and two programs that implement convex hull computation and have been automatically obtained from formally verified mathematical proofs. A special attention has been given to handling degenerate cases that are often overlooked by conventional algorithm presentations.

Domaines: Logique en informatique [cs.LO]; Géométrie algorithmique [cs.CG]

David Pichardie, Yves Bertot. Formalizing Convex Hulls Algorithms. TPHOLs 2001 - 14th International Conference Theorem Proving in Higher Order Logics, Sep 2001, Edinburgh, United Kingdom. pp.346-361, ⟨10.1007/3-540-44755-5_24⟩. ⟨hal-01702679⟩