¿Cómo probar que la línea fuera de un polígono convexo, que tiene la suma mínima de distancias, es una de las aristas?

Como parte de una pregunta de geometría computacional, necesito un resultado para un paso intermedio.

Supongamos que hay un polígono convexo S, con un número finito de puntos dentro del polígono. Ahora, queremos encontrar la línea fuera del polígono (es decir, la línea puede pasar por un vértice o una arista pero no puede intersecarse) lo que minimiza la suma de las distancias perpendiculares entre la línea y (vértices + puntos interiores).

Tengo el presentimiento de que podemos probar que esta línea debe ser uno de los bordes, pero no puedo encontrar una prueba.

El enfoque más simple que probé fue verificar si rotar una línea que pasa por el vértice (pero fuera del polígono) siempre disminuye la suma hasta que llega al borde. Pero esto claramente no es cierto.

¿Cómo probar esto?

Nota 1: Creo que este teorema debe ser cierto, pero no lo he visto por ninguna parte. Es posible que en realidad sea falso y que la pregunta original se pueda resolver con un método diferente. Si es así, me gustaría ver un contraejemplo.

Nota 2: La pregunta original , la única respuesta propone el teorema pero no proporciona una demostración.

"... rotar una línea que pasa por el vértice (pero fuera del polígono) siempre disminuye la suma hasta que llega al borde. Pero esto claramente no es cierto". ¿Para qué arreglos puntuales esto no es cierto?
Para casi todos los arreglos. Como si giras la línea, has dividido el plano en regiones basadas en las bisectrices perpendiculares. Los puntos que se encuentran en algunas regiones pueden aumentar su suma.
Según mi análisis no puede suceder. La suma máxima de distancias se logra si la línea que pasa por un vértice se dibuja perpendicular a la dirección que apunta al centroide. Cualquier rotación desde esta posición disminuirá la suma de las distancias.
Lo que dijiste es correcto, pero no implica que deba seguir disminuyendo continuamente hasta llegar al borde. En otras palabras, la función puede no ser monótona. Tal vez solo estoy arruinando algo, pero no es obvio para mí.
Comprueba tu cálculo. Hasta que la línea interseca al polígono, la suma de la distancia es proporcional al seno del ángulo entre la línea y la dirección al baricentro, y el seno es una función monótona en [ 0 , π / 2 ] .

Respuestas (1)

Una distancia desde un punto ( X i , y i ) a una recta dada por la ecuación a X + b y + C = 0 es

(1) | a X i + b y i + C | a 2 + b 2 .

Ahora, debido a que la línea está fuera del polígono del casco, la expresión a X i + b y i + C tiene el mismo signo para todos los puntos, que sin pérdida de generalidad asumiremos como positivo. Por lo tanto, podemos dejar de tomar el valor absoluto y escribir para la suma de las distancias:

(2) D ( a , b , C ) = ∑ i = 1 norte a X i + b y i + C a 2 + b 2 = norte a X + b Y + C a 2 + b 2 ,
dónde ( X , Y ) son las coordenadas del centroide de los puntos.

Ahora observa que el lado derecho en (2) no es más que el multiplicado por norte distancia desde el centroide hasta la línea que, de hecho, está minimizada por uno de los bordes del polígono, como se afirma.

¿Cómo probar que la línea fuera de un polígono convexo, que tiene la suma mínima de distancias, es una de las aristas?
RespuestasAquíPolítica de privacidad1y, 0v