Partitionieren einer verbundenen Form in Rechtecke

8

Ich stelle mir vor, dass dies eine einführende Frage zur rechnergestützten Geometrie sein muss, bin mir aber nicht sicher, welche Suchphrasen am besten geeignet sind, und ich interessiere mich auch für Variationen der Frage. Ich hoffe daher auf Hinweise auf nützliche Referenzen. Ich interessiere mich für mögliche Algorithmen für das folgende Problem.

Eingang: A verbunden Punkte (Form) in der Serie . Ausgabe: Eine Aufteilung der Form in Rechtecke, sodass sich die Rechtecke nicht überlappen und nur die Form abdecken, kein "leerer" Raum.Z×Z

Ich bin daran interessiert, die minimale Anzahl von Rechtecken zu finden, die "beste" Menge von Rechtecken für jede Vorstellung von Best, ob dieses Problem für verschiedene Klassen von Formen einfacher oder schwieriger wird.

Vielen Dank. :-)

reference-request cg.comp-geom Aaron Sterling
quelle
3
Schauen Sie sich diese MathOverflow-Frage an
Peter Shor
@ Peter Shor: Vielen Dank. Das sieht genau so aus, wie ich es brauche.
Aaron Sterling
3
Sollte dies also eine Antwort sein? oder sollte die frage geschlossen werden?
Suresh Venkat
4
@Suresh: Ich denke, es löst meine Frage, obwohl vielleicht jemand anderes etwas über Varianten des Problems hinzufügen kann. Ich würde es vorziehen, wenn die Frage offen bleibt, falls jemand anderes etwas hinzuzufügen hat. Ich würde es gerne als Antwort akzeptieren, wenn @Peter Shor es als solches posten würde.
Aaron Sterling
Ich denke, ich kann es als Antwort posten, obwohl es so aussieht, als hätte ich sehr wenig Arbeit geleistet. Sie sollten warten, bis Sie sicher sind, dass niemand etwas hinzuzufügen hat.
Peter Shor

Antworten:

9

David Eppstein hat diese Frage hier auf MathOverflow hervorragend beantwortet (Beantwortung einer Frage, für die es keine ganz so gute Antwort gibt). Zusammenfassend gibt es einen Polynom-Zeit-Algorithmus zum Ermitteln der minimalen Anzahl von Rechtecken.

Peter Shor
quelle