Matemático resuelve uno de los problemas más complejos de la geometría combinatoria

La investigación tiene aplicaciones en áreas tan diversas como el desarrollo de medicamentos, la planificación del movimiento de robots y los gráficos por ordenador.

Un matemático de la Facultad de Artes y Ciencias de la Universidad de Indiana ha resuelto un problema de hace 65 años de la geometría combinatoria, que buscaba determinar en número mínimo de distancias distintas entre cualquier conjunto finito de puntos en un plano.

Matematicas


El trabajo del Profesor del Departamento de Matemáticas de la IU Nets Hawk Katz, Junto a Larry Guth del Instituto de Estudios Avanzados en Princeton, Nueva Jersey, logró lo que muchos pensaban que era inalcanzable: Resolver el Problema de Distancias Distintas de 1946 de Paul Erdös.

“Si alguien te da algunos conjuntos de puntos distintos, puedes calcular el conjunto de diferencias. El problema es determinar cuál es el conjunto mínimo posible de distancias”, dice Katz. “Lo que hicimos fue demostrar que no importa cómo coloques los N puntos, el número de distancias es, al menos, una constante N/log N veces.

Aquí, N representa el número de conjuntos finito de puntos. En un logro histórico, Katz y Guth fueron capaces de alcanzar el exponente de 1, lo que se pensaba que era imposible.

Basándose en décadas de trabajo realizado por otros, Katz y Guth examinaron el problema dentro de un grupo de movimientos rígidos del plano y usaron la geometría Euclidiana para ver el problema de la distancia como uno lineal en tres dimensiones. Introduciendo dos nuevas ideas a la demostración existente, ambos mejoraron exponencialmente el límite inferior rescrito más recientemente de 0,8641, una marca que Katz hacía ayudado anteriormente a obtener.

Guth y Katz fueron capaces de combinar el método algebraico con un resultado procedente de la topología, conocido como el teorema polinomial del sándwich de jamón, que se usó para crear una descomposición celular que arrojó los resultados deseados cuando la mayor parte de los puntos estaban en el interior de las células, mientras que en el caso contrario podían manejarse por el método algebraico.

La nueva demostración usó una reformulación geométrica del problema original que fue ideada por Gyorgy Elekes (Universidad de Eotvos, Hungría) y Micha Sharir (Universidad de Tel Aviv). Usando este marco de trabajo, Katz y Guth implementaron el teorema polinomial del sándwich de jamón para crear un nuevo tipo de descomposición celular que deja los puntos del plano en el interior o en las paredes de las células.

“Este procedimiento tiene lo que ha resultado ser la ventaja de no terminar siempre en una descomposición”, señala Katz. “En lugar de esto, hay una dicotomía. Logramos una descomposición extremadamente eficiente que proporciona los teoremas de incidencia que queremos, o la alternativa, que el procedimiento falle y la mayor parte de líneas estén en el conjunto cero de un grado polinomial bastante bajo. Ésta es una alternativa aceptable, debido a que nos permite aplicar el método algebraico”.

El profesor de matemáticas de UCLA y ganador de la Medalla Fields, Terence Tao, dice que el trabajo es “impresionante” y la base para posteriores avances.

“Ahora que sabemos que dos de las herramientas más potentes de la geometría de incidencia combinatoria – la descomposición celular el método polinomial – pueden combinarse para dar unos resultados casi perfectos que están fueran del alcance de cada método por separado, parece que merece la pena volver a visitar el resto de problemas estándar sobre el tema y ver si podemos mejorar los resultados parciales de estos problemas un poco más”, escribe sobre la recientemente descubierta dicotomía durante una revisión de la demostración.

La geometría combinatoria, un campo que tiene aplicaciones de gran alcance en áreas tan diversas como el desarrollo de medicamentos, la planificación del movimiento de robots y los gráficos por ordenador, examina propiedades discretas tales como simetría, plegamiento, empaquetamiento, descomposición y teselado asociadas con la combinación de objetos geométricos.

