Du hast doch schon Datenstrukturen für eine effiziente Suche nach Nachbarrechtecken? Man könnte versuchen, sich mit Hilfe dieser Strukturen an der Außenseite entlangzuhangeln (ohne die ggf. quadratisch vielen inneren Rechtecke betrachten zu müssen). Könnte aber in jedem Fall ein bißchen fummelig werden. (Je nachdem, welche Anforderungen (und Ansprüche (an sich selbst)) man hat, und um welchen zeitlichen Rahmen es geht, sollte man vielleicht erstmal zusehen, das überhaupt stabil hinzukriegen, und danach über schnellere Alternativen nachzudenken).