Matematické Fórum

↑ sio:
Ahoj, chceš najít algoritmus na nalezení toho poloměru a nebo vzorec?
Algoritmus je např. brual force: Zkusit všechny trojice bodů, opsat jim kružnici, a zjistit, zda takové obsahují alespoň M bodů - a ze všech takových vybrat tu s nejmenším poloměrem. (Lze to nějakými heuristikami vylepšit - např. je-li daná kružnice příliš malá, tak nemá cenu zkoumat trojice z boů v ní obsažených, apod.)

Hlouběji jsem nad tím nepřemýšlel, ale nejspíš bude dost zajímavý i případ M=N=3.

Skutočne, v prípade ktorý som uviedol to je priamočiare riešenie. Žiaľ, číslo N môže byť až 500 bodov a pre M platí M<=N (je to programátorská úloha). Presne tento algoritmus mi napadol, skúsiť všetky možnosti. Okrem toho, že by bol brutálne časovo zložitý, je asi nie korektný. Okrem prípadov, kedy by ležala trojica bodov na priamke (to sa dá ošetriť), by mohla nastať situácia, kedy by jednoducho na kružnici neležali všetky 3 body - domnievam sa, že minimálne jeden tam ležať musí. Nie je možné urobiť nejakú kružnicu v ktorej KRUHU (nemusia na kružnici) sa nachádzajú vrcholy mnohouholníka? Urobil by som konvexný obal a mal by som vrcholy.

ahoj ↑ sio:,

poloměr nejmenšího kruhu, ve kterém leží tři body je

a) polovina vzdálenosti dvou nejvzdálenějších v případě tupoúhlého nebo pravoúhlého trojúhelníka
b) poloměr opsané kružnice v případě ostroúhlého.

Takže algoritmus bych viděl takto:

1) Nastav hledaný průměr na "téměř nekonečno".
2) Procházej všechny možné dvojice bodů
3) Nad průměrem 2) opiš kružnici
4) Je-li v kruhu 3) právě N bodů, přepiš hledaný průměr průměrem aktuálním
5) Je-li po průchodu všech dvojic hledaný průměr menší než téměř nekonečno, úloha končí.
6) Pokud úloha neskončila, procházej všechny možné trojice
7) Trojúhelníku 6) opiš kružnici
8) Je-li v kruhu 7) právě N bodů, přepiš hledaný průměr.

↑ Honzc:

Ano, ale to ten problém přece řeší - nejmenší kruh, který obsahuje daných N bodů je přeci tentýž, který obsahuje z té N-tice "největší" trojúhelník - stačí tedy kruh obsahující vždy dva (event. tři) body, a pak se podívat, kolik dalších je uvnitř...

PS: Pozor - on nemá najít konvexní obal, on má najít kruh. A to je dost rozdíl...

↑ Eratosthenes:
Máš pravdu-svůj příspěvek jsem zeditoval.

↑ Honzc:

V tom případě má ovšem stejnou "malou vadu" samotné zadání - taková úloha totiž řešení nemá.

Veľmi sa ospravedlňujem, musí mať minimálne M bodov.

Riešenie prve všetkých dvojíc a potom trojíc je síce korektné, ale má závadu a tou je štvorrozmerná asymptotická zložitosť. Ako by som teda urobil kruh v ktorom je konvexný obal?

↑ sio:

>> Riešenie prve všetkých dvojíc a potom trojíc je síce korektné, ale má závadu a tou je štvorrozmerná asymptotická zložitosť.

To není závada. O složitosti algoritmu není v zadání řeč a nic jednoduššího mě nenapadá. Je to lepší, než kdyby byl algoritmus jednodušší a nefungoval by.

>> Ako by som teda urobil kruh v ktorom je konvexný obal?

Přesně tak, jak jsem popsal. Testoval bych nejdřív dvojice a potom trojice, kde sestrojený kruh obsahuje všechny požadované body. Našel bych toto:

↑ sio:

>> Podľa wikipedie sa dá riešiť lineárne

No tak to řeš lineárně - co to brání? Já jsem to neštudoval, ale když se tam podíváš na ty obrátky, tak jsou úplně stejný, jako maluju já...

Zdravím,
tady jsem něco zkusil ve wxMaximě: Odkaz
Je to pro 100 náhodných bodů, výpočet je bleskový. Potíž je v tom, že generovaní seznamu vzdáleností trvá asi minutu, což je dáno asi programovacím jazykem (lisp) ve kterém je wxMaxima vytvořena.
Takže asi jen na ukázku.