From 5c2272caaf80702bc3c0b829e27aa79855660c12 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sun, 20 Jan 2008 21:35:59 +0100 Subject: [PATCH] Dalsi drobne korektury 9. kapitoly. --- 9-geom/9-geom.tex | 14 ++++++++------ 1 file changed, 8 insertions(+), 6 deletions(-) diff --git a/9-geom/9-geom.tex b/9-geom/9-geom.tex index 5615ac0..8de859d 100644 --- a/9-geom/9-geom.tex +++ b/9-geom/9-geom.tex @@ -151,15 +151,17 @@ o n jak se pobøe¾í zmìnilo a co se vykreslilo. Dùle¾itým místùm, kde se budeme zastavovat, budeme øíkat {\I události}. -Místní událost +\>{\I Místní událost} Pokud narazíme na bod, musíme najít místo, kde pobøe¾í rozetnou a kam vklínit dal¹í výbì¾ek (parabolu). Takovéto události budeme øíkat místní událost. Pokud se pohybujeme v obecné poloze, nestane se nám, ¾e bychom narazili na prùseèík. -\figure{mistni.eps}{Místní událost - èervená kolmice je novì vznikající parabola, -pøi postupu zametací pøímky dále se bude rozevírat a vytvoøí dal¹í parabolu.}{3in} +\figure{mistni.eps}{\vbox{ +\hsize=0.6\hsize\leftskip=0pt plus 0.3\hsize\rightskip=\leftskip\parfillskip=0pt +\>Místní událost -- èervená kolmice je novì vznikající parabola, +pøi postupu zametací pøímky dále se bude rozevírat a vytvoøí dal¹í parabolu.}}{3in} -Kru¾nicová událost +\>{\I Kru¾nicová událost} Poslední situace, která mù¾e nastat, je, ¾e se nìjaká parabola schová za jiné. Kouknìme se na první obrázek ní¾e, fialový bod le¾í na v¹ech tøech parabolách. @@ -179,9 +181,9 @@ situaci p Budeme potøebovat haldu událostí (místních i kru¾nicových dohromady), ta nám zabere $\O(\log n)$ pamìti. -Dále bude zapotøebí udr¾ovat si pobøe¾ní linii, nebo-li posloupnost míst +Dále bude zapotøebí udr¾ovat si pobøe¾ní linii, neboli posloupnost míst v~ohniscích parabolických obloukù. Zde je potøeba si definovat operace -{\I Insert,Delete} a {\I FindX.} Navíc budeme potøebovat vyhledávací strom nad +{\I Insert, Delete} a {\I FindX.} Navíc budeme potøebovat vyhledávací strom nad prùseèíky s implicitní reprezentací. Zdá se, ¾e je toho hodnì, ale v¹echno to zvládneme s pamìtí $\O(\log n).$ -- 2.39.2