أكبر مستطيل فارغ

يمكن معالجة الحالة التي يكون فيها المستطيل المطلوب مربعًا موجهًا نحو محور باستخدام مخططات فورونوي في${\displaystyle L_{1}}$مقاييس لمجموعة العوائق المقابلة، على غرار مسألة أكبر دائرة فارغة . على وجه الخصوص، في حالة النقاط داخل المستطيل، خوارزمية مثلى ذات تعقيد زمني${\displaystyle \Theta (n\log n)}$معروف. ^{[ 8 ]}

تُعرَّف المسألة التي ناقشها نعماد ولي وهسو لأول مرة عام 1983 ^{[ 1 ]} على النحو التالي: بالنظر إلى مستطيل A يحتوي على n نقطة، جد مستطيلاً ذا مساحة أكبر وأضلاع موازية لأضلاع A يقع داخل A ولا يحتوي على أي من النقاط المعطاة. وقد قدم نعماد ولي وهسو خوارزمية ذات تعقيد زمني${\displaystyle O(\min(n^{2},s\log n))}$حيث يمثل s عدد الحلول الممكنة، أي المستطيلات الفارغة القصوى. وقد أثبتوا أيضًا أن${\displaystyle s=O(n^{2})}$وقدم مثالاً تكون فيه s دالة تربيعية في n . بعد ذلك، قدم عدد من الأوراق البحثية خوارزميات أفضل لهذه المشكلة.

تم تناول مشكلة المستطيلات الفارغة متساوية العتبة بين القطع المستقيمة متساوية العتبة لأول مرة ^{[ 9 ]} في عام 1990. ^{[ 10 ]} وفي وقت لاحق، تم تناول مشكلة أكثر عمومية تتمثل في المستطيلات الفارغة متساوية العتبة بين العوائق غير متساوية العتبة. ^{[ 9 ]}

في الفضاء ثلاثي الأبعاد، توجد خوارزميات معروفة لإيجاد أكبر مشكلة مكعب متساوي الأضلاع فارغ أقصى ، وكذلك لحصر جميع المكعبات الفارغة متساوية الأضلاع القصوى. ^{[ 11 ]}