File:Welzl's algorithm counterexample.png
Size of this preview: 717 × 599 pixels. Other resolutions: 287 × 240 pixels | 574 × 480 pixels | 974 × 814 pixels.
Original file (974 × 814 pixels, file size: 21 KB, MIME type: image/png)
 | This is a file from the Wikimedia Commons. Information from its description page there is shown below. Commons is a freely licensed media file repository. You can help. |
Summary
| Description |
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? |
| Date | |
| Source | Own work |
| Author | Hippo.69 |
Licensing
I, the copyright holder of this work, hereby publish it under the following license:
This file is licensed under the Creative Commons Attribution-Share Alike 4.0 International license.
- You are free:
- to share – to copy, distribute and transmit the work
- to remix – to adapt the work
- Under the following conditions:
- attribution – You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- share alike – If you remix, transform, or build upon the material, you must distribute your contributions under the same or compatible license as the original.
File history
Click on a date/time to view the file as it appeared at that time.
| Date/Time | Thumbnail | Dimensions | User | Comment | |
|---|---|---|---|---|---|
| current | 14:11, 26 February 2019 | | 974 × 814 (21 KB) | Hippo.69 | User created page with UploadWizard |
File usage
The following page uses this file:
