Algoritmo Ótimo para o Problema dos Dois Centros Planar

Estudamos um problema fundamental em Geometria Computacional, o problema dos dois centros planares. Neste problema, a entrada é um conjunto S de n pontos no plano e o objetivo é encontrar dois menores discos congruentes cuja união contenha todos os pontos de S. Um problema em aberto há muito tempo tem sido obter um algoritmo de tempo O (n n) para o problema dos dois centros planares, correspondendo ao limite inferior (n n) dado por Eppstein SODA'97. Nesse sentido, pesquisadores têm se esforçado bastante ao longo de décadas. O melhor algoritmo anterior, dado por Wang SoCG'20, resolve o problema em O (n² n) tempo. Neste artigo, apresentamos um algoritmo determinístico de tempo O (n n) para o problema dos dois centros planares, que resolve completamente este problema em aberto.