Zum Inhalt springen

Datei:Welzl's algorithm counterexample.png

Seiteninhalte werden in anderen Sprachen nicht unterstützt.
Zur Beschreibungsseite auf Commons
aus Wikipedia, der freien Enzyklopädie

Originaldatei (974 × 814 Pixel, Dateigröße: 21 KB, MIME-Typ: image/png)

Diese Datei und die Informationen unter dem roten Trennstrich werden aus dem zentralen Medienarchiv Wikimedia Commons eingebunden.

Zur Beschreibungsseite auf Commons


Beschreibung

Beschreibung
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?
Datum
Quelle Eigenes Werk
Urheber Hippo.69

Lizenz

Ich, der Urheber dieses Werkes, veröffentliche es unter der folgenden Lizenz:
w:de:Creative Commons
Namensnennung Weitergabe unter gleichen Bedingungen
Dieses Werk darf von dir
  • verbreitet werden – vervielfältigt, verbreitet und öffentlich zugänglich gemacht werden
  • neu zusammengestellt werden – abgewandelt und bearbeitet werden
Zu den folgenden Bedingungen:
  • Namensnennung – Du musst angemessene Urheber- und Rechteangaben machen, einen Link zur Lizenz beifügen und angeben, ob Änderungen vorgenommen wurden. Diese Angaben dürfen in jeder angemessenen Art und Weise gemacht werden, allerdings nicht so, dass der Eindruck entsteht, der Lizenzgeber unterstütze gerade dich oder deine Nutzung besonders.
  • Weitergabe unter gleichen Bedingungen – Wenn du das Material wiedermischst, transformierst oder darauf aufbaust, musst du deine Beiträge unter der gleichen oder einer kompatiblen Lizenz wie das Original verbreiten.

Kurzbeschreibungen

Ergänze eine einzeilige Erklärung, was diese Datei darstellt.
Counterexample for Welzl's minium enclosing circle algorithm

In dieser Datei abgebildete Objekte

Motiv

Dateiversionen

Klicke auf einen Zeitpunkt, um diese Version zu laden.

Version vomVorschaubildMaßeBenutzerKommentar
aktuell16:11, 26. Feb. 2019Vorschaubild der Version vom 16:11, 26. Feb. 2019974 × 814 (21 KB)Hippo.69User created page with UploadWizard

Keine Seiten verwenden diese Datei.

Globale Dateiverwendung

Die nachfolgenden anderen Wikis verwenden diese Datei:

Metadaten