ในเรขาคณิตเชิงคำนวณปัญหาสี่เหลี่ยมผืนผ้าว่างที่ใหญ่ที่สุด^{[ 2 ]}ปัญหาสี่เหลี่ยมผืนผ้าว่างสูงสุด^{[ 3 ]}หรือปัญหาสี่เหลี่ยมผืนผ้าว่างสูงสุด [ ^{4 ]}คือปัญหาของการหาสี่เหลี่ยมผืนผ้า ที่มีขนาดใหญ่ที่สุดเพื่อวางไว้ท่ามกลางสิ่งกีดขวางในระนาบ มีหลายรูปแบบของปัญหา ^นี้ขึ้นอยู่กับลักษณะเฉพาะของสูตรทั่วไปนี้ โดยเฉพาะอย่างยิ่ง ขึ้นอยู่กับการวัด "ขนาด" โดเมน (ประเภทของสิ่งกีดขวาง) และทิศทางของสี่เหลี่ยมผืนผ้า

ปัญหาประเภทนี้เกิดขึ้น เช่น ในการออกแบบอัตโนมัติทางอิเล็กทรอนิกส์ในการออกแบบและการตรวจสอบเค้าโครงทางกายภาพของวงจรรวม^{[ 5 ]}

สี่เหลี่ยมผืนผ้าว่างที่ใหญ่ที่สุดคือสี่เหลี่ยมผืนผ้าที่ไม่บรรจุอยู่ในสี่เหลี่ยมผืนผ้าว่างอื่น แต่ละด้านของสี่เหลี่ยมผืนผ้าว่างที่ใหญ่ที่สุดจะติดกับสิ่งกีดขวาง (มิฉะนั้นด้านนั้นอาจเลื่อนออกไปด้านนอก ทำให้สี่เหลี่ยมผืนผ้าว่างมีขนาดใหญ่ขึ้น) การประยุกต์ใช้ในลักษณะนี้คือการแจงนับ "สี่เหลี่ยมผืนผ้าสีขาวที่ใหญ่ที่สุด" ใน การวิจัยและพัฒนาการ แบ่งส่วนภาพของการประมวลผลภาพและการรู้จำรูปแบบ [ ^{6 ] ใน}บริบทของอัลกอริทึมจำนวนมากสำหรับสี่เหลี่ยมผืนผ้าว่างที่ใหญ่ที่สุด "สี่เหลี่ยมผืนผ้าว่างที่ใหญ่ที่สุด" เป็นโซลูชันที่เป็นไปได้ที่อัลกอริทึมจะพิจารณา เนื่องจากสามารถพิสูจน์ได้ง่ายว่า เช่นสี่เหลี่ยมผืนผ้าว่างที่มีพื้นที่สูงสุดเป็นสี่เหลี่ยมผืนผ้าว่างที่ใหญ่ที่สุด

ในแง่ของการวัดขนาด กรณีที่พบได้บ่อยที่สุดสองกรณีคือสี่เหลี่ยมผืนผ้าว่างที่มีพื้นที่มากที่สุดและสี่เหลี่ยมผืนผ้าว่างที่มีเส้นรอบวงมากที่สุด^{[ 7 ]}

การจำแนกประเภทที่สำคัญอีกประการหนึ่งคือ สี่เหลี่ยมผืนผ้าที่ต้องการค้นหานั้นเป็นรูป สี่เหลี่ยมผืนผ้า ที่วางตัวตามแกนหรือรูปสี่เหลี่ยมผืนผ้าที่วางตัวตามอำเภอใจ

กรณีที่สี่เหลี่ยมผืนผ้าที่ต้องการเป็นสี่เหลี่ยมจัตุรัสที่วางแนวแกนอาจได้รับการจัดการโดยใช้แผนภาพโวโรนอยในเมตริกสำหรับชุดสิ่งกีดขวางที่สอดคล้องกัน คล้ายกับ ปัญหา วงกลมว่างที่ใหญ่ที่สุดโดยเฉพาะอย่างยิ่ง สำหรับกรณีของจุดภายในสี่เหลี่ยมผืนผ้าอัลกอริทึมที่เหมาะสมที่สุดที่มีความซับซ้อนของเวลาเป็นที่รู้จัก^{[ 8 ]}${\displaystyle L_{1}}$${\displaystyle \Theta (n\log n)}$

ปัญหาที่ Naamad, Lee และ Hsu อภิปรายเป็นครั้งแรกในปี 1983 ^{[ 1 ]}ระบุไว้ดังนี้: กำหนดสี่เหลี่ยมผืนผ้าAที่มี จุด nจุด ให้หาสี่เหลี่ยมผืนผ้าที่มีพื้นที่มากที่สุดที่มีด้านขนานกับด้านของAซึ่งอยู่ภายในAและไม่มีจุดใด ๆ ที่กำหนดให้ Naamad, Lee และ Hsu ได้นำเสนออัลกอริทึมที่มีความซับซ้อนของเวลา โดยที่sคือจำนวนของคำตอบที่เป็นไปได้ กล่าวคือ สี่เหลี่ยมผืนผ้าว่างที่ใหญ่ที่สุด พวกเขายังพิสูจน์ว่าและให้ตัวอย่างที่sเป็นกำลังสองของnหลังจากนั้นมีเอกสารจำนวนมากที่นำเสนออัลกอริทึมที่ดีกว่าสำหรับปัญหานี้ ${\displaystyle O(\min(n^{2},s\log n))}$${\displaystyle s=O(n^{2})}$

ปัญหาของสี่เหลี่ยมจัตุรัสไอโซเทติกว่างเปล่าระหว่างส่วนของเส้นตรงไอโซเทติก ได้รับการพิจารณาครั้งแรก ^{[ 9 ]}ในปี 1990 ^{[ 10 ]}ต่อมาปัญหาทั่วไปของสี่เหลี่ยมจัตุรัสไอโซเทติกว่างเปล่าระหว่างสิ่งกีดขวางที่ไม่ใช่ไอโซเทติกได้รับการพิจารณา^{[ 9 ]}

ในพื้นที่ 3 มิติ อัลกอริทึมเป็นที่รู้จักสำหรับการค้นหา ปัญหา ลูกบาศก์ ไอโซเทติกว่างเปล่าที่ใหญ่ที่สุด รวมถึงการแจงนับลูกบาศก์ไอโซเทติกว่างเปล่าที่ใหญ่ที่สุดทั้งหมด^{[ 11 ]}

• ทรงกลมว่างที่ใหญ่ที่สุด
• ขอบเขตขั้นต่ำ , สี่เหลี่ยมขอบเขตขั้นต่ำ