Diskussion:Chans Algorithmus

Laufzeit

Stimmt es, dass die Gesamtlaufzeit dieselbe Größenordnung hat wie der erste Schritt? Ich finde das ziemlich unplausibel.--Pugo (Diskussion) 17:26, 16. Mär. 2016 (CET)

Laut englischem Artikel haben beide Schritte die gleiche Größenordnung, sollte also passen, auch wenn ich mich da nicht weiter auskenne. -- HilberTraum (d, m) 17:09, 20. Mär. 2016 (CET)

Letzter Absatz

Die folgende Formulierung verstehe ich nicht: "Im Best-Case ist m=h, wobei h die Anzahl der Punkte auf der konvexen Hülle entsprechen" --Pugo (Diskussion) 17:28, 16. Mär. 2016 (CET)

Ich habe das so verstanden: Wenn man m kleiner als h wählt, funktioniert der Algorithmus nicht. Wenn man m zu groß wählt, wird die Laufzeit schlechter. Die beste Wahl wäre also m=h, aber h kennt man ja normalerweise nicht. -- HilberTraum (d, m) 17:15, 20. Mär. 2016 (CET)

Neubearbeitung

Ich habe mich mal an einer Neubearbeitung versucht. Da (neben dem schlechten Zustand des Artikels und den sinnentstellenden Typos) auch die obigen beiden Diskussions-Beiträge eine maßgebliche Motivation dazu waren, möchte ich auch gern zu beiden noch eine Antwort geben:

• Laufzeit: Da es sich hier nur um zwei Schritte mit der gleichen Laufzeit $O(n\log m)$ handelt und man bei der Landau-Notation sowieso konstante Faktoren vernachlässigt, gilt in der Tat $O(n\log m)+O(n\log m)=O(n\log m)$. Ich nehme bei dir einfach Mal einen mathematischen (statt informatischen) Background an: Da lässt sich das am ehesten damit erläutern, dass es im Grenzwert egal ist, ob ich $x$ oder $2x$ betrachte (für $x\to \infty$) beide wachsen linear.

• Letzter Absatz: In der bisherigen Fassung blieb schlicht unerwähnt, dass das ganze Problem bei der Berechnung ist, dass man die Größenordnung von $h$ i.d.R. nicht vorher kennt. Das ist genau die Schwierigkeit, die Chans Algorithmus löst (bzw. umgeht). Um zu verstehen, warum das tatsächlich funktioniert, muss man allerdings sehr weit ausholen. Daher auch die ganze Vorrede in Abhängigkeit eines fest gewählten $m$. Nur wenn man den Algorithmus genau so aufzieht wie Chan/Nielsen das getan haben, kann man am Ende sagen "Wenn ich $m$ in jedem Schritt quadriere, erhalte ich genau die optimale Laufzeit." Zu keinem Zeitpunkt ist also die Größe der Hülle bekannt, aber man kann sich rantasten ohne (asymptotisch) Zeit zu verlieren.

Liebe Grüße -- 2A02:8109:A7BF:E964:613C:3E5E:3787:80A3 23:43, 5. Apr. 2016 (CEST)

Nach meinem Verständnis ist der von Chan vorgestellte Algorithmus nicht nur für Punktmengen in der Ebene geeignet, sondern auch im dreidimensionalen Raum. Er merkte an, daß dei Laufzeit keinen Vorteil gegenüber bereits bekannten Algorithmen darstelle, die sowohl im zwei- wie auch dreidimensionalen Raum existieren, allerdings findet sein Ansatz in beiden Fällen die Lösung in der bereits bekannten optimalen Zeit von O(n • log h) berechnet. Ich verweise auf den Text "Optimal Output-Sensitive Convex Hull Algorithms in Two and Three Dimensions" von eben Herrn Chan.