kon krétně jestli má každý bod ode všech ostatních vzdálenost aspoň 1. Jak postupovat, aby
pro g ram zvládl i velký počet bodů (řekněme milióny) v rozumném čase? Pozor, kontrolo vat
každou dvojici bodů zvlášť by bylo beznadějně pomalé!
A co KAM? V oboru diskrétní a výpočetní geometrie se na Katedře aplikované matematiky
věnujeme především základnímu výzkumu. Popíšeme teď konkrétně jedno z četných témat
studovaných našimi pracovníky a studenty.
Nová křivka
Hiroshi Murata, japonský inženýr zabývající se výrobou integrovaných obvodů, přišel
s následující geometrickou otázkou. Máme dva body P a Q v rovině a chceme mezi nimi
vést k křivek C 1 ,C 2 ,…,C k tak, aby měly „stejné odstupy“. Tím se myslí to, že každý bod X
křivky C 1 je stejně daleko od P jako od C 2 , každý bod křivky C 2 je stejně daleko od C 1 jako
od C 3 atd. Případ k = 1 je lehký, řešením je přímka na obrázku 3 vlevo.
Pro k = 3 úlohu také řeší dobře známé