Minimizar y maximizar la longitud de una cadena poligonal con ciertas condiciones de contorno

Question

Dejar $P_0,\ldots, P_k\in \mathbb{R}^2$ sea un conjunto de puntos. Además, dejemos que $\epsilon\in \mathbb{R}$ .

Ahora estoy tratando de encontrar límites inferiores y superiores no triviales para

$$ \sum_{i=1}^k ||Q_i-Q_{i-1}||^2\quad \text{w.r.t.}\quad ||P_i-Q_i||\leq \epsilon\quad\text{for all} \quad i=0,\ldots,k $$

---

Sé que existe el límite trivial $$ \sum_{i=1}^k \left(||P_i-P_{i-1}||-2\epsilon\right)^2\leq\sum_{i=1}^k ||Q_i-Q_{i-1}||^2\leq \sum_{i=1}^k \left(||P_i-P_{i-1}||+2\epsilon\right)^2 $$ (utilizando la desigualdad del triángulo).

Sin embargo, para la mayoría de las combinaciones de $P_i$ Estos límites son bastante débiles. ¿Conoce usted un método mejor para obtener un límite estricto en esa suma? Por supuesto, siempre podría utilizar alguna optimización numérica, pero entonces tendría que molestarse en poner entre paréntesis el mínimo y el máximo, lo que me gustaría evitar. Preferiría una solución geométrica o analítica limpia.

Gracias por sus opiniones.

P.D.: Estoy teniendo bastantes problemas para etiquetar esta pregunta en el campo correcto, ya que parece muy elemental. Si lo desea, puede poner mejores etiquetas que las que he puesto yo...

---

Edición 1

Dos pensamientos:

• Puede demostrar que es $P_i=Q_i$ o $||P_i-Q_i||=\epsilon$ al minimizar o maximizar la suma de cuadrados
• Se puede escribir el problema como un programa cuadrático con restricciones cuadráticas. Sin embargo, esto parece muy complicado para un problema tan pequeño...

Answer 1

Lo primero que podrías hacer es atar pares de las aristas adyacentes, en lugar de sólo las aristas una por una.

Es decir, que $d_i = \lVert Q_{i-1} - Q_i\rVert^2 + \lVert Q_i - Q_{i+1}\rVert^2$ para que su función objetivo sea precisamente $\frac{1}{2}\big( \lVert Q_0 - Q_1\rVert^2 + \sum_{i=1}^{k-1} d_i + \lVert Q_{k-1} - Q_k\rVert^2 \big)$ . Debería ser posible encontrar buenos límites en $d_i$ en cuanto a las posiciones $P_{i-1}$ , $P_i$ y $P_{i+1}$ . Volveré a rellenar esto cuando tenga tiempo.

Por cierto, no es cierto que tampoco $P_i = Q_i$ o $\lVert P_i - Q_i\rVert = \epsilon$ . Para $k = 2$ , dejemos que $P_0 = (-1, 0)$ , $P_2 = (1,0)$ y elija cualquier $P_1$ a una distancia entre $0$ y $\epsilon$ desde el origen. T $Q_0 = (-1+\epsilon,0)$ , $Q_1 = (0,0)$ , $Q_2 = (1-\epsilon,0)$ . Por otro lado, para el máximo, creo que es cierto que $\lVert P_i - Q_i\rVert = \epsilon$ porque estás minimizando una función que es convexa con respecto a cualquier $Q_i$ .