Two triangulations that share only their hull
Any two triangulations of a finite planar point set share the edges of its convex hull. For every n ≥ 9 there are n points in general position, with a pentagonal hull, that have two triangulations sharing nothing else; since at least five edges must be shared once n ≥ 5, the minimum number of shared edges is exactly five for every n ≥ 9. The construction starts from nine explicit points and inserts points one at a time, carrying along a configuration (a chain) that makes the next insertion possible. Started from a convex polygon, the same construction settles every hull size: n points with h hull vertices admit two triangulations sharing only the hull exactly when n = h, or h ≥ 6, or h = 5 and n ≥ 9. The cases of a pentagonal hull with six to eight points rest on an exhaustive search over the order-type database of Aichholzer, Aurenhammer and Krasser; everything else is formalised in Lean 4. This record is identical to the folder two-triangulations-hull at tag two-triangulations-hull-v3 of https://github.com/jvvk/mathematics. Version 3 of the preprint; versions 1 and 2 were released on GitHub only.
Authors
- Vamshi Jandhyala (ORCID: https://orcid.org/0009-0006-6708-5805)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-19
- DOI
- https://doi.org/10.5281/zenodo.24366551
- Primary Topic
- Computational Geometry and Mesh Generation
- Type
- preprint