アレンジメントでポリゴンを数える
線の配置について $\cal{A}$平面では、誘導ポリゴン $P$ は、以下を満たす単純なポリゴンです：（a）すべてのエッジ $e$ の $P$ いくつかの行にあります $\ell$ の $\cal{A}$、および（b）すべての行 $\ell \in \cal{A}$ エッジと同一線上にあります $e$ の $P$。場合$P$ 持っている $k$ エッジと $\cal{A}$ 持っている $n$ 行、 $k \ge n$。のいくつかのエッジに注意してください$P$ の同じ行にある可能性があります $\cal{A}$。
の行が $\cal{A}$ 2本の線が平行でなく、3本の線が1点で交わらないという意味で、一般的な位置にあります。 $\cal{A}$誘導ポリゴンがあります。1私の質問は、誘導ポリゴンのカウントに関するものです。
Q。すべての取り決めにわたって$\cal{A}$ の $n$ 一般的な位置の線、誘導ポリゴンの数の上限と下限は何ですか $\cal{A}$、そしてどの取り決めがそれらの限界を達成しますか？
明確にするために（MaxAlekseyevに感謝します）： $\cal{A}$ の特定の配置である $n$ 一般的な位置の線。 $\cal{A}$一定数の不一致の誘導ポリゴンをサポートします。この数の最大値と最小値は、$n$ 行？
他のおそらくより簡単な質問は、それ自体を示唆しています。例えば、どの配置にも複数の凸状の誘導ポリゴンがありますか？
私の当初の目的は、ポリゴンを誘発する最小領域を見つけることでしたが、これはおそらく難しいでしょう。
1 Scharf、Ludmila、およびMarcScherfenberg。「線の配置のポリゴンを誘導します。」ではアルゴリズムと計算に関する国際シンポジウム、頁507から519まで。スプリンガー、ベルリン、ハイデルベルク、2008年。スプリンガーリンク。
回答
幾何学的な二重に行く、
- 線は極座標を持つポイントにマップされます $(\varphi,\,r)$ どこ $\varphi$ 法線の角度で、原点から離れる方向を指し、正の角度です。 $x$-軸と $r$ 原点から線までの距離
- ユークリッド平面で交差する線のペアは、それぞれの二重点を接続する線分にマップされます。
- デュアルプレーンのポイントセグメント配置は、グラフの平面埋め込みとして解釈でき、線の単純な配置によって完全なグラフが生成されます。
線の単純な配置が完全なグラフを生成するということは、それらが常に単一のポリゴンで表すことができることを意味します。二重平面内の点を通るハミルトンサイクルならどれでもかまいません。
他の質問は、セル複合体に関する結果によって答えられるようです。その一部は、たとえば「」のような引用されたウィキペディアの記事にあります。配置内の単一のセルはすべてのn行で囲まれている場合がありますが、一般にm個の異なるセルがすべてn本の線で囲まれています。むしろ、m個のセルの合計の複雑さは最大で$Θ(m^{2/3}n^{2/3} + n)$、[11]平面内の点線入射に関するセメレディ・トロッターの定理で発生するのとほぼ同じ限界"
$ILP$ 配合
線と多角形の辺の間の1対1の対応が必要な場合、整数線形計画法の定式化により、望ましい最適化基準に従うことができる解が得られる場合があります。
バイナリ変数は、交点で線を分割することによって作成されたエッジに対応します。制約は、同一線上のエッジの変数の合計が $1$そして2つのラインのすべての交差点にその隣接する縁部に対応する変数の和、すなわち、等しくなる
場合$l_{1i},l_{i1},l_{2,i},l_{i2}$ 線のエッジに対応するバイナリ変数です $L_1$ そして $L_2$ ポイントで交差する $(x_i,y_i)$、その後 $l_{1i}+l_{i1}=l_{2,i}+l_{i2}$ 満たす必要があります。
サブツアー除去制約を課すことで、エッジとラインの間に全単射がある単一のポリゴンの存在に答えることができます。