Dado que todos los puntos tienen el mismo radio de visión, puede garantizar que, si aún no se ve un borde de la línea, el movimiento más pequeño que puede hacer para cubrirlo es mover el punto extremo de ese lado lo suficiente como para hacerlo completamente visto Y dado que se necesita ver toda la línea, cuando no se ven sus bordes, debe cubrirlos.
Entonces, muevamos nuestros puntos más extremos a sus distancias mínimas para cubrir sus respectivos bordes. Ahora podemos cortar la línea en una sublínea que termina en los puntos más internos de los círculos de visión de los puntos que acabamos de mover, y podemos eliminar esos dos puntos de nuestra pila de “mover”. A partir de ahí, ¡solo dividimos y conquistamos! Use los siguientes dos puntos más externos para cubrir apenas los nuevos bordes y repita una y otra vez hasta que la línea esté cubierta.
Creo que este algoritmo moverá todo a la menor distancia posible (¡aunque agradezco un contraejemplo!). Como los puntos deben moverse en el orden más externo al más interno, la complejidad temporal del algoritmo es [matemática] O (n log n) [/ matemática], donde [matemática] n [/ matemática] es el número de puntos para mover.
- Cómo organizar y buscar un árbol de búsqueda binario donde cada nodo tiene más de un campo de datos
- ¿Cómo podrían analizarse las preguntas arbitrarias de Quora para adivinar si el cartel es suicida?
- ¿Qué algoritmo se usa para escanear?
- Cómo representar el algoritmo de hash SHA256 en python
- ¿Qué tan valioso sería ser ubicado para aprender la estructura de datos usando C?
Esta complejidad puede mejorarse (más o menos) con cierta información sobre nuestro parámetro adicional, [math] r [/ math]. Sabemos a priori que [math] \ lceil \ frac {1} {r} \ rceil [/ math] puntos serán necesarios para cubrir la línea; por lo tanto, solo necesitamos tomar tantos puntos extremos. Podemos usar Quickselect para tomar tantos puntos, haciendo nuestra complejidad de tiempo (promedio) alrededor de [matemáticas] O (\ frac {n} {r}) [/ matemáticas].
