algorithm - longest - ¿Cómo encontrar sobres superiores de líneas intersecadas en O(nlogn)?

longest subsequence (8)

Aquí hay un algoritmo sensible a la salida:

for t = 0, 1, 2 ... do k = 2^(2^t) arbitrarily partition the segments into ceiling(n/k) subsets each of size at most k run any O(nlogn) time algorithm on each group yielding ceiling(n/k) monotone polygonal chains find the upper envelope of these monotone polygonal chains, and abort if the output size exceeds k end for

tiempo de ejecución: O (nlogk), donde k = número de segmentos en la respuesta. Esta es esencialmente una idea dual del algoritmo de casco convexo de Chan.

Descargo de responsabilidad: Sí, esta es una tarea y lo estoy pensando durante un par de días, pero no pude encontrar una manera de hacerlo.

Entonces hay n líneas rectas (y = ax + b) y quiero encontrar sobres superiores de ellas (parte en negrita en la imagen). Tiene que estar en O (nlogn).

Lo que entiendo es que necesito encontrar una manera de ignorar algunas de las líneas, porque si busco todas las líneas no será O (nlogn).

Estoy pensando en un enfoque de divide y vencerás para poder dividir la lista en dos y continuar de forma recursiva hasta la solución. Pero entonces no sé cómo deshacerme de algunas de las líneas. Claramente, no necesito considerar algunas de las líneas de fondo de la imagen porque es imposible que contribuyan a la solución. Pero no se me ocurrió nada. Cualquier consejo es apreciado.

Este es un comentario sobre la respuesta de Simones, que creo que es incorrecto.

Ahora comenzamos a considerar las líneas lmin, lmax, que son las líneas con la más pequeña y la más grande; contribuirán con seguridad con los puntos dados desde las intersecciones con la segunda línea más pequeña y la segunda más grande, y sumamos esos 2 puntos a la envoltura superior.

No necesariamente tiene que ser el caso. La parte que contribuye al sobre podría ser la parte de lmin a cualquier otra línea de la lista. Ejemplo:

Además, parece razonable excluir todas las líneas con y <= yi en x = xi. Pero estas líneas NO se identifican por tener un valor b entre b_lmin y b_lmax (si esto es lo que quieres decir, es un poco incierto). Un ejemplo contrario a esto, es:

Espero no haber entendido mal su descripción de su algoritmo. Si tengo, por favor hágamelo saber!

Imagino rayos enviados desde (0, + INFINIDAD) a nuestro conjunto de líneas. El primer punto de colisión de los rayos es parte de nuestra envoltura. Cuando las 3 colisiones consecutivas no son colineales, se envían más rayos entre los puntos de colisión 1 y 2, y 2 y 3. Para las colisiones consecutivas que llegan a la misma línea, solo se debe registrar una en un conjunto de salida. Luego, usaría el conjunto de líneas colisionadas para generar el vértice real entre cada par de líneas.

Desafortunadamente, esto daría una gran estimación del sobre, pero no una respuesta exacta ("¿ya que necesitarías infinitos rayos?).

Paso 1) Lanza tu primera salva de rayos {0, -Pi / 4, -3Pi / 4, -Pi}

Paso 2) Lanzar rayos entre golpes consecutivos de líneas únicas (1 y 2, y 3 y 4). Inserción en los resultados y selección de las repeticiones internas (aciertos de línea que tienen la misma línea en ambos lados).

Paso 3) Repita el Paso 2 hasta (medida de precisión mágica).

Paso 4) Genere su lista de puntos de envolvente haciendo una intersección de líneas entre todas las líneas únicas consecutivas en los resultados.

No sé cómo resolver esto, pero tenga en cuenta que conoce las líneas de más a la izquierda y de más a la derecha (ya que x tiende a menos y más a infinito), ya que tendrán los valores más pequeños y más grandes de a (a medida que x se vuelve grande, el ax domina cualquier valor de b ).

dado eso, puede encontrar dónde se intersecan y descartar líneas debajo de ese punto (creo). y entonces probablemente puedas iterar de alguna manera. (por ejemplo, encontrando la línea más alta en la coordenada x de la intersección, y luego repitiendo con los dos puntos que intersectan las dos líneas originales ...). Espero que ayude.

Sé que la pregunta es bastante antigua, pero no estoy de acuerdo con todos los argumentos dados, en particular con los de la respuesta aceptada.

El problema no parece ser solucionable por algún argumento directo. De hecho, como resultado, la mayoría de los algoritmos de dividir y conquistar solo logran un tiempo de ejecución en O (n log na (n)), que contiene la función de Ackerman inversa a (n).

