Diskussion:Kreispackung

Neu erstellt

Ich starte einfach Mal mit diesem meiner Meinung nach wichtigem Artikel. Das Thema ist in der englischen Wikipedia sehr ausführlich über mehrere Artikel verteilt. In der deutschen noch kaum vorhanden. Relevanz sollte durch die Literatur belegt sein. Freue mich über jede Art der Hilfe oder Kritik. Geschichte könnte noch ergänzt werden. Pizzaschneider (Diskussion) 16:10, 31. Mär. 2018 (CEST)

P vs. NP

Die Komplexitätsklassen $P$ und $NP$ sind zunächst einmal nur für Entscheidungsprobleme definiert. Da stellt sich die Frage, welches Entscheidungsproblem für Kreispackungen $NP$-schwer sein soll. Die Existenz offenbar nicht, denn Planarität ist in $P$. Bitte präzisieren! Liebe Grüße -- 2A02:8109:9440:9174:125:2BC6:1E98:301E 15:43, 1. Apr. 2018 (CEST)

Update: Ich hab das mal nachgelesen. Die üblichen Entscheidungsprobleme rund um Kreispackungen beschäftigen sich mit der Frage, ob eine gegebene Menge von Kreisen in ein gegebenes ebenes Polygon gepackt werden können (sei dies das Einheitsquadrat, ein gleichseitiges Dreieck oder ein Rechteck mit bestimmter Höhe), diese Probleme sind $NP$-vollständig. (Standardquelle ist das Paper [1] von Demaine, Fekete & Lang.) Daraus kann man dann leicht interessante Optimierungsprobleme ableiten, bspw. wie hoch ist das kleinste Rechteck (mit dem Einheitsintervall als Grundseite), in das alle Kreise gepackt werden können. Diese abgeleiteten Probleme sind dann $NP$-schwer und nur für die letztere Klasse macht es Sinn Approximationsalgorithmen anzugeben (wie soll man auch die Antwort JA/NEIN eines Entscheidungsproblems approximieren?) Um das alles sauber im Artikel darzustellen und zu motivieren, muss man ein bisschen weiter ausholen. Vielleicht setz ich mich nach Ostern mal dran.

Liebe Grüße -- 2A02:8109:9440:9174:D45D:9C39:F95C:AF4B 13:38, 2. Apr. 2018 (CEST)

Danke für deinen Einwand und die Infos. Da hast du Recht, das ist missverständlich formuliert. Die Approximation die ich meine bekommt als Input einen (ungerichteten) Graphen und berechnet die passenden Radien der dazugehörigen Kreispackung. Wie dazu das entsprechende Entscheidungsproblem zu formulieren ist (oder ob es überhaupt eins gibt); da bin ich mir nicht sicher. --Pizzaschneider (Diskussion) 16:33, 3. Apr. 2018 (CEST)