Hierarchische Darstellungen von Sammlungen kleiner Rechtecke

Eine Tutorial-Umfrage über hierarchische Datenstrukturen zur Darstellung von Sammlungen kleiner Rechtecke wird vorgestellt. Rechtecke werden oft als Näherung für Formen verwendet, für die sie als das minimal rechtwinklige umschließende Objekt dienen. Sie treten in Anwendungen in der Kartographie sowie bei der Überprüfung von Entwurfsregeln in der sehr groß angelegten Integration (VLSI) auf. Die verschiedenen Datenstrukturen werden dahingehend diskutiert, wie sie die Ausführung von Abfragen zu Nähebeziehungen unterstützen. Der Fokus liegt auf Schnittmengen- und Teilmengenabfragen. Mehrere Arten von Darstellungen werden beschrieben. Einige sind für die Verwendung mit dem Plane-Sweep-Paradigma konzipiert, das gut für statische Sammlungen von Rechtecken funktioniert. Andere sind auf dynamische Sammlungen ausgerichtet. In diesem Fall reduziert eine Darstellung jedes Rechteck auf einen Punkt in einem höheren mehrdimensionalen Raum und behandelt das Problem als eines, das Punktdaten betrifft. Die andere Darstellung ist flächenbasiert – das heißt, sie hängt vom physischen Umfang jedes Rechtecks ab.