Cómo calcular eficientemente el área cubierta por N círculos que se cruzan con el mismo radio en la superficie de una esfera

Answer 1

Puede calcular la respuesta exactamente (excepto el error de coma flotante) en tiempo [matemático] O (N \ log N) [/ matemático]. Aquí hay una breve descripción.

1. Calcule el diagrama de Voronoi de los centros de los círculos en la esfera. Esto se puede hacer en [matemáticas] O (N \ log N) [/ matemáticas]. Aunque puede haber algunos algoritmos específicos para el diagrama de Voronoi en la esfera (vea los diagramas de Voronoi en la esfera), una forma simple de hacerlo es calcular el casco convexo de esos puntos en el espacio 3D, que corresponde a la triangulación de Delaunay de esos puntos en la esfera, y luego tome la gráfica dual [1].
2. Tenga en cuenta que para cada punto [matemática] P [/ matemática] en una región de Voronoi correspondiente al centro [matemática] O [/ matemática], ya que [matemática] P [/ matemática] está más cerca de [matemática] O [/ matemática] que a cualquier otro centro, puede verificar dónde [matemática] P [/ matemática] se encuentra en la unión de los círculos simplemente verificando si [matemática] P [/ matemática] se encuentra en el círculo con el centro [matemática] O [/ matemática ] Por lo tanto, el área en una región de Voronoi cubierta por la unión de círculos es solo el área de la intersección entre la región y el círculo con el centro [matemáticas] O [/ matemáticas]. Dividir la región en triángulos con [matemáticas] O [/ matemáticas] como vértice puede ayudar.
3. Repita para cada región de Voronoi y sume para obtener la respuesta.

Un problema más desafiante sería el caso en que los círculos no tienen el mismo radio, que no puedo pensar en una solución elegante (puede intentar hacer algo como calcular todos los puntos de intersección y construir un gráfico con ellos).

[1] Kevin Q. Brown, “Transformaciones geométricas para algoritmos geométricos rápidos”, p.75
http: //reports-archive.adm.cs.cm…