En geometria discreta i en geometria computacional, es diu que un conjunt de punts en el pla o en un espai euclídeo de dimensions superiors està en posició convexa o en posició convexa independent si cap dels punts pot representar-se com una combinació convexa dels demés.[1] Un conjunt finit de punts està en posició convexa si tots ells són vèrtiços del seu envolvente convexa.[1] De manera més general, es diu que una família de convexidadés està en posició convexa si estan separades per parells i cap d'elles està continguda en la envolvente convexa de les demés.[2]

Propietats

La suposició d'una posició convexa pot facilitar la resolució de certs problemes computacionals. Per eixemple, el problema del viajante, NP-dur per a conjunts arbitraris de punts en el pla, és trivial per a punts en posició convexa: el recorregut òptim és la envolvente convexa.[3] De manera similar, la triangulació de pes mínim de conjunts de punts plans és NP-dur per a conjunts de punts arbitraris, pero es pot resoldre en temps polinòmic per mig de programació dinàmica per a una série de punts en posició convexa.[4]

El teorema de Erdős-Szekeres garantisa que cada conjunt de n punts en posició general (llevat para tres o més d'ells en llínea recta) en dos o més dimensions tinga a lo manco un número logarítmic de punts en posició convexa.[5] Si els punts n s'elegixen uniformemente a l'encert en un quadrat unitat, la provabilitat de que estiguen en posició convexa és[6]

((2n−2n−1)/n!)2.

El problema de McMullen consistix en trobar el número màxim ν(d) tal que cada conjunt de ν(d) punts en posició general en un espai proyectivo d-dimensional tinga una transformació proyectiva que genere un conjunt image en posició convexa. Els llímits coneguts són 2d+1≤ν(d)≤2d+⌈(d+1)/2⌉. [7]

Referències


  1. ↑ 1,0 1,1 Erro en la cita: L'element <ref> no és vàlit; puix no n'hi ha una referència en text nomenada m02
  2. ↑ Erro en la cita: L'element <ref> no és vàlit; puix no n'hi ha una referència en text nomenada tv05
  3. ↑ Erro en la cita: L'element <ref> no és vàlit; puix no n'hi ha una referència en text nomenada dhow06
  4. ↑ Erro en la cita: L'element <ref> no és vàlit; puix no n'hi ha una referència en text nomenada k80
  5. ↑ Erro en la cita: L'element <ref> no és vàlit; puix no n'hi ha una referència en text nomenada és35
  6. ↑ Erro en la cita: L'element <ref> no és vàlit; puix no n'hi ha una referència en text nomenada v95
  7. ↑ Erro en la cita: L'element <ref> no és vàlit; puix no n'hi ha una referència en text nomenada flvs01