Búsqueda paramétrica

En el diseño y análisis de algoritmos de optimización combinatoria , la búsqueda paramétrica es una técnica inventada por Nimrod Megiddo (1983) para transformar un algoritmo de decisión (¿este problema de optimización tiene una solución con una calidad mejor que un umbral dado?) en un algoritmo de optimización (encontrar la mejor solución). Se utiliza con frecuencia para resolver problemas de optimización en geometría computacional .

Técnica

La idea básica de la búsqueda paramétrica es simular un algoritmo de prueba que toma como entrada un parámetro numérico , como si se estuviera ejecutando con el valor de solución óptima (desconocido) como entrada. Se supone que este algoritmo de prueba se comporta de manera discontinua cuando , y que opera sobre su parámetro solo mediante comparaciones simples de con otros valores calculados, o probando el signo de funciones polinómicas de bajo grado de . Para simular el algoritmo, es necesario simular cada una de estas comparaciones o pruebas, aunque se desconozca el del algoritmo simulado. Para simular cada comparación, la búsqueda paramétrica aplica un segundo algoritmo, un algoritmo de decisión , que toma como entrada otro parámetro numérico , y que determina si es superior, inferior o igual al valor de solución óptima . ${\estilo de visualización X}$ ${\estilo de visualización X^{*}}$ $X=X^{*}$ ${\estilo de visualización X}$ ${\estilo de visualización X}$ ${\estilo de visualización X}$ ${\estilo de visualización X}$ ${\estilo de visualización Y}$ ${\estilo de visualización Y}$ ${\estilo de visualización X^{*}}$

Dado que el algoritmo de decisión se comporta necesariamente de manera discontinua en , el mismo algoritmo también se puede utilizar como algoritmo de prueba. Sin embargo, muchas aplicaciones utilizan otros algoritmos de prueba (a menudo, algoritmos de ordenación por comparación ). Las versiones avanzadas de la técnica de búsqueda paramétrica utilizan un algoritmo paralelo como algoritmo de prueba y agrupan las comparaciones que se deben simular en lotes, con el fin de reducir significativamente la cantidad de instancias del algoritmo de decisión. ${\estilo de visualización X^{*}}$

Algoritmo de prueba secuencial

En la forma más básica de la técnica de búsqueda paramétrica, tanto el algoritmo de prueba como los algoritmos de decisión son algoritmos secuenciales (no paralelos), posiblemente el mismo algoritmo entre sí. La técnica simula el algoritmo de prueba paso a paso, como se ejecutaría si se le diera el valor de solución óptima (desconocido) como su parámetro . Siempre que la simulación llega a un paso en el que el algoritmo de prueba compara su parámetro con algún otro número , no puede realizar este paso haciendo una comparación numérica, ya que no sabe cuál es. En cambio, llama al algoritmo de decisión con el parámetro , y usa el resultado del algoritmo de decisión para determinar la salida de la comparación. De esta manera, el tiempo para la simulación termina siendo igual al producto de los tiempos para los algoritmos de prueba y decisión. Debido a que se supone que el algoritmo de prueba se comporta de manera discontinua en el valor de solución óptima, no se puede simular con precisión a menos que uno de los valores de parámetro pasados al algoritmo de decisión sea realmente igual al valor de solución óptima. Cuando esto sucede, el algoritmo de decisión puede detectar la igualdad y guardar el valor de solución óptima para una salida posterior. Si el algoritmo de prueba necesita conocer el signo de un polinomio en , esto se puede simular nuevamente pasando las raíces del polinomio al algoritmo de decisión para determinar si el valor de la solución desconocida es una de estas raíces o, si no, entre cuáles dos raíces se encuentra. ${\estilo de visualización X}$ ${\estilo de visualización X}$ ${\estilo de visualización Y}$ ${\estilo de visualización X}$ ${\estilo de visualización Y}$ ${\estilo de visualización Y}$ ${\estilo de visualización X}$

Un ejemplo considerado tanto por Megiddo (1983) como por van Oostrum & Veltkamp (2002) se refiere a un sistema de un número impar de partículas, todas moviéndose hacia la derecha a diferentes velocidades constantes a lo largo de la misma línea. La mediana de las partículas, también, tendrá un movimiento hacia la derecha, pero uno que es lineal por partes en lugar de tener una velocidad constante, porque diferentes partículas serán la mediana en diferentes momentos. Inicialmente, las partículas, y su mediana, están a la izquierda del origen de la línea, y eventualmente ellas y su mediana estarán todas a la derecha del origen. El problema es calcular el tiempo en el que la mediana se encuentra exactamente en el origen. Un algoritmo de decisión de tiempo lineal es fácil de definir: para cualquier tiempo , uno puede calcular la posición de cada partícula en el tiempo y contar el número de partículas en cada lado del origen. Si hay más partículas a la izquierda que a la derecha, entonces , y si hay más partículas a la derecha que a la izquierda, entonces . Cada paso de este algoritmo de decisión compara el parámetro de entrada con el tiempo en que una de las partículas cruza el origen. ${\estilo de visualización t_{0}}$ ${\estilo de visualización t}$ ${\estilo de visualización t}$ $estilo de visualización t<t_{0}}$ $estilo de visualización t>t_{0}}$ ${\estilo de visualización t}$

El uso de este algoritmo de decisión como algoritmo de prueba y algoritmo de decisión de una búsqueda paramétrica conduce a un algoritmo para encontrar el tiempo óptimo en tiempo total cuadrático. Para simular el algoritmo de decisión para el parámetro , la simulación debe determinar, para cada partícula, si su tiempo de cruce es anterior o posterior a , y, por lo tanto, si está a la izquierda o a la derecha del origen en el tiempo . La respuesta a esta pregunta para una sola partícula (comparando el tiempo de cruce de la partícula con el tiempo de cruce óptimo desconocido ) se puede realizar ejecutando el mismo algoritmo de decisión con el tiempo de cruce de la partícula como su parámetro. Por lo tanto, la simulación termina ejecutando el algoritmo de decisión en cada uno de los tiempos de cruce de la partícula, uno de los cuales debe ser el tiempo de cruce óptimo. Ejecutar el algoritmo de decisión una vez toma tiempo lineal, por lo que ejecutarlo por separado en cada tiempo de cruce toma tiempo cuadrático. ${\estilo de visualización t_{0}}$ ${\estilo de visualización t_{0}}$ ${\estilo de visualización t_{0}}$ ${\estilo de visualización t_{0}}$ ${\estilo de visualización t_{0}}$

Megiddo señala que, para este problema específico, existe un algoritmo de tiempo lineal simple que no implica una búsqueda paramétrica: solo determina el tiempo en el que cada partícula cruza el origen y devuelve la mediana de estos tiempos. Sin embargo, explica que la búsqueda paramétrica a menudo coincide con el mejor tiempo de ejecución conocido o proporciona el algoritmo más rápido conocido para problemas más avanzados.

Algoritmo de prueba paralela

Como ya observó Megiddo (1983), la técnica de búsqueda paramétrica puede acelerarse sustancialmente reemplazando el algoritmo de prueba simulado por un algoritmo paralelo eficiente , por ejemplo en el modelo de máquina de acceso aleatorio paralelo (PRAM) de computación paralela, donde una colección de procesadores operan en sincronía en una memoria compartida , y todos realizan la misma secuencia de operaciones en diferentes direcciones de memoria. Si el algoritmo de prueba es un algoritmo PRAM que utiliza procesadores y lleva tiempo (es decir, pasos en los que cada procesador realiza una sola operación), entonces cada uno de sus pasos puede simularse utilizando el algoritmo de decisión para determinar los resultados de, como máximo, comparaciones numéricas. Al encontrar un valor mediano o cercano a la mediana en el conjunto de comparaciones que necesitan evaluarse, y pasar este único valor al algoritmo de decisión, es posible eliminar la mitad o casi la mitad de las comparaciones con una sola llamada del algoritmo de decisión. Al reducir repetidamente a la mitad el conjunto de comparaciones requeridas por la simulación de esta manera, hasta que no quede ninguna, es posible simular los resultados de las comparaciones numéricas utilizando solo llamadas al algoritmo de decisión. Por lo tanto, el tiempo total para la búsqueda paramétrica en este caso se convierte (para la simulación en sí) en el tiempo de las llamadas al algoritmo de decisión (para lotes de comparaciones, tomando llamadas por lote). A menudo, para un problema que se puede resolver de esta manera, el producto de tiempo-procesador del algoritmo PRAM es comparable al tiempo para un algoritmo de decisión secuencial, y el tiempo paralelo es polilogarítmico , lo que lleva a un tiempo total para la búsqueda paramétrica que es más lento que el algoritmo de decisión por solo un factor polilogarítmico. ${\estilo de visualización P}$ ${\estilo de visualización T}$ ${\estilo de visualización T}$ ${\estilo de visualización P}$ ${\estilo de visualización P}$ $O(\log P)$ $O(PT)$ $O(T\log P)$ ${\estilo de visualización T}$ $O(\log P)$

En el caso del problema de ejemplo de encontrar el tiempo de cruce de la mediana de partículas en movimiento, el algoritmo de prueba secuencial puede reemplazarse por un algoritmo de ordenamiento paralelo que ordena las posiciones de las partículas en el tiempo dado por el parámetro del algoritmo, y luego usa el orden ordenado para determinar la partícula mediana y encontrar el signo de su posición. La mejor opción para este algoritmo (según su análisis teórico, si no en la práctica) es la red de ordenamiento de Ajtai , Komlós y Szemerédi (1983). Esto puede interpretarse como un algoritmo PRAM en el que el número de procesadores es proporcional a la longitud de entrada y el número de pasos paralelos es logarítmico. Por lo tanto, simular este algoritmo secuencialmente toma tiempo para la simulación en sí, junto con lotes de comparaciones, cada uno de los cuales puede manejarse mediante llamadas al algoritmo de decisión de tiempo lineal. Juntando estos límites de tiempo se obtiene el tiempo total para la búsqueda paramétrica. Este no es el momento óptimo para este problema (el mismo problema se puede resolver más rápidamente observando que el tiempo de cruce de la mediana es igual a la mediana de los tiempos de cruce de las partículas), pero la misma técnica se puede aplicar a otros problemas de optimización más complicados y, en muchos casos, proporciona el algoritmo fuertemente polinomial más rápido conocido para estos problemas. ${\estilo de visualización n}$ ${\estilo de visualización P}$ ${\estilo de visualización n}$ $O(n\log n)$ $O(\log n)$ $O(\log n)$ $Estilo de visualización O(n\log ^{2}n)}$

Debido a los grandes factores constantes que surgen en el análisis de la red de ordenamiento AKS, la búsqueda paramétrica que utiliza esta red como algoritmo de prueba no es práctica. En su lugar, van Oostrum y Veltkamp (2002) sugieren utilizar una forma paralela de quicksort (un algoritmo que divide repetidamente la entrada en dos subconjuntos y luego ordena recursivamente cada subconjunto). En este algoritmo, el paso de partición es masivamente paralelo (cada elemento de entrada debe compararse con un elemento pivote elegido) y las dos llamadas recursivas pueden realizarse en paralelo entre sí. El algoritmo paramétrico resultante es más lento en el peor de los casos que un algoritmo basado en la red de ordenamiento AKS. Sin embargo, van Oostrum y Veltkamp sostienen que si se guardan los resultados de los algoritmos de decisión anteriores (de modo que solo las comparaciones no resueltas por estos resultados conduzcan a llamadas adicionales al algoritmo de decisión) y los valores de comparación probados por el algoritmo de prueba simulado se distribuyen de manera suficientemente uniforme, entonces, a medida que el algoritmo avanza, el número de comparaciones no resueltas generadas en cada paso de tiempo será pequeño. Basándose en este análisis heurístico y en resultados experimentales con una implementación del algoritmo, sostienen que un algoritmo de búsqueda paramétrica basado en quicksort será más práctico de lo que sugeriría su análisis del peor de los casos.

Ordenación desincronizada