Janos Pach, editor jefe de la revista Discrete and Computational Geometry y uno de los colaboradores más frecuentes de Erdös, describe el artículo en un blog personal como “un gran logro”. “Vamos a celebrar este fantástico desarrollo”, escribe.

Erdös creó un premio de 500 dólares para cualquiera que llegase a la solución del problema de la distancia, que se ha considerado desde hace mucho tiempo como uno de los problemas más difíciles de la combinatoria geométrica. Hasta ahora nadie había reclamado el premio. Pero en una reciente reunión de la Sociedad Matemática Canadiense, Ron Graham, científico jefe del Instituto de California para Telecomunicaciones y Tecnologías de la Información, y la persona a cargo del premio desde la muerte de Erdös, acordaron tras un debate con los asistentes que el descubrimiento garantizaba un premio de 250 dólares.

“El límite inferior es del orden N/(log N) en lugar del óptimo N/(log N)^{{1/2}}, pero el exponente – que es la potencia de N en el numerador – es justo 1”.

Katz, que llegó a la IU en 2004, tiene una Licenciatura en matemáticas por la Universidad de Rice y es doctor en matemáticas por la Universidad de Pennsylvania. Guth es miembro de la Facultad de Matemáticas en el Instituto para Estudios Avanzados.

El artículo, “On the Erdös distinct distance problem in the plane”, está actualmente disponible aquí, en el archivo de borradores electrónico de arXiv y ha sido enviado para su publicación a Annals of Mathematics, considerada una de las revistas matemáticas más prestigiosas del mundo. El trabajo de Katz estuvo parcialmente patrocinado por la Fundación Nacional de Ciencia.


Fecha Original: 24 de febrero de 2011
Enlace Original

Comparte:
  • Print
  • Digg
  • StumbleUpon
  • del.icio.us
  • Facebook
  • Twitter
  • Google Bookmarks
  • Bitacoras.com
  • Identi.ca
  • LinkedIn
  • Meneame
  • Netvibes
  • Orkut
  • PDF
  • Reddit
  • Tumblr
  • Wikio
This page is wiki editable click here to edit this page.

Like This Post? Share It

Comments (7)

  1. Información Bitacoras.com…

    Valora en Bitacoras.com: La investigación tiene aplicaciones en áreas tan diversas como el desarrollo de medicamentos, la planificación del movimiento de robots y los gráficos por ordenador. Un matemático de la Facultad de Artes y Ciencias de la……

  2. Pachu

    $250 por todo eso ??

    Con razón dicen que la ciencia no paga XD

  3. [...] Matemático resuelve uno de los problemas más complejos de la geometría combinatoria http://www.cienciakanija.com/2011/03/01/matematico-resuelve-uno-…  por Think_Future hace 3 segundos [...]

  4. Paul Erdos fue el matemático que más artículos escribió de la historia, muchos en colaboración con otros matemáticos. Como buen genio de las matemáticas era bastante excéntrico, no daba ninguna importancia a los bienes materiales y repartía casi todo su sueldo en forma de apuestas matemáticas: proponía un problema matemático junto con un premio para el que lo resolviera, de ahí el viene el valor simbólico del premio que se menciona en el artículo. Como no tenía dinero vivía como un vagabundo, iba de casa en casa de sus colaboradores matemáticos.
    Es curioso darse cuenta de lo singular de la personalidad de muchos de los grandes matemáticos: para ellos la matemática es la verdad suprema, la fuente del conocimiento absoluto y la razón de su existencia. Los actos cotidianos de la vida no tienen ninguna importancia (muchos descuidaban su aspecto e incluso su higiene), la matemática “trasciende” el valor de la propia existencia personal.

  5. Perdonen la ignorancia que es mucha, pero buena. El problema planteado y resuelto ¿se puede relacionar con el del Viajante de Comercio?

    • Garred

      ¿Nadie sabe si está relacionado con el problema del viajante? : (

      Justamente había pensado sobre él leyendo la entrada, pero como no entiendo ni la mitad…

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos necesarios están marcados *