Advertencia: Este post tiene contenidos de la vida real(no apto para fundamentalistas de la matematica pura)

mayo 4, 2008

1) Supongamos que tengo n ovejas que viven en \mathbb{R}^2 . En un determinado momento de tiempo se encuentran en (x_1,y_1),...,(x_n,y_n) . Yo que soy un malvado opresor imperialista las quiero encerrar en un muro circular del menor radio. Para minimizar los costos quiero encontrar un punto (x,y) y un numero real r para que todas las ovejas esten en el circulo de radio r y centro (x,y) con r minimo.
2) Tengo n peces que viven en \mathbb{R}^3 y los quiero encerrar en una red esferica de radio minimo. El resto es similar al item 1.

Para los curiosos: Estoy haciendo un programa para unas cosas de GPS y me aparecio este problema.

4 comentarios to “Advertencia: Este post tiene contenidos de la vida real(no apto para fundamentalistas de la matematica pura)”

  1. Anónimo said

    Y si te parás en el baricentro y tirás un círculo de radio R donde R es el máximo de las distancias de las ovejas al baricentro?

  2. Grin Without a Cat said

    En el plano, el disco que buscás tiene como diametro a dos vertices de la cápsula convexa C del conjunto de puntos que realizan el diámetro C, o pasa por tres de los vertices de C. Como encontrar la cápsula convexa es poco más que “ordenar” el conjunto (ie, es algo así como n\log n), esto te da un algoritmo que tarde aprox n^4. Si $\latex n$ es chico, esto no está tan mal.

    Pero, como casi todos los problemas de `cercanía’, si uno construye el diagrama de Voronoi de los puntos, es más rápido todo. Si mal no recuerdo, podés encontrar el disco que querés en tiempo n\log n. Fijate en el libro de Preparata y Shamos sobre geometría computacional: creo que ahí estan los detalles—seguro, al menos, ahi está la construcción del diagrama de Voronoi. A la hora de transformar esto en un programa, seguramente vas a encontrar alguna librería ya escrita que encuentre el diagrama.

    En \mathbb{R^3} imagino que es igual, aunque la complejidad va ser peor.

  3. Grin Without a Cat said

    Qhull, que Google encuentra rápidamente, es, aparte de unos varios programas que hacen varias cosas, una librería que calcula diagramas de Voronoi—con una licencia lo suficientemente grácil como para que Matlab y Maple la incluyan.

  4. julianhaddad said

    Tengo una idea que puede ser una tontería, (dado que no tengo idea de qué es un algoritmo eficiente) pero es divertida.
    Supongamos que los puntos son los (x_i,y_i), 1 \leq i \leq n
    dado un punto (x,y) llamo F(x,y) a la máxima de las distancias de (x,y) a los (x_i,y_i) al cuadrado, F(x,y)=\max\{d_i(x,y) : 1 \leq i \leq n\} donde d_i(x,y) = (x-x_i)^2+(y-y_i)^2 pero sé que || x ||_p \rightarrow || x ||_{\infty} cuando p\rightarrow \infty. sea
    F_p(x,y) = (\sum_{i=1}^n d_i(x,y)^p)^{\frac 1 p}
    Entonces mi propuesta es encontrar el mínimo de Fp usando análisis, para lo cual hay que resolver un sistema de 2 ecuaciones polinomiales de grado 2p. Y como podemos pensar que el dominio es un compacto, existe una sucesión de mínimos que va a converger al mínimo de F. =)

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: