Cómo encontrar el punto máximo en un polígono convexo usando la búsqueda ternaria

Answer 1

Describo el algoritmo de búsqueda binaria dado en Puntos extremos de polígonos convexos. Nuestro objetivo es encontrar el punto [matemática] V ^ * [/ matemática] entre [matemática] V_1,…, V_n [/ matemática] que tiene la mayor proyección en alguna dirección [matemática] \ vec {u} [/ matemática] (por ejemplo, si buscamos el punto con la coordenada y máxima, consideramos [math] \ vec {u} = (0,1) [/ math])

Suponga que sabe que el máximo [matemático] V ^ * [/ matemático] se encuentra dentro de algún intervalo [matemático] V_a,…, V_b [/ matemático]. Consideramos [math] V_c [/ math], que está en el medio. Podemos probar si [math] V_c [/ math] es el máximo comparando su proyección en [math] \ vec {u} [/ math] con la de sus vecinos. Si es así, sacamos [math] V_c [/ math]. Si no, consideramos los dos vectores [matemática] A = V_ {a + 1} – V_a [/ matemática] y [matemática] C = V_ {c + 1} – V_c [/ matemática]. Dependiendo de las direcciones de las proyecciones de [matemáticas] A [/ matemáticas] y [matemáticas] C [/ matemáticas] en [matemáticas] \ vec {u} [/ matemáticas], podemos deducir que [matemáticas] V ^ * [/ matemática] debe estar en [matemática] V_a, .., V_c [/ matemática] o [matemática] V_ {c + 1},…, V_b [/ matemática], lo que reduce el espacio de búsqueda a la mitad. El análisis de casos basado en [matemáticas] A [/ matemáticas] y [matemáticas] B [/ matemáticas] se muestra a continuación:
(fuente: primer enlace)

Repetimos hasta encontrar [math] V_c [/ math] que es el máximo de sus vecinos.
Según el análisis estándar, esto ha esperado tiempo de ejecución [math] O (\ log n) [/ math].