Convex Polygons in Cartesian Products - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2018

Convex Polygons in Cartesian Products

Résumé

We study several problems concerning convex polygons whose vertices lie in a Cartesian product (for short, grid) of two sets of n real numbers. First, we prove that every such grid contains a convex polygon with Ω(log n) vertices and that this bound is tight up to a constant factor. We generalize this result to d dimensions (for a fixed d ∈ N), and obtain a tight lower bound of Ω(log d−1 n) for the maximum number of points in convex position in a d-dimensional grid. Second, we present polynomial-time algorithms for computing the largest convex chain in a grid that contains no two points of the same x-or y-coordinate. We show how to efficiently approximate the maximum size of a supported convex polygon up to a factor of 2. Finally, we present exponential bounds on the maximum number of convex polygons in these grids, and for some restricted variants. These bounds are tight up to polynomial factors.
Fichier principal
Vignette du fichier
gridgons_full.pdf (462.42 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01965360 , version 1 (26-12-2018)

Identifiants

Citer

Jean-Lou de Carufel, Adrian Dumitrescu, Wouter Meulemans, Tim Ophelders, Claire Pennarun, et al.. Convex Polygons in Cartesian Products. 2018. ⟨hal-01965360⟩
93 Consultations
383 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More