nの最小被覆半径

これを解決するアルゴリズムはありますか？nの最小被覆半径

2016-11-01 Guru

もちろん、使用できるアルゴリズムがあります。どのような時間の複雑さを達成しようとしていますか？ – ollpu

これは、アルゴリズムを要求しています。壊れたコードの助けにはなりません。 – thecoshman

センターも整数でも、半分にすることもできますか？ – m69

貪欲アルゴリズムで解けるだ関連の問題があります：点と半径与え、円の最小数を見つけます。このアルゴリズムは、左端がxでソートされた点で時刻O（n）に実行されている左端の非表示点にある円を繰り返し配置します。

要求された問題のアルゴリズムを取得するには、ポイントを一度ソートしてから、二分探索を使用して最大でd個の円になる最小半径を見つけます。 x座標を機械語で表すことができると仮定すると、これはうまくいくはずです。（そうでない場合は、他のアルゴリズムもあります）

出典

2016-11-01 18:21:31

@Blender彼は答えにバイナリ検索を使うよう提案しています。私は彼に同意します。この質問に似て：[リンク]（http://stackoverflow.com/questions/40189551/arrange-n-items-in-k-nonempty-groups-such-that-the-difference-between-the-minimu/40205972 ＃40205972）と[link]（http://stackoverflow.com/questions/39673898/divide-array-into-k-contiguos-partitions-such-that-sum-of-maximum-partition-is-m/39675098# 39675098） – Tempux

答えて

関連する問題