Polígon en forma d'estrela
 |
Esta pàgina de desambiguació enumera artículs que tenen títuls similars. |
En geometria, un polígon en forma d'estrela és un polígon pla que és un domini en estrela, és dir, un polígon que conté un punt a partir del com tot el llímit del polígon és visible.
Formalment, un polígon P té forma d'estrela si existix a lo manco un punt z tal que per a cada punt p de P el segment es trobe completament dins de P. El conjunt de tots els punts z en esta propietat (és dir, el conjunt de punts des dels quals tot P és visible) es denomina núcleu de P.
Si un polígon en forma d'estrela és convexo, la distància d'enllaç entre dos dels seus punts (el número mínim de segments de llínea seqüencials suficients per a conectar eixos punts) és 1, per lo que el diàmetro d'enllaç del polígon (la distància màxima d'enllaç sobre tots els parells de punts) és 1. Si un polígon en forma d'estrela no és convexo, la distància d'enllaç entre un punt en el núcleu i qualsevol atre punt en el polígon és 1, mentres que la distància d'enllaç entre dos punts qualssevol que estan en el polígon pero fòra del núcleu és 1 o 2; en este cas, la distància màxima de l'enllaç és 2.
Eixemples
[editar | editar còdic]- Els polígons convexos tenen forma d'estrela i un polígon convexo coincidix en el seu propi núcleu.
- Les estreles regulars tenen forma d'estrela i el seu centre sempre està en el núcleu.
- Els antiparalelogramos i els hexàgons de Lemoine, figures que es intersecan a sí mateixes, tenen forma d'estrela i el núcleu consta d'un sol punt.
- Els polígons de visibilitat tenen forma d'estrela, ya que cada punt dins d'ells deu ser visible des del centre per definició.
Algoritmes
[editar | editar còdic]Provar si un polígon té forma d'estrela i trobar un únic punt en el núcleu es pot resoldre en temps llineal formulant el problema com un cas de programació llineal, i conseqüentment, aplicant tècniques de programació llineal de baixa dimensió (vore http://www.inf.ethz .ch/personal/emo/PublFiles/SubexLinProg_ALG16_96.pdf, pàgina 16).
Cada aresta d'un polígon definix un semiplano interior, el semiplano el llímit del qual es troba en la llínea recta que conté l'aresta i que conté els punts del polígon en un entorn de qualsevol punt interior de l'aresta. El núcleu d'un polígon és l'intersecció de tots els seus semiplanos interiors. L'intersecció d'un conjunt arbitrari de N semiplanos es pot trobar en temps Θ(N log N) utilisant l'algoritme conegut com dividix i venceràs. No obstant, per al cas de núcleus de polígons, és possible un método més ràpit: Lee y Preparata (1979) varen presentar un algoritme per a construir el núcleu en temps llineal.
Vore també
[editar | editar còdic]Referències
[editar | editar còdic]
- Este artícul conté una traducció derivada de «Polígono con forma de estrella» 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.