最大の空の長方形

求める長方形が軸に沿った正方形である場合は、ボロノイ図を使用して処理できます。${\displaystyle L_{1}}$対応する障害物セットのメトリックは、最大の空円問題と同様です。特に、長方形内の点の場合、時間計算量の最適なアルゴリズムが存在します。${\displaystyle \Theta (n\log n)}$知られている。^{[ 8 ]}

1983年にNaamad、Lee、Hsuによって初めて議論された問題^{[ 1 ]}は、次のように述べられています。n個の点を含む長方形Aが与えられたとき、 Aの辺と平行で、 Aの内部にあり、与えられた点を一切含まない、面積が最大の長方形を見つけます。Naamad、Lee、Hsuは、時間計算量nのアルゴリズムを発表しました。${\displaystyle O(\min(n^{2},s\log n))}$ここで、sは実行可能な解の数、つまり最大の空の長方形の数である。彼らはまた、次のことを証明した。${\displaystyle s=O(n^{2})}$そして、 sがnに関して二次関数となる例を示した。その後、この問題に対するより優れたアルゴリズムを提示する論文が多数発表された。

等長線分間の空の等長長方形の問題は、1990 年に初めて検討されました^{[ 9 ]。[ 10 ]}その後、非等長障害物間の空の等長長方形というより一般的な問題が検討されました。^{[ 9 ]}

3次元空間では、最大の等長空直方体問題を見つけるアルゴリズムや、すべての最大の等長空直方体を列挙するアルゴリズムが知られています。^{[ 11 ]}