Cole (1987) optimizó aún más la técnica de búsqueda paramétrica para casos (como el ejemplo) en los que el algoritmo de prueba es un algoritmo de ordenamiento por comparación. Para la red de ordenamiento AKS y algunos otros algoritmos de ordenamiento que se pueden utilizar en su lugar, Cole observa que no es necesario mantener los procesadores simulados sincronizados entre sí: en cambio, se puede permitir que algunos de ellos avancen más a través del algoritmo de ordenamiento mientras que otros esperan a que se determinen los resultados de sus comparaciones. Basándose en este principio, Cole modifica la simulación del algoritmo de ordenamiento, de modo que mantenga una colección de comparaciones simuladas no resueltas que pueden no provenir todas del mismo paso de tiempo paralelo del algoritmo de prueba. Al igual que en la versión paralela sincronizada de la búsqueda paramétrica, es posible resolver la mitad de estas comparaciones encontrando el valor de comparación mediano y llamando al algoritmo de decisión sobre este valor. Luego, en lugar de repetir este procedimiento de reducción a la mitad hasta que la colección de comparaciones no resueltas se vacíe, Cole permite que los procesadores que estaban esperando las comparaciones resueltas avancen a través de la simulación hasta que lleguen a otra comparación que debe resolverse. Usando este método, Cole demuestra que un algoritmo de búsqueda paramétrica en el que el algoritmo de prueba está ordenando puede completarse usando solo un número logarítmico de llamadas al algoritmo de decisión, en lugar de las llamadas hechas por la versión original de búsqueda paramétrica de Megiddo. En lugar de usar la red de ordenamiento AKS, también es posible combinar esta técnica con un algoritmo de ordenamiento por fusión paralela de Cole (1988), lo que resulta en límites de tiempo con factores constantes más pequeños que, sin embargo, todavía no son lo suficientemente pequeños como para ser prácticos. Se puede obtener una aceleración similar para cualquier problema que pueda calcularse en una red de computación distribuida de grado acotado (como lo es la red de ordenamiento AKS), ya sea mediante la técnica de Cole o mediante una técnica relacionada de simulación de múltiples rutas de computación (Fernández-Baca 2001). $O(\log ^{2}n)$

Goodrich y Pszona (2013) combinan la mejora teórica de Cole con las aceleraciones prácticas de van Oostrum y Veltkamp (2002). En lugar de utilizar un ordenamiento rápido paralelo, como hicieron van Oostrum y Veltkamp, utilizan el ordenamiento por cajas, una variante del ordenamiento rápido desarrollada por Reischuk (1985) en la que el paso de partición divide la entrada aleatoriamente en subproblemas más pequeños en lugar de solo dos subproblemas. Al igual que en la técnica de Cole, utilizan una búsqueda paramétrica desincronizada, en la que se permite que cada hilo de ejecución independiente del algoritmo de ordenamiento paralelo simulado avance hasta que necesite determinar el resultado de otra comparación, y en la que el número de comparaciones no resueltas se reduce a la mitad al encontrar el valor de comparación mediano y llamar al algoritmo de decisión con ese valor. Como muestran, el algoritmo de búsqueda paramétrica aleatoria resultante solo realiza un número logarítmico de llamadas al algoritmo de decisión con alta probabilidad, lo que coincide con el análisis teórico de Cole. Una versión ampliada de su artículo incluye resultados experimentales de una implementación del algoritmo, que muestran que el tiempo total de ejecución de este método en varios problemas de optimización geométrica natural es similar al de la mejor implementación de búsqueda paramétrica sincronizada (el método basado en quicksort de van Oostrum y Veltkamp): un poco más rápido en algunos problemas y un poco más lento en otros. Sin embargo, el número de llamadas que realiza al algoritmo de decisión es significativamente menor, por lo que este método obtendría mayores beneficios en aplicaciones de búsqueda paramétrica donde el algoritmo de decisión es más lento. $O({\sqrt {n}})$

En el problema de ejemplo de hallar el tiempo medio de paso de un punto, tanto el algoritmo de Cole como el de Goodrich y Pszona obtienen el tiempo de recorrido . En el caso de Goodrich y Pszona, el algoritmo es aleatorio y obtiene este tiempo límite con alta probabilidad. $O(n\log n)$

Comparación con la búsqueda binaria y la búsqueda aleatoria

El método de bisección (búsqueda binaria) también se puede utilizar para transformar la decisión en optimización. En este método, se mantiene un intervalo de números, que se sabe que contiene el valor de la solución óptima, y se reduce repetidamente el intervalo llamando al algoritmo de decisión sobre su valor mediano y manteniendo solo la mitad del intervalo por encima o por debajo de la mediana, según el resultado de la llamada. Aunque este método solo puede encontrar una aproximación numérica al valor de la solución óptima, lo hace en un número de llamadas al algoritmo de decisión proporcional al número de bits de precisión de exactitud para esta aproximación, lo que da como resultado algoritmos débilmente polinomiales .

En cambio, cuando es aplicable, la búsqueda paramétrica encuentra algoritmos fuertemente polinómicos, cuyo tiempo de ejecución es una función únicamente del tamaño de la entrada y es independiente de la precisión numérica. Sin embargo, la búsqueda paramétrica conduce a un aumento en la complejidad temporal (en comparación con el algoritmo de decisión) que puede ser mayor que la logarítmica. Debido a que son fuertemente polinómicos en lugar de débilmente polinómicos, los algoritmos basados en la búsqueda paramétrica son más satisfactorios desde un punto de vista teórico. En la práctica, la búsqueda binaria es rápida y a menudo mucho más simple de implementar, por lo que se necesitan esfuerzos de ingeniería de algoritmos para hacer que la búsqueda paramétrica sea práctica. No obstante, van Oostrum y Veltkamp (2002) escriben que "si bien un enfoque de búsqueda binaria simple a menudo se recomienda como un reemplazo práctico para la búsqueda paramétrica, nuestro algoritmo [de búsqueda paramétrica] lo supera" en las comparaciones experimentales que realizaron.

Cuando solo se trata del rendimiento esperado, se puede utilizar una técnica de optimización aleatoria (Chan 1998) en lugar de la búsqueda paramétrica. Este método solo implica un aumento constante de la complejidad temporal y, al mismo tiempo, genera un algoritmo fuertemente polinomial.

Aplicaciones

La búsqueda paramétrica se ha aplicado en el desarrollo de algoritmos eficientes para problemas de optimización, particularmente en geometría computacional (Agarwal, Sharir y Toledo 1994). Entre ellos se incluyen los siguientes:

Un punto central de un conjunto de puntos en un espacio euclidiano es un punto tal que cualquier semiespacio que contenga el punto central también contiene una fracción constante de los puntos de entrada. Para espacios de dimensión 1, la fracción óptima que se puede lograr es siempre al menos . Los algoritmos basados en búsqueda paramétrica para construir puntos centrales bidimensionales se mejoraron posteriormente para el tiempo lineal utilizando otras técnicas algorítmicas. Sin embargo, esta mejora no se extiende a dimensiones superiores. En tres dimensiones, la búsqueda paramétrica se puede utilizar para encontrar puntos centrales en el tiempo (Cole 1987). ${\estilo de visualización d}$ ${\estilo de visualización 1/(d+1)}$ $O(n^{2}\log ^{4}n)$
La búsqueda paramétrica se puede utilizar como base para un algoritmo de tiempo para el estimador de Theil–Sen , un método en estadística robusta para ajustar una línea a un conjunto de puntos que es mucho menos sensible a los valores atípicos que la regresión lineal simple (Cole et al. 1989). $O(n\log n)$
En gráficos de computadora , el problema del disparo de rayos (determinar el primer objeto en una escena que es intersectado por una línea de visión o haz de luz dado) se puede resolver combinando la búsqueda paramétrica con una estructura de datos para un problema más simple, probando si alguno de un conjunto dado de obstáculos ocluye un rayo dado (Agarwal y Matoušek 1993).
El mayor problema de la línea recta consiste en encontrar el segmento de línea más largo que se encuentre completamente dentro de un polígono dado . Se puede resolver en tiempo , para polígonos de lados y cualquier , utilizando un algoritmo basado en búsqueda paramétrica (Agarwal, Sharir y Toledo 1994). $O(n^{8/5+\epsilon })$ ${\estilo de visualización n}$ $\epsilon >0$
El anillo que contiene un conjunto de puntos dado y tiene el ancho más pequeño posible (diferencia entre los radios interno y externo) se puede utilizar como una medida de la redondez del conjunto de puntos. Nuevamente, este problema se puede resolver en tiempo , para polígonos de lados y cualquier , utilizando un algoritmo basado en búsqueda paramétrica (Agarwal, Sharir y Toledo 1994). $O(n^{8/5+\epsilon })$ ${\estilo de visualización n}$ $\epsilon >0$
La distancia de Hausdorff entre las traslaciones de dos polígonos, con la traslación elegida para minimizar la distancia, se puede encontrar utilizando la búsqueda paramétrica en el tiempo , donde y son los números de lados de los polígonos (Agarwal, Sharir y Toledo 1994). $O((mn)^{2}\log ^{3}mn)$ ${\estilo de visualización m}$ ${\estilo de visualización n}$
La distancia de Fréchet entre dos cadenas poligonales se puede calcular utilizando una búsqueda paramétrica en el tiempo , donde y son los números de segmentos de las curvas (Alt y Godau 1995). $O(mn\log mn)$ ${\estilo de visualización m}$ ${\estilo de visualización n}$
Para puntos en el plano euclidiano, que se mueven a velocidades constantes, el tiempo en el que los puntos obtienen el diámetro más pequeño (y el diámetro en ese momento) se puede encontrar utilizando una variación de la técnica de Cole en el tiempo . La búsqueda paramétrica también se puede utilizar para otros problemas similares de encontrar el tiempo en el que alguna medida de un conjunto de puntos en movimiento obtiene su valor mínimo, para medidas que incluyen el tamaño de la bola mínima que lo encierra o el peso del árbol de expansión máximo (Fernández-Baca 2001). ${\estilo de visualización n}$ $Estilo de visualización O(n\log ^{2}n)}$

