Poligonalisació

En geometria computacional, una poligonalisació d'un conjunt finit de punts del pla euclidiano és un polígon simple els vèrtiços del qual són precisament els punts donats.
Una poligonalisació també pot denominar-se poligonisació, poligonisació simple, polígon hamiltoniano, cicle hamiltoniano sense creus, o cicle que comprén arestes rectes sense creus.
Tot conjunt de punts que no estiga contingut en una única recta posseïx a lo manco una poligonalisació, la qual pot trobar-se en temps polinòmic. Per als punts en posició convexa existix una sola poligonalisació, mentres que per a atres conjunts poden existir exponencialment moltes. Trobar una poligonalisació òptima segons diversos criteris naturals d'optimisació constituïx un problema difícil, i inclou com a cas particular el problema del viajante. La complexitat computacional de contar totes les poligonalizaciones seguix sent desconeguda.
Definició
Una poligonalisació és un polígon simple que té com a conjunt de vèrtiços un conjunt donat de punts del pla euclidiano. Un polígon pot descriure's per mig d'un orde cíclico dels seus vèrtiços, units en parells consecutius per mig de segments de recta que constituïxen els seus costats. Un polígon definit d'esta manera és «simple» quan els únics punts d'intersecció entre dits segments són els seus extrems comuns.
Alguns autors consideren únicament poligonalizaciones per a conjunts de punts en posició general, és dir, en els que no existixen tres punts colineales. Baix esta hipòtesis, l'àngul entre dos costats consecutius del polígon mai pot ser de 180°. No obstant, quan es consideren conjunts de punts en colinealidades, generalment es permet que les poligonalizaciones presenten ànguls de 180° en alguns vèrtiços. En estos casos, dits punts seguixen considerant-se vèrtiços i no punts interiors d'un costat.
Existència

Steinhaus (1964) va observar que tot conjunt finit de punts sense tres colineales constituïx el conjunt de vèrtiços d'un polígon simple. No obstant, exigir que no existixquen tres punts alineats resulta una condició més forta de lo necessari. En realitat, n'hi ha prou en que els punts no estiguen tots sobre una mateixa recta per a garantisar l'existència d'una poligonalisació (permetent ànguls de 180°). En tal cas, pot construir-se en temps polinòmic. Una forma de construir una poligonalisació consistix en elegir qualsevol punt pertanyent a l'envolvente convexa de (sense que necessàriament siga un dels punts donats). Després, en ordenar radialmente els punts al voltant de (desfent empats per mig de la distància a ) s'obté l'orde cíclico d'un polígon estrelat que passa per tots els punts donats i el núcleu dels quals conté a . Esta mateixa idea d'ordenar radialmente els punts al voltant d'un punt central també s'utilisa en algunes versions de l'algoritme d'escanege de Graham per a calcular la envolvente convexa i pot realisar-se en temps . No sempre existixen poligonalizaciones que eviten ànguls de 180°. Per eixemple, en les cuadrículas quadrades de 3 × 3 i 5 × 5, totes les poligonalizaciones contenen ànguls de 180°.
Ademés de les poligonalizaciones estrelades, tot conjunt no colineal de punts admet una poligonalisació que és un polígon monòton. Açò significa que, sobre una determinada recta (que pot prendre's com l'eix ), tota recta perpendicular a la recta de referència intersecta el polígon en un únic interval, o no ho intersecta en absolut. La construcció proposta per Grünbaum (1994) comença ordenant els punts segons les seues coordenades i traçant una recta que passa pels dos punts extrems. Com els punts no són tots colineales, a lo manco un dels dos semiespacios oberts delimitats per dita recta deu ser no buit. Grünbaum construïx llavors dos cadenes poligonales monòtones que conecten els punts extrems recorrent subsecuencias ordenades dels punts: una per als punts pertanyents al semiplano obert no buit i una atra per als punts restants. L'unió d'abdós cadenes constituïx el polígon monòton buscat. Despuix de l'etapa d'ordenament, el restant de la construcció pot realisar-se en temps llineal.
Determinar si un conjunt de punts admet una poligonalisació els costats de la qual siguen únicament paralels als eixos és un problema NP-complet. No obstant, les poligonalizaciones que, ademés, realisen un gir recte en cada vèrtiç, quan existixen, estan determinades de manera única. Cada recta paralela als eixos que passa per un punt deu contindre un número par de punts, i la poligonalisació deu conectar parells alternats de punts sobre dita recta. Pot trobar-se en temps agrupant els punts en la mateixa coordenada i ordenant cada grup segons l'atra coordenada. Per a qualsevol conjunt de punts, com a màxim una rotació admet una poligonalisació d'este tipo, i dita rotació també pot trobar-se en temps polinòmic.
Referències
- Este artícul conté una traducció derivada de «Poligonalización» 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.