Media de puntos en un círculo

Question

Dado $N$ puntos en un círculo, donde la distancia entre dos puntos es la distancia medida a lo largo del círculo, ¿cómo puedo encontrar el punto medio? Si dejamos que el círculo tiene unidad de circunferencia, definir la mediana $m$ como punto tal que hay un número igual de puntos hacia la derecha una distancia no mayor que $1/2$ frente a los puntos en contra de las manecillas una distancia no mayor que $1/2$.

EDITAR

Después de joriki y un anon señalado, este 'mediana' no es necesariamente un único punto. Entonces, ¿cómo podría uno encontrar alguna de estas mediana de los puntos? Presumiblemente se podría comprobar cada punto, pero yo estaría interesado en una manera más rápida.

Answer 1

Para "definir la mediana $m$ como punto tal que hay un número igual de puntos hacia la derecha una distancia no mayor que $1/2$ frente a los puntos en contra de las manecillas una distancia no mayor que $1/2$", usted primero tiene que demostrar que hay sólo un punto. Este no suele ser el caso. Esto no es sólo, como para el "normal" de la mediana, porque de los degenerados situaciones de las que sólo hay un conjunto de medida cero; puede haber varios de estos puntos, incluso si los puntos están en posición general. Para ver esto, imagina un número impar $n$ de los puntos equidistantes (es decir, que de forma regular $n$-gon) y, a continuación, mover cada punto por algunos arbitraria de la cantidad pequeña de menos de un cuarto de la distancia entre los puntos. A continuación, seguirá siendo el caso que cada uno de los puntos que tiene muchos puntos de las agujas del reloj como en sentido antihorario a una distancia no mayor que $1/2$.

[Editar en respuesta a la edición en la pregunta:]

Usted no tiene que comprobar cada punto por separado (lo que sería un doble bucle); un solo bucle es suficiente. Cíclicamente ordenar los puntos de acuerdo a sus ángulos (teniendo en $O(N\log N)$ tiempo), punto de partida, y se mueven a lo largo del círculo de las agujas del reloj con un segundo punto, hasta llegar a un punto en sentido antihorario desde el primer punto. Hasta encontrar un punto medio, mover el primer y segundo punto en bloque, en la hilera avanzar en el segundo punto, hasta que en sentido antihorario a partir de la primera y el avance de la primera hasta la segunda está a la derecha de nuevo. Desde las dos mitades del círculo de cambiar de lado durante el proceso, debe haber algún punto del camino donde contienen el mismo número de puntos, y que es la "mediana" que estás buscando.

Answer 2

Pensé que esta cuestión había un interesante sabor a él a pesar de la no-unicidad discutido en joriki del post. Así que no te preocupes por eso, y en su lugar voy a considerar la tarea de encontrar un 'mediana'. Creo que este método numérico-como en el enfoque funciona bien.

He métodos diferentes para los números pares y los impares de puntos en el círculo. Impar es más fácil. Creo que podemos estar de acuerdo que para un número impar de puntos, una mediana debe o bien se encuentran en un punto o mentira diametralmente opuesto a un punto (en caso contrario, un número impar de puntos nunca puede ser cortado en dos porciones de la misma paridad). También podemos ver que estos dos casos son equivalentes, y que lo que realmente estamos buscando es el de una mediana de cuerda, es decir, un diámetro del círculo que pone la mitad de los puntos en un lado y la otra en el otro. Tan sólo la comprobación de todos los puntos, y usted encontrará una mediana.

Ahora supongamos que tenemos un número par de puntos en el círculo. Este es el más entretenido parte. Para examinar esta parte, me gustaría describir un proceso y se basan en una especie de discreta intermedio valor de la propiedad.

Supongamos que reformular el problema como el dibujo de un diámetro, como he mencionado anteriormente, y contando el número de puntos en cada lado. Además, asociado a un lado de el diámetro con valores positivos y otros negativos, y llame a la Suma de la suma de estos dos (uno positivo, uno negativo) de los números. Buscamos cuando la Suma es cero. A continuación, el proceso de rotación, el diámetro de la siguiente manera una especie de discreta intermedio valor de la propiedad, donde la Suma del cambio en el valor absoluto de 0, 1, o 2 solamente. 1 sólo puede ocurrir cuando el diámetro se encuentra en un punto.

Ahora, para el proceso en sí. Calcular la Suma del diámetro en cada uno de los puntos. Si cualquiera de estos resultados en una Suma de cero, entonces hemos terminado (el uso que de diámetro). Si no, entonces existe un punto de Suma positiva adyacente a un punto de Suma negativa. A continuación, un diámetro que pasa por el espacio entre estos dos puntos. Afortunadamente, sólo un número finito de puntos que necesitan ser revisados sólo donde el diámetro de la cruza de un punto (en este caso, en el lado opuesto, y en realidad debería simplemente mirar sus Sumas en su lugar, pero que así sea).

Por último, quiero señalar que no siempre existe una mediana. Y yo quería señalar que mientras escribía esto, yo no terminan usando el IVP casi tanto como pensé que lo haría.

Answer 3

Esta página tiene un algoritmo útil para encontrar el ángulo medio en un círculo:

http://en.wikipedia.org/wiki/Mean_of_circular_quantities

Una vez que encuentre el ángulo promedio, recorrer el conjunto de puntos y calcular el ángulo a cada uno en relación con el centro del círculo. Reste el ángulo promedio de cada uno, de y con el menor valor absoluto - que es su punto mediano.