Skip to Main content Skip to Navigation

Covering families of triangles

Otfried Cheong 1 Olivier Devillers 2 Marc Glisse 3 Ji-Won Park 2
2 GAMBLE - Geometric Algorithms and Models Beyond the Linear and Euclidean realm
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
3 DATASHAPE - Understanding the Shape of Data
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : A cover for a family $\mathcal{F}$ of sets in the plane is a set into which every set in $\mathcal{F}$ can be isometrically moved. We are interested in the convex cover of smallest area for a given family of triangles. Park and Cheong conjectured that any family of triangles of bounded diameter has a smallest convex cover that is itself a triangle. The conjecture is equivalent to the claim that for every convex set $\mathcal{X}$ there is a triangle $Z$ whose area is not larger than the area of $\mathcal{X}$, such that $Z$ covers the family of triangles contained in $\mathcal{X}$. We prove this claim for the case where a diameter of~$\mathcal{X}$ lies on its boundary. We also give a complete characterization of the smallest convex cover for the family of triangles contained in a half-disk, and for the family of triangles contained in a square. In both cases, this cover is a triangle.
Document type :
Complete list of metadatas
Contributor : Olivier Devillers <>
Submitted on : Tuesday, December 1, 2020 - 2:20:40 PM
Last modification on : Tuesday, December 8, 2020 - 10:29:12 AM


  • HAL Id : hal-03031995, version 1


Otfried Cheong, Olivier Devillers, Marc Glisse, Ji-Won Park. Covering families of triangles. [Research Report] RR-9378, INRIA. 2020, pp.31. ⟨hal-03031995⟩



Record views


Files downloads