Método de Graham

Método de Graham

El método de Graham (Graham scan) es un método de cálculo computacional de la envolvente convexa de un grupo finito de puntos en el plano de complejidad O(nlogn). El nombre hace honor a Ronald Graham, quien publicó el algoritmo en 1972.[1] El algoritmo calcula todos los vértices de la envolvente convexa ordenados a lo largo de la frontera. Puede se fácilmente modificado para calcular los puntos que, sin ser vértices, pertenecen a dicha envolvente.

Contenido

Algoritmo

Como se puede ver, el giro entre los vectores PA y AB es contrario a las agujas del rejoj, pero no lo es el giro entre BC y CD. El algoritmo detecta esta situación y descarta los segmentos que llevan a un giro dextrógiro.

El primer paso de este algoritmo consiste en encontrar el punto con la menor coordenada ordenada (menor coordenada en el eje y). Si hay más de un punto que cumpla esta condición, se escoge el punto con menor coordenada en el eje x. A este punto se lo nombra por la letra P. Este paso es de complejidad O(n), donde n es el número de puntos del problema.

Después, el conjunto de puntos debe ser ordenado en orden creciente de ángulo abarcado entre el segmento que los une con el punto P y el eje ordenado. Para ello se pude utilizar cualquier algoritmo de ordenamiento. Para agilizar el proceso, se puede omitir el cálculo del ángulo ya que es suficiente con hallar su cotangente.


El algoritmo continúa tratando secuencia de puntos ordenados según el ángulo creciente. Para cada punto se calcula si el movimiento desde los dos anteriores es un "giro a derecha" o un "giro a izquierda". Si el movimiento es dextrógiro, indica que el segundo punto de la terna no es parte de la envolvente convexa y debe dejar de considerarse en los cálculos y tomar el siguiente. Cuando se halla un giro a izquierda, el algoritmo pasa a calcular el siguiente punto. En caso de que existan puntos alineados pertenecientes a la envolvente, los centrales pueden ser descartados o considerados como parte de la misma.

No es necesario calcular el ángulo entre tres puntos para saber si es un giro a derecha o a izquierda, pues puede conocerse ese dato con una sola operación aritmética. Para tres puntos (x1,y1), (x2,y2) y (x3,y3), se puede calcular el producto vectorial de los dos vectores definidos por las coordenadas (x1,y1), (x2,y2) y (x1,y1), (x3,y3), de tal manera que el resultado se obtiene con la ecuación (x2x1)(y3y1) − (y2y1)(x3x1). Si el resultado es 0, los puntos está alineados, si es positivo, el giro es a izquierdas y, si es negativo, el giro es a derecha.

Finalmente, con este proceso se vuelve al punto P de partida, momento en el que el algoritmo está completado y sólo quedan los puntos pertenecientes a la envolvente convexa correctamente ordenados.

Complejidad

El ordenamiento de los puntos tiene una complejidad O(nlogn). Aunque parezca que la complejidad del prodeso es O(n2), pues para cada punto vuelve atrás para comprobar si alguno de las coordenadas anteriores lleva a un giro dextrógiro, realmente es O(n) ya que cada punto se considera como mucho en dos ocasiones en cada sentido. Cada punto puede aparecer sólo una vez como (x3,y3) en un giro a izquierdas ya que el algoritmo avanza al siguiente punto en ese caso y como punto (x2,y2) en un giro a derechas, ya que en ese caso, el punto es eliminado. La complejidad total es por tanto O(nlogn) ya que el tiempo para ordenar los puntos domina sobre el tiempo necesario para calcular la envolvente.

Notas

La misma idea básica funciona si los puntos están ordenados según el eje ordenado en lugar del ángulo, y la envolvente se calcula en dos pasos, generando la parte superior y la parte inferior de la misma.

La técnica de apilar datos usada en el método de Graham es muy similar al utilizado en el problema de cálculo del valor menor más cercano, el cual puede ser usado también para calcular eficientemente envolventes convexas de una serie de puntos.[2]

Referencias

  1. Graham, R.L. (1972). An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set. Information Processing Letters 1, 132-133
  2. Berkman, Omer; Schieber, Baruch; Vishkin, Uzi (1993), «Optimal double logarithmic parallel algorithms based on finding all nearest smaller values», Journal of Algorithms 14 (3): 344–370, doi:10.1006/jagm.1993.1018 .

Wikimedia foundation. 2010.

Игры ⚽ Поможем написать реферат

Mira otros diccionarios:

  • Benjamin Graham — Saltar a navegación, búsqueda Benjamin Graham (nacido Benjamin Grossbaum) (Londres, 8 de mayo de 1894 – 21 de septiembre de 1976) fue un economista influyente y un inversionista profesional. Graham es considerado el primer proponente y partidario …   Wikipedia Español

  • Martha Graham — Nacimiento …   Wikipedia Español

  • Ley de Graham — La Ley de Graham, formulada en 1829 por Thomas Graham, establece que las velocidades de efusión de los gases son inversamente proporcionales a las raíces cuadradas de sus respectivas densidades. Siendo v las velocidades y δ las densidades.… …   Wikipedia Español

  • Thomas Graham — (Glasgow, 21 de diciembre de 1805 – 16 de septiembre de 1869), químico británico, conocido por sus investigaciones en la difusión de gases y líquidos y en la química de los coloides. Estudió en las universidades de Edimburgo y su ciudad natal.… …   Wikipedia Español

  • Thomas Graham — (Glasgow, 1805 1869), químico británico, conocido por sus investigaciones en la difusión de gases y líquidos y en la química de los coloides. Estudió en las universidades de Edimburgo y su ciudad natal. Enseñó química en Glasgow y en el… …   Enciclopedia Universal

  • Ley de Graham — La ley de Graham, formulada en 1829 por Thomas Graham, establece que las velocidades de difusión de los gases son inversamente proporcionales a las raíces cuadradas de sus respectivas densidades. Se hace uso de este principio en el método de… …   Enciclopedia Universal

  • Bell, Alexander Graham — ► (1847 1922) Físico estadounidense. La problemática de la enseñanza de los sordomudos le impulsó a llevar a cabo diversos estudios e investigaciones sobre el sonido. Inventó el teléfono (1876) y fundó la empresa de telecomunicaciones ATT. * * *… …   Enciclopedia Universal

  • Asamblea Parlamentaria de las Naciones Unidas — Emblema de la propuesta Asamblea Parlamentaria de las Naciones Unidas. Consiste en un fondo azul claro con el emblema en blanco, que son los colores oficiales de las Nac …   Wikipedia Español

  • Música de Nigeria — La música de Nigeria incluye muchas clases de música tradicional y popular africanas. Se relaciona con múltiples grupos étnicos del país, cada uno con sus propias técnicas, instrumentos y canciones. Poco se sabe sobre la historia de la música del …   Wikipedia Español

  • Historia de la electricidad — Un fragmento de ámbar como el que pudo utilizar Tales de Mileto en su experimentación del efecto triboeléctrico. El nombre en griego de est …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”