geometry - マージンのある一連のポイントの最小スパン ライン

Question

ジオメトリに関連する簡単なプログラミングの問題があります。鉛筆と紙を使って (ビジュアル モードで) 解けますが、プログラムできるかどうかはわかりません。コード自体は必要ありませんが、疑似コードまたは実装するアイデアが必要です。

ライン内の 4 ポイントで、位置が与えられます。各ポイントには、ポイントの位置の後に指定された、自分の周りに最小限のスペースが必要です。上記のすべての要件を満たす最小の (長さの) 線分を見つけたいと考えています。言い換えれば、要件の周りに最小限のスペースで、これらのポイントに最小限のスパン ラインが必要です。

例: $p_i$: (x, L)、ここで x は位置 (実数) を表し、L は x の周囲の最小スペース要件を表します。

p1: (1,1) p2: (2,1) p3: (5,1) p4: (7,2)

グラフ表示：

示されているように、結果は長さ 6 の 1 から 7 までの線分です。

別の例: p1: (2,1) p2: (3,2) p3: (4,1.5) p4: (6.5,0.5)

結果 (下の緑の線) は、2 から 6.5 までの線分 (長さ: 4.5) です。

Answer 1

最適な結果の長さは常に max(x_i)-min(x_i) i=1,2,3,4 を超えます

1 つの端点が x_i に一致する最適解が常に存在することも簡単です。つまり、スパン最適結果をロールして、点 (x_1 など) と一致させることができます。

$-\infty$ から $+\infty$ までスイープします。x_1 を開始し、その右マージンにまたがります。さらに、他のすべてのポイント (つまり、左マージンが開始されたポイント) を開始します。つまり、最初のポイントをできるだけ遅く開始し、その後、他のすべてのポイントをできるだけ早く開始します。最後に、x_1 の前に左マージンが開始された点 x_i がある場合、この差を diff_i と呼びます。すべての diff_i をすべての x_i に追加し、結果の最終点からすべてのセグメントを見つけます (つまり、if (x_i+diff_i>current_end_position then current_end_position=x_i+diff_i.

コメントしてくれてありがとう。