From 914180b39544f2133b224077ab4a873e8e32bfab Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Thu, 24 Jan 2013 22:58:34 +0100 Subject: [PATCH] Voroneho diagramy: Oprava preklepu --- 6-geom/6-geom.tex | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/6-geom/6-geom.tex b/6-geom/6-geom.tex index 5daabf9..bafab25 100644 --- a/6-geom/6-geom.tex +++ b/6-geom/6-geom.tex @@ -324,8 +324,8 @@ na du ve~Voroného diagramu a takové neexistují, nebo» ka¾dá stìna je ohranièena rovnými èarami. -Voroneho diagram pro $n$~zadaných bodù je tedy velký $\O(n)$. Dodejme, ¾e ho lze -zkonstruovat zkonstruovat v èase $\O(n \log n)$, napøíklad pomocí zametání roviny nebo metodou +Voroného diagram pro $n$~zadaných bodù je tedy velký $\O(n)$. Dodejme, ¾e ho lze +zkonstruovat v èase $\O(n \log n)$, napøíklad pomocí zametání roviny nebo metodou Rozdìl a panuj. Tím se v¹ak zabývat nebudeme,\foot{Pro zvídavé, kteøí nemají zkou¹ku druhý den ráno: Detaily naleznete v~zápiscích z~ADS z~roku 2007/2008.} místo toho si uká¾eme, jak v ji¾ spoèteném Voroného diagramu rychle hledat nejbli¾¹í body. -- 2.39.2