Convexly independent subsets of Minkowski sums of convex polygons

Mateusz Skomra (1) , Stéphan Thomassé (2, 3)

1 LAAS-MAC - Équipe Méthodes et Algorithmes en Commande
2 MC2 - Modèles de calcul, Complexité, Combinatoire
3 IUF - Institut universitaire de France

We show that there exist convex n-gons P and Q such that the largest convex polygon in the Minkowski sum P + Q has size Θ(n log n). This matches an upper bound of Tiwary.

Domaines: Combinatoire [math.CO]; Géométrie algorithmique [cs.CG]; Mathématique discrète [cs.DM]

Mateusz Skomra, Stéphan Thomassé. Convexly independent subsets of Minkowski sums of convex polygons. Discrete Mathematics, 2021, 344 (8), pp.112472. ⟨10.1016/j.disc.2021.112472⟩. ⟨hal-03457272⟩