Finding Digital Convexity
Loïc Crombez · 2021
Le monde de la convexité discrète Un ensemble S⊂Zd est \emph{convexe discret} si \conv(S)∩Zd=S, où \conv(S) est l'enveloppe convexe de S. Ici, nous considérons plusieurs problèmes algorithmiques traitant de la reconnaissance d'ensembles convexes discrets ainsi que de la détection de sous ensembles convexes discrets. Nous montrons que l'algorithme quickhull s'exécute en temps linéaire pour des ensembles convexe discret. Puis nous utilisons ce résultat afin de proposer un algorithme qui teste la convexité discrète de S⊂Z2 en O(n+hlogr) temps, où h est le nombre de sommet de l'enveloppe convexe de S et r est le diamètre de S. Ensuite, nous étendons ce résultat et montrons comment il peut être utilisé afin de résoudre le problème de reconnaissance d'ensemble convexe discret. Enfin, nous proposons un algorithme en temps polynomial qui détecte la plus grande union de k sous ensembles convexes discrets de S⊂Z2.