Referencias

Agarwal, Pankaj K. ; Matoušek, Jiří (1993), "Disparo de rayos y búsqueda paramétrica", SIAM Journal on Computing , 22 (4): 794–806, CiteSeerX 10.1.1.298.6047 , doi :10.1137/0222051, MR 1227762
Agarwal, Pankaj K. ; Sharir, Micha ; Toledo, Sivan (1994), "Aplicaciones de la búsqueda paramétrica en la optimización geométrica", Journal of Algorithms , 17 (3): 292–318, doi : 10.1006/jagm.1994.1038 , MR 1300253, S2CID 380722.
Ajtai, M. ; Komlós, J. ; Szemerédi, E. (1983), "Una red de ordenamiento $O (n log n) ",$ Actas del 15.º Simposio ACM sobre teoría de la computación (STOC '83) , págs. 1–9, doi :10.1145/800061.808726, ISBN 0-89791-099-0, S2CID15311122 .
Alt, Helmut ; Godau, Michael (1995), "Cálculo de la distancia de Fréchet entre dos curvas poligonales" (PDF) , Revista internacional de geometría computacional y aplicaciones , 5 (1–2): 75–91, doi :10.1142/S0218195995000064, MR 1331177.
Chan, Timothy M (1998), "Aplicaciones geométricas de una técnica de optimización aleatoria", Actas del decimocuarto simposio anual sobre geometría computacional, págs. 269-278, doi : 10.1145/276884.276915, ISBN 0-89791-973-4.
Cole, Richard (1987), "Reducir la velocidad de las redes de ordenamiento para obtener algoritmos de ordenamiento más rápidos", Journal of the ACM , 34 (1): 200–208, doi : 10.1145/7531.7537 , MR 0882669, S2CID 2301419.
Cole, Richard (1988), "Ordenamiento por fusión paralela", SIAM Journal on Computing , 17 (4): 770–785, doi :10.1137/0217049, MR 0953293, S2CID 2416667.
Cole, Richard; Salowe, Jeffrey S.; Steiger, WL; Szemerédi, Endre (1989), "Un algoritmo de tiempo óptimo para la selección de pendientes", SIAM Journal on Computing , 18 (4): 792–810, doi :10.1137/0218055, MR 1004799.
Fernández-Baca, D. (2001), "Sobre la búsqueda paramétrica no lineal", Algorithmica , 30 (1): 1–11, doi :10.1007/s00453-001-0001-2, MR 1816864, S2CID 20320912.
Goodrich, Michael T. ; Pszona, Paweł (2013), "La técnica de búsqueda paramétrica de Cole hecha práctica" (PDF) , Proc. 25th Canadian Conference on Computational Geometry (CCCG 2013) , arXiv : 1306.3000 , Bibcode :2013arXiv1306.3000G.
Megiddo, Nimrod (1983), "Aplicación de algoritmos de computación paralela en el diseño de algoritmos seriales", Journal of the ACM , 30 (4): 852–865, doi : 10.1145/2157.322410 , MR 0819134, S2CID 2212007.
Reischuk, Rüdiger (1985), "Algoritmos probabilísticos paralelos para ordenamiento y selección", SIAM Journal on Computing , 14 (2): 396–409, doi :10.1137/0214030, MR 0784745.
van Oostrum, René; Veltkamp, Remco C. (2002), "La búsqueda paramétrica hecha práctica", Actas del Decimoctavo Simposio Anual sobre Geometría Computacional (SoCG '02) , Nueva York, NY, EE. UU.: ACM, págs. 1–9, doi : 10.1145/513400.513401, hdl : 1874/18869 , ISBN 1-58113-504-1, Número de identificación del sujeto 1551019.