Tengo un conjunto 2D y me gustaría determinar a partir de ellos el subconjunto de puntos que, si se unen con líneas, daría lugar a una arista por debajo de la cual no existe ninguno de los puntos del conjunto.
Este problema se asemeja al problema del casco convexo, pero es fundamentalmente diferente en su definición.
Un enfoque para determinar estos puntos podría ser evaluar el producto cruzado de sólo x_1 , x_2 y x_3 , donde x_1 está en el "casco", x_2 se está evaluando el 'casco' y x_3 es otro punto del conjunto (todos los demás puntos del conjunto deberían dar productos cruzados positivos si x_2 está efectivamente en el casco), con la restricción adicional de que x_1 < x_2 en una dimensión.
Me doy cuenta de que este algoritmo no es del todo perfecto; el gráfico de abajo muestra que algunos puntos válidos se perderían como resultado de la restricción del casco convexo. ¿De qué otra manera puedo definir esta arista?
Espero que la pregunta esté clara.
0 votos
¿Quiere un borde o un conjunto de bordes?
0 votos
Creo que no ha expuesto claramente su problema. Así que está dado un conjunto finito $A$ de puntos en el plano. Se quiere un subconjunto que esté de alguna manera en el fondo (con respecto a $y$ ). Dicho subconjunto estará formado por $>2$ puntos, así que ¿cómo puede definir "una línea"? Tal vez esta "línea" sea en realidad un arco poligonal - ¿por qué todo esto debería ser "fundamentalmente diferente" de la búsqueda del casco convexo de $A$ ?
4 votos
Esto se llama "casco convexo inferior" (haz una búsqueda en Google). Muchos algoritmos de cascos convexos lo calculan por separado y el casco convexo superior para crear el casco convexo.
0 votos
@Cristian : Estoy buscando un arco poligonal aquí.