Sin embargo, hay un documento que proporciona una solución agradable, pero no trivial: http://www.sciencedirect.com/science/article/pii/0020019089901361

Tenga en cuenta que el algoritmo está diseñado para segmentos de línea finitos. Sin embargo, es fácil proporcionar límites para el punto de intersección más pequeño y más grande posible y para "convertir" las funciones afines en segmentos de línea en estos intervalos.

Si lo veo bien, las líneas siempre contribuyen al "sobre" en el orden de su valor "a". Así que ordénalos por a. Si tienes dos con la misma a, son paralelos y la b decide cuál está por encima de la otra (puedes omitir la inferior). Si conoce el orden de las líneas, puede calcular el punto de intersección para dos líneas sucesivas en O (1). Así que, básicamente, no es más que una ordenación, y eso es O (n log n).

EDIT : Ok, uno de los comentarios es correcto: no hay líneas paralelas que no se distribuyan en el sobre, la razón es que contribuirían al sobre más allá del punto de inflexión. Pero el hecho de que los segmentos del sobre sean de las líneas en el orden de su "a" sigue siendo correcto (y eso significa que siempre tiene el segmento de inicio y final).

La pregunta es cómo determinaría qué línea contribuye al sobre y cuál no. Usted escanea una vez sobre la matriz para encontrar el punto de inflexión (que debe ser donde "a" se enciende la señal). Comienzas desde allí una vez hacia abajo (disminuyendo las a) y una vez hacia arriba (aumentando las a). Calcula el punto de intersección con la siguiente línea: si está en el lado incorrecto (no disminuye / aumenta) x, omítelo. El escaneo para eliminar los paralelos (con igual a) todavía debe aplicarse después de la clasificación, ya que esto omite el caso patológico al calcular el punto de intersección.

Un consejo: este problema es básicamente un doble del problema del casco convexo .

Solución: Si trata cada línea y=ax+b como un punto (a,b) , y agrega un "punto" adicional a (0, -infinity) , debería poder incluir esto en cualquier algoritmo de casco convexo 2D y Obtener una solución correcta.

Nota: A la inversa, cualquier solución de este problema también puede usarse para construir un algoritmo de casco convexo 2D del mismo O ().

Editar: Una solicitud para probarlo ...

Para que un punto (x,y) esté sobre una línea particular y=ax+b , tiene la desigualdad ax - y + b > 0 .

Esta desigualdad también es equivalente al punto (-a,b) está sobre la línea (b)=x(-a)+y , donde x es la pendiente e y es la intersección.

Esta duality nos permite tratar los puntos como líneas y las líneas como puntos: cualquier prueba o algoritmo en puntos y líneas se puede mapear en uno igualmente válido con líneas y puntos invertidos.

En este caso: el casco convexo de un conjunto de puntos 2D determina los puntos "extremos" que no son combinaciones convexas de otros, así como las líneas entre los puntos extremos sucesivos. De manera correspondiente, la versión dual del casco convexo determina las líneas "extremas" que no son combinaciones convexas de otras, así como los puntos de intersección entre las líneas extremas sucesivas. Este es el sobre del conjunto de líneas dado.

El doble del casco convexo le da tanto el sobre superior como el inferior del conjunto de líneas de entrada. Como solo desea el sobre superior de sus líneas, debe agregar una línea más baja que cualquier línea regular posible para eliminar el sobre más bajo. Alternativamente, puede mirar a través de la solución y elegir solo intersecciones con pendiente creciente.

A la inversa, cualquier solución de este problema puede usarse para determinar el casco convexo superior de un conjunto de puntos. Si lo ejecuta dos veces, una para las líneas {(a, b)} y otra vez para las líneas {(-a, -b)}, obtendrá un casco convexo completo.

Primero construimos dos árboles de búsqueda binarios diferentes para las líneas, uno con las líneas ordenadas según su a y el otro según su b .

Ahora comenzamos a considerar las líneas lmin , lmax , que son las líneas con la más pequeña y la más grande; contribuirán con seguridad con los puntos dados desde las intersecciones con la segunda línea más pequeña y la segunda más grande, y sumamos esos 2 puntos a la envoltura superior.

Ahora consideramos la intersección (xi,yi) entre lmin y lmax e idealmente dibujamos la línea vertical x = xi . Ahora tenemos que identificar las líneas que se intersecan x = xi en una coordenada y0 st y0 <= yi y eliminar todas estas líneas de ambos árboles.

¿Cómo podemos identificar estas líneas? Encontramos todas las líneas con una b st lmin <= b <= lmax , usando el segundo árbol.

Al final también lmin y lmax de los árboles.

Ahora nos ocuparemos de los nuevos árboles obtenidos.