Algoritmusok
Feladatunk lecsupaszítva a következő: adott pontok véges halmaza a síkon. Keressük, hogy legfeljebb hány fedhető közülük egy adott sugarú körrel.
Első észrevétel
Ha a pontok túl messze vannak egymástól (messzebb, mint a kör átmérője), akkor legfeljebb
egy pont fedhető.
Második észrevétel
Ha vannak pontok az átmérőnél közelebb, akkor van olyan optimális (maximális számú pontot fedő) kör, ami legalább két adott pontot határán tartalmaz.
Harmadik észrevétel
Az előző megjegyzés alapján a következő polinomiális algoritmus adódik: az elég közel lévő pontpárok mindegyikére illesztünk két-két adott sugarú kört (az egyenes mindkét oldalára lehet), és megnézzük, hány pontot fed a kör. Pontpárok: $n^2$, ellenőrzés: $n$, vagyis egy $n^3$-ös algoritmushoz jutottunk.
Matematikus módszer a körök ellenőrzésére
Egy adott húr és a sugár lehetővé teszi a kör egyenletének kiszámítását. Az egyenlet ismeretében eldönthető minden pontról, fedi-e a kör.
Informatikus módszer a körök ellenőrzésére
Ha el akarjuk kerülni a lebegőpontos aritmetikát, dolgozhatunk a kerületi szögek tétele alapján. Elég a szögek koszinuszát összehasonlítani, ami az egész koordinátákból egy racionális kifejezéssel pontosan megadható.
Ha $P$ az $AB$ ugyanazon oldalán van, mint $C$, akkor pontosan abban az esetben esik az $ABC$ köréírt körébe, ha
$APB\angle \ge ACB \angle$.
Kódok
