Le monde de la convexité discrète
| Autor: | Crombez, Loïc |
|---|---|
| Přispěvatelé: | STAR, ABES, Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA), Université Clermont Auvergne, Guilherme Dias Da Fonseca |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
Convexity
Convexité [INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG] Géométrie digitale Recogniton Séparation polyhédrale Digital geometry Polyhedral separation [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG] Géométrie algorithmique Computational geometry Reconnaissance |
| Zdroj: | Computational Geometry [cs.CG]. Université Clermont Auvergne, 2021. English. ⟨NNT : 2021UCFAC110⟩ |
| Popis: | A set S⊂Zd is said \emph{digital convex} if \conv(S)∩Zd=S, where \conv(S) denotes the convex hull of S. Herein, we consider several algorithmic problems related to recognition of digital convex sets, as well as the detection of digital convex sets. We start by showing that the quickhull algorithm runs in linear time for digital convex sets. Then, based on this result, we propose an algorithm to test the digital convexiyty of a lattice set S⊂Z2 in O(n+hlogr) time, where h denotes the number of vertices of the convex hull of S, and r denotes the diameter of S. Then, We show how those results can be used to solve the digital polyhedra recognition problem. Finally, we propose a polynomial time algorithm to find the largest union of k digital convex subsets of S⊂Z2. 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|