Búsqueda de segmentos superiores de la intersección de las parábolas

Question

Tengo varias parábolas ($y = ax^2 + bx + c$) que pueden cruzarse entre sí (o algunos de ellos puede que no se cruzan). Estoy tratando de encontrar segmentos superiores de estas parábolas, por ejemplo, parte en negrita en la imagen:

Necesito encontrarlo en $O(n\log n)$. Hay una solución para la versión de línea de este problema: http://stackoverflow.com/questions/7420193/how-to-find-upper-envelopes-of-intersected-lines-in-onlogn

Pero no puedo encontrar una manera de aplicar esta solución a la ecuación cuadrática versión, ya que hay $a$, $b$ y $c$ variables a considerar. Cualquier ayuda será apreciada.

Answer 1

Usted está en busca de lo que se denomina en la literatura de la parte superior de la envolvente de una colección de $x$-monotonía curvas. En realidad, la búsqueda de "envolvente inferior" le dará más éxitos; obviamente son equivalentes. Usted puede mirar en el CGAL aplicación, por ejemplo, a través de este enlace:

La actualización. A la dirección de joriki comentario, permítanme citar el Teorema 6.5 (p. 137) de la Sharir-Agarwal libro, Davenport-Schinzel Secuencias y Sus Aplicaciones Geométricas:

Dada una colección de $\Gamma$ de $n$ $x$-monotono Jordania arcos, cada par de que se cruzan en la mayoría de los $s$ puntos de la envolvente inferior de $\Gamma$ puede ser calculado en $O(\lambda_{s+1}(n) \log n)$ del tiempo.

Debido a $s=2$ en el caso de las parábolas, el término pertinente es $\lambda_3(n)$. Esta $\lambda$-la función es una combinatoria de la cantidad que se ha demostrado tiene ciertos límites. Un apretado obligado es conocido por $\lambda_3(n)$: es $\Theta( n \alpha(n) )$ donde $\alpha(n)$ es la inversa de la función de Ackermann, es decir, $\le 5$ en este universo. Por lo que la complejidad en el teorema es sólo un pelo por encima de $O( n \log n)$.

Answer 2

[Nota: La primera versión de esta respuesta era incorrecta; los comentarios se refieren a la versión incorrecta.]

Voy a asumir que las parábolas todas abierto hacia abajo como en el diagrama; si no, las cosas pueden ser más complicadas. Voy a tomar $y$ a aumentar hacia abajo para simplificar las cosas.

Una parábola es el lugar geométrico de los puntos a igual distancia de un punto (el foco) y una recta (directriz). En el presente caso, todas las directrices son horizontales. Si el peso de la distancia del foco mediante la adición de la $y$ coordenadas de la directriz, podemos considerar la parábola como lugar geométrico de los puntos donde este ponderado de la distancia del foco es igual a la $y$ coordenadas del punto. Por encima de la parábola, la ponderación de la distancia del foco es mayor, y por debajo de la parábola, el $y$ coordinar es mayor. Para un punto en la parte superior de la envolvente, la ponderación de la distancia desde el foco de la parábola que forman la envolvente es igual a la $y$ coordenadas del punto, y el promedio ponderado de las distancias de todos los otros focos son menores o iguales a esta $y$ coordinar. Por lo tanto, si se forma el aditiva ponderado diagrama de Voronoi de los focos, la parabólica, los segmentos que forman la parte superior de la envolvente de la mentira en las regiones de Voronoi de los correspondientes a los focos.

De ello se desprende que las intersecciones en las que la parte superior de la envolvente cambia de una parábola con otra mentira en los bordes de la ponderado diagrama de Voronoi. El promedio ponderado de diagrama de Voronoi puede ser calculado en $O(n\log n)$ el tiempo, por ejemplo el uso de Fortune algoritmo; la modificación de la forma aditiva ponderado caso es sencillo y se describe en el documento original (Sección 4). Desde la ponderado diagrama de Voronoi es un plano gráfico con un mínimo grado de los vértices $3$ $n$ caras, Euler fórmula implica que ha $O(n)$ bordes. Por lo tanto, la parte superior de la envolvente puede ser construido en $O(n\log n)$ tiempo calculando el promedio ponderado de diagrama de Voronoi, encontrando las intersecciones de las parábolas cuyo Voronoi regiones comparten un borde, ordenar las intersecciones de acuerdo a su $x$ coordenadas y se recorre de izquierda a derecha para determinar en cuál de ellos la envolvente cambia a otra parábola.

Ver también estas notas para una discusión de la relación entre el superior/inferior de la envolvente de un conjunto de parábolas y un diagrama de Voronoi.