• Diskrétní
a výpočetní
geometrie
Katedra aplikované
matemati ky
http://kam.mff.cuni.cz/
Podrobnější informace o katedře viz
str. 76 o kombinatorice a teorii grafů.
1
2
Geometrie je jednou z nejstarších věd
a moh lo by se zdát, že o jednoduchých
geometrických objektech jako body,
přímky, elipsy či kvádry bylo už všechno
objeveno. Ale diskrétní geometrie i vý-
početní geometrie, discip líny mnohem
mladší, si o týchž objektech kladou nové
otázky a zasahují i do vývoje nejmo-
dernějších technologií.
Začneme příkladem poměrně snadné otázky,
která spadá do diskrétní geometrie. Je st-
liže rozstříháme obdélník podél n-pří mek,
kolik můžeme maximálně dostat ústřižků?
(obr. 1)
Obrázek dosvědčuje, že pro n = 5 lze
zís kat aspoň 16 kousků. Tuto úlohu často
ře ší studenti v prvním ročníku MFF, mnozí
s úspěchem (zpravidla dostanou nápo -
vědu – o kolik může vzrůst počet ústřižků
při dáním další přímky?). Můžete to zkusit
taky.
Jakými problémy se zabývá výpočetní
geo metrie? Zde je malá ukázka: Vstupem
po čítačového programu je n bodů v ro-
vi ně jako na obrázku 2 a program má zkon-
trolovat, zda mají dostatečné odstupy –
3
80
Informati ka: Diskrétní a výpočetní geometrie