What question did this study set out to answer?

Diese Forschung untersucht, wie ein Polygon mit der geringsten Anzahl an kleinen zusammenhängenden Teilen bedeckt oder partitioniert werden kann.

May 29, 2026Open Access

Bedeckung und Partitionierung komplexer Objekte mit kleinen Teilen

Key Points

Diese Forschung untersucht, wie ein Polygon mit der geringsten Anzahl an kleinen zusammenhängenden Teilen bedeckt oder partitioniert werden kann.
Entwicklung eines lokalen Suchalgorithmus zur Optimierung des Teileaustausches in einer Polygonbedeckung.
Demonstration der Äquivalenz zwischen optimalen Bedeckungen und Partitionen in Bezug auf die Anzahl der Teile.
Analyse der Komplexität in drei Dimensionen, Feststellung der NP-Schwere in bestimmten Fällen.
Eine 1 + O(1/√k) Approximation für die Bedeckung von Polygonen mit Löchern erreicht, was eine signifikante Verbesserung gegenüber früheren Methoden darstellt.
Bestätigung, dass die Beschaffung einer optimalen Bedeckung oder Partition in drei Dimensionen NP-schwer ist, selbst für einfache Polyeder.

Abstract

Wir untersuchen die Probleme der Bedeckung oder Partitionierung eines Polygons P (möglicherweise mit Löchern) unter Verwendung einer minimalen Anzahl von kleinen Teilen, wobei ein kleines Teil ein zusammenhängendes Unterpolygon ist, das in einem achsenausgerichteten Einheitsquadrat enthalten ist. Bei der Bedeckung möchten wir P als Vereinigung kleiner Teile schreiben, und bei der Partitionierung verlangen wir zudem, dass die Teile paarweise innerlich disjunkt sind. Wir zeigen, dass diese Probleme tatsächlich äquivalent sind: Optimale Bedeckungen und Partitionen haben die gleiche Anzahl an Teilen. Bei der Bedeckung versucht ein natürlicher lokale Suchalgorithmus wiederholt, k Teile aus einer Kandidatenbedeckung durch k-1 Teile zu ersetzen. In zwei Dimensionen und für ausreichend großes k zeigen wir, dass, wenn ein solcher Tausch nicht möglich ist, die Bedeckung eine 1 + O(1/√k) Approximation ist, was die erste PTAS für das Problem ergibt. Vor unserer Arbeit war der einzige bekannte Algorithmus eine 13-Approximation, die nur für Polygone ohne Löcher funktioniert Abrahamsen und Rasmussen, SODA 2025. Im Gegensatz dazu zeigen wir in der dreidimensionalen Version des Problems, dass es NP-schwer ist, eine optimale Bedeckung oder Partition innerhalb eines Faktors zu approximieren, der in n logarithmisch ist, selbst wenn P einfach ist, d.h. Genus 0 hat und keine Löcher aufweist.

Bookmark

View Full Paper