Перейти к содержанию

Файл:Welzl's algorithm counterexample.png

Содержимое страницы недоступно на других языках.
Материал из Wikivoyage

Исходный файл(974 × 814 пкс, размер файла: 21 КБ, MIME-тип: image/png)

Этот файл из на Викискладе и может использоваться в других проектах. Информация с его страницы описания приведена ниже.

Краткое описание

Описание
English: When selecting points in mentioned order points A, B, C, D are going to be fixed by the algorithm, but at most 3 should be fixed. Patch would be to guarantee the radius of the maintained circle never decreases. Matousek, Sharir, Welzl correcteed it in following paper. Sufficient correction is to exclude the last 4 points from the random selection unless there are no other points remaining. Fixed point replaces the point remaining fourth. Then radius for last 4 points never decreases and algorithm works well. Oops the original algorithm ends recurrence immediately when there are 3 fixed points, even when the subresult does not enclose entire subset. In that case there is point on the stack (when less then 3 points are fixed) which is outside the subresulting disc. So this point would be fixed and algorithm recovers. What are consequences to the algorithm's time complexity?
Čeština: Pokud vybíráme body v zmíněném pořadí, body A, B, C, D budou upevněny, ale nejvýš 3 smějí být upevněny. Záplatou by bylo garantovat že poloměr udržované kružnice se nezmenší. Matoušek, Sharir, Welzl opravili chybu v následujícím článku. Dostatečnou záplatou je vyloučit poslední 4 body z náhodného výběru, s výjimkou toho, kdy se jedná o poslední body. Upevněný bod nahrazuje čtvrtý zůstávající. Pak poloměr pro poslední 4 body neklesá a algoritmus pracuje dobře. Oops, původní algoritmus končí rekurenci když jsou 3 body upevněny i v případě, kdy mezivýsledek neobsahuje celou podmnožinu. V takovém případě je ale na zásobníku bod (když méně než 3 body jsou upevněny), který leží mimo kruh mezivýsledku. Proto bude tento bod upevněn a algoritmus se vzpamatuje. Jaké to má důsledky na časovou náročnost algoritmu?
Дата
Источник Собственная работа
Автор Hippo.69

Лицензирование

Я, владелец авторских прав на это произведение, добровольно публикую его на условиях следующей лицензии:
w:ru:Creative Commons
атрибуция распространение на тех же условиях
Этот файл доступен по лицензии Creative Commons Attribution-Share Alike 4.0 International
Вы можете свободно:
  • делиться произведением – копировать, распространять и передавать данное произведение
  • создавать производные – переделывать данное произведение
При соблюдении следующих условий:
  • атрибуция – Вы должны указать авторство, предоставить ссылку на лицензию и указать, внёс ли автор какие-либо изменения. Это можно сделать любым разумным способом, но не создавая впечатление, что лицензиат поддерживает вас или использование вами данного произведения.
  • распространение на тех же условиях – Если вы изменяете, преобразуете или создаёте иное произведение на основе данного, то обязаны использовать лицензию исходного произведения или лицензию, совместимую с исходной.

Краткие подписи

Добавьте однострочное описание того, что собой представляет этот файл
Counterexample for Welzl's minium enclosing circle algorithm

Элементы, изображённые на этом файле

изображённый объект

У этого свойства есть некоторое значение без элемента в

История файла

Нажмите на дату/время, чтобы увидеть версию файла от того времени.

Дата/времяМиниатюраРазмерыУчастникПримечание
текущий17:11, 26 февраля 2019Миниатюра для версии от 17:11, 26 февраля 2019974 × 814 (21 КБ)Hippo.69User created page with UploadWizard

Нет страниц, использующих этот файл.

Глобальное использование файла

Данный файл используется в следующих вики:

Метаданные