Posició convexa
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 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 s'elegixen uniformemente a l'encert en un quadrat unitat, la provabilitat de que estiguen en posició convexa és[6]
El problema de McMullen consistix en trobar el número màxim tal que cada conjunt de punts en posició general en un espai proyectivo -dimensional tinga una transformació proyectiva que genere un conjunt image en posició convexa. Els llímits coneguts són . [7]
Referències
- Este artícul conté una traducció derivada de «Posición convexa» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.
- ↑ 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 nomenadam02 - ↑ Erro en la cita: L'element
<ref>no és vàlit; puix no n'hi ha una referència en text nomenadatv05 - ↑ Erro en la cita: L'element
<ref>no és vàlit; puix no n'hi ha una referència en text nomenadadhow06 - ↑ Erro en la cita: L'element
<ref>no és vàlit; puix no n'hi ha una referència en text nomenadak80 - ↑ Erro en la cita: L'element
<ref>no és vàlit; puix no n'hi ha una referència en text nomenadaés35 - ↑ Erro en la cita: L'element
<ref>no és vàlit; puix no n'hi ha una referència en text nomenadav95 - ↑ Erro en la cita: L'element
<ref>no és vàlit; puix no n'hi ha una referència en text nomenadaflvs01