Хамгийн ойрхон цэгийн хосыг олох¶
Бодлогын томьёолол¶
Хавтгай дээр $n$ цэг өгөгдсөн. Цэг бүр $p_i$ нь өөрийн $(x_i,y_i)$ координатаар тодорхойлогдоно. Тэдгээрийн дундаас хоорондох зай нь хамгийн бага байх хоёр цэгийг олох шаардлагатай:
Бид ердийн Евклидийн зайг авна:
Энгийн алгоритм — бүх хосыг тойрч, тус бүрийн зайг тооцоолох — $O(n^2)$-д ажиллана.
$O(n \log n)$ хугацаанд ажиллах алгоритмыг доор тайлбарлав. Энэ алгоритмыг 1975 онд Shamos, Hoey нар санал болгосон. (Эх сурвалж: Kleinberg, Tardos нарын Algorithm Design-ийн 5-р бүлгийн тэмдэглэл, мөн эндээс үз) Preparata, Shamos нар мөн энэ алгоритм шийдвэрийн модны загварт оновчтой болохыг харуулсан.
Алгоритм¶
Бид алгоритмыг хуваа ба ялагтун алгоритмуудын ерөнхий схемийн дагуу байгуулна: алгоритмыг рекурсив функц хэлбэрээр зохион бүтээх ба түүнд бид цэгүүдийн олонлогийг дамжуулна; энэ рекурсив функц энэ олонлогийг хагаслан хувааж, хагас тус бүр дээр өөрийгөө рекурсивээр дуудаад дараа нь хариултуудыг нэгтгэх зарим үйлдлийг гүйцэтгэнэ. Нэгтгэх үйлдэл нь оновчтой шийдийн нэг цэг нэг хагаст, нөгөө цэг нөгөө хагаст оногдсон тохиолдлыг илрүүлэхээс бүрдэнэ (энэ тохиолдолд хагас тус бүрээс хийсэн рекурсив дуудлага энэ хосыг тусад нь илрүүлж чадахгүй). Хуваа ба ялагтун алгоритмуудын хувьд үргэлж байдаг шиг гол бэрхшээл нь нийлүүлэх үе шатыг үр ашигтай хэрэгжүүлэхэд оршино. Хэрэв рекурсив функцэд $n$ цэгийн олонлог дамжуулагдвал нийлүүлэх үе шат $O(n)$-ээс илүүгүй ажиллах ёстой, тэгвэл бүхэл алгоритмын асимптот $T(n)$-г дараах тэгшитгэлээс олно:
Энэ тэгшитгэлийн шийд нь мэдэгдэж байгаачлан $T(n) = O(n \log n)$ юм.
Тэгэхээр бид алгоритмыг байгуулах руу шилжье. Ирээдүйд нийлүүлэх үе шатыг үр ашигтай хэрэгжүүлэхийн тулд бид цэгүүдийн олонлогийг тэдгээрийн $x$ координатын дагуу хоёр дэд олонлог болгон хуваана: Үнэндээ бид цэгүүдийн олонлогийг ойролцоогоор ижил хэмжээтэй хоёр дэд олонлог болгон хуваах ямар нэг босоо шулуун татна. Ийм хуваалтыг дараах байдлаар хийх нь тохиромжтой: Бид цэгүүдийг тоонуудын хос болгон стандарт аргаар эрэмбэлнэ, өөрөөр хэлбэл:
Дараа нь эрэмбэлсний дараах дунд цэг $p_m (m = \lfloor n/2 \rfloor)$-г аваад түүний өмнөх бүх цэг ба $p_m$ өөрөө эхний хагаст, түүний дараах бүх цэг хоёр дахь хагаст оноогдоно:
Одоо $A_1$ ба $A_2$ олонлог тус бүр дээр рекурсивээр дуудаж бид хагас тус бүрийн хувьд $h_1$ ба $h_2$ хариултыг олно. Мөн тэдгээрийн хамгийн сайныг авна: $h = \min(h_1, h_2)$.
Одоо бид нийлүүлэх үе шат хийх хэрэгтэй, өөрөөр хэлбэл бид хоорондох зай нь $h$-ээс бага бөгөөд нэг цэг нь $A_1$-д, нөгөө нь $A_2$-т орших цэгүүдийн хосуудыг олохыг оролдоно. Босоо шулуунаас $h$-ээс бага зайд байгаа цэгүүдийг л авч үзэхэд хангалттай нь илэрхий, өөрөөр хэлбэл энэ үе шатанд авч үзэх цэгүүдийн $B$ олонлог дараахтай тэнцүү:
$B$ олонлог дахь цэг бүрийн хувьд бид түүнд $h$-ээс ойр байгаа цэгүүдийг олохыг оролдоно. Жишээ нь $y$ координат нь $h$-ээс илүүгүйгээр ялгаатай цэгүүдийг л авч үзэхэд хангалттай. Түүнчлэн $y$ координат нь одоогийн цэгийн $y$ координатаас их байгаа цэгүүдийг авч үзэх нь утгагүй. Ингэснээр цэг $p_i$ бүрийн хувьд бид авч үзэх цэгүүдийн $C(p_i)$ олонлогийг дараах байдлаар тодорхойлно:
Хэрэв бид $B$ олонлогийн цэгүүдийг $y$ координатаар эрэмбэлбэл $C(p_i)$-г олоход маш амархан болно: эдгээр нь $p_i$ цэгийн өмнө дараалан байгаа хэдэн цэг юм.
Тэгэхээр шинэ тэмдэглэгээгээр нийлүүлэх үе шат дараах байдалтай харагдана: $B$ олонлогийг байгуул, доторх цэгүүдийг $y$ координатаар эрэмбэл, дараа нь цэг $p_i \in B$ бүрийн хувьд бүх цэг $p_j \in C(p_i)$-г авч үз, мөн хос $(p_i,p_j)$ бүрийн хувьд зайг тооцоолж, одоогийн хамгийн сайн зайтай харьцуул.
Эхлээд харахад энэ нь оновчтой биш алгоритм хэвээр байна: $C(p_i)$ олонлогуудын хэмжээ $n$ эрэмбэтэй байх ба шаардагдах асимптот биелэхгүй мэт санагдана. Гэвч гайхалтай нь $C(p_i)$ олонлог тус бүрийн хэмжээ $O(1)$ хэмжигдэхүүн болохыг, өөрөөр хэлбэл цэгүүдээс үл хамааран ямар нэг бага тогтмолоос хэтрэхгүйг батлах боломжтой. Энэ баримтын баталгааг дараагийн хэсэгт өгөв.
Эцэст нь дээрх алгоритмд агуулагдах эрэмбэлэлтэд анхаарлаа хандуулъя: эхлээд $(x, y)$ хосоор эрэмбэлэх, дараа нь $B$ олонлогийн элементүүдийг $y$-ээр эрэмбэлэх. Үнэндээ рекурсив функцийн доторх эдгээр хоёр эрэмбэлэлтийг хоёуланг нь арилгаж болно (эс бөгөөс бид нийлүүлэх үе шат-ын $O(n)$ үнэлгээнд хүрэхгүй бөгөөд алгоритмын ерөнхий асимптот $O(n \log^2 n)$ байх байсан). Эхний эрэмбэлэлтээс салахад амархан — энэ эрэмбэлэлтийг рекурс эхлэхээс өмнө гүйцэтгэхэд хангалттай: эцсийн эцэст элементүүд өөрсдөө рекурсын дотор өөрчлөгддөггүй тул дахин эрэмбэлэх шаардлагагүй. Хоёр дахь эрэмбэлэлтийг гүйцэтгэхэд арай илүү хэцүү, түүнийг урьдчилан гүйцэтгэх нь ажиллахгүй. Гэвч мөн хуваа ба ялагтун зарчмаар ажилладаг нийлүүлэх эрэмбэлэлтийг санавал бид энэ эрэмбэлэлтийг рекурстээ зүгээр л шигтгэж болно. Рекурс ямар нэг цэгүүдийн олонлогийг (бидний санаж байгаагаар $(x, y)$ хосоор эрэмбэлэгдсэн) аваад ижил олонлогийг, гэхдээ $y$ координатаар эрэмбэлж буцаадаг байг. Үүний тулд рекурсив дуудлагуудын буцаасан хоёр үр дүнг зүгээр л ($O(n)$-д) нийлүүл. Энэ нь $y$ координатаар эрэмбэлэгдсэн олонлогийг өгнө.
Асимптотын үнэлгээ¶
Дээрх алгоритм үнэхээр $O(n \log n)$-д гүйцэтгэгддэгийг харуулахын тулд бид дараах баримтыг батлах хэрэгтэй: $|C(p_i)| = O(1)$.
Тэгэхээр ямар нэг $p_i$ цэгийг авч үзье; $C(p_i)$ олонлог нь $y$ координат нь $[y_i-h; y_i]$ хэрчимд орших цэгүүдийн олонлог бөгөөд түүнчлэн $x$ координатын дагуу $p_i$ цэг өөрөө ба $C(p_i)$ олонлогийн бүх цэг $2h$ өргөнтэй зурваст оршдогийг сануулъя. Өөрөөр хэлбэл бидний авч үзэж буй $p_i$ ба $C(p_i)$ цэгүүд $2h \times h$ хэмжээтэй тэгш өнцөгтөд оршино.
Бидний даалгавар бол энэ $2h \times h$ тэгш өнцөгтөд орших боломжтой цэгүүдийн хамгийн их тоог үнэлэх явдал юм; ингэснээр бид $C(p_i)$ олонлогийн хамгийн их хэмжээг үнэлнэ. Үүний зэрэгцээ үнэлэхдээ бид давтагдсан цэгүүд байж болохыг мартах ёсгүй.
$h$ нь $A_1$ ба $A_2$ олонлогууд дээрх хоёр рекурсив дуудлагын үр дүнгээс гарсныг санаарай, мөн $A_1$ нь хуваах шулууны зүүн талын ба хэсэгчлэн түүн дээрх цэгүүдийг агуулах ба $A_2$ нь хуваах шулууны үлдсэн цэгүүд ба түүний баруун талын цэгүүдийг агуулна. $A_1$-ээс, мөн $A_2$-оос авсан дурын цэгийн хосын хувьд зай нь $h$-ээс бага байж чадахгүй — эс бөгөөс энэ нь рекурсив функц буруу ажилласан гэсэн үг болно.
$2h \times h$ тэгш өнцөгт дэх цэгүүдийн хамгийн их тоог үнэлэхийн тулд бид түүнийг $h \times h$ хэмжээтэй хоёр квадрат болгон хуваана, эхний квадрат нь $C(p_i) \cap A_1$ бүх цэгийг агуулах ба хоёр дахь нь бусад бүгдийг буюу $C(p_i) \cap A_2$-г агуулна. Дээрх үндэслэлээс эдгээр квадрат тус бүрд дурын хоёр цэгийн хоорондох зай дор хаяж $h$ болох нь гарна.
Бид квадрат бүрд хамгийн ихдээ дөрвөн цэг байхыг харуулъя. Жишээ нь үүнийг дараах байдлаар хийж болно: квадратыг $h/2$ талтай $4$ дэд квадрат болгон хуваа. Тэгвэл эдгээр дэд квадрат тус бүрд нэгээс олон цэг байж болохгүй (учир нь диагональ нь ч $h / \sqrt{2}$-тэй тэнцүү бөгөөд энэ нь $h$-ээс бага). Тиймээс бүхэл квадратад $4$-өөс олон цэг байж болохгүй.
Ингэснээр бид $2h \times h$ тэгш өнцөгтөд $4 \cdot 2 = 8$-аас олон цэг байж болохгүйг, тиймээс $C(p_i)$ олонлогийн хэмжээ шаардлагын дагуу $7$-оос хэтэрч болохгүйг баталлаа.
Implementation¶
We introduce a data structure to store a point (its coordinates and a number) and comparison operators required for two types of sorting:
struct pt {
int x, y, id;
};
struct cmp_x {
bool operator()(const pt & a, const pt & b) const {
return a.x < b.x || (a.x == b.x && a.y < b.y);
}
};
struct cmp_y {
bool operator()(const pt & a, const pt & b) const {
return a.y < b.y;
}
};
int n;
vector<pt> a;
For a convenient implementation of recursion, we introduce an auxiliary function upd_ans(), which will calculate the distance between two points and check whether it is better than the current answer:
double mindist;
pair<int, int> best_pair;
void upd_ans(const pt & a, const pt & b) {
double dist = sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
if (dist < mindist) {
mindist = dist;
best_pair = {a.id, b.id};
}
}
Finally, the implementation of the recursion itself. It is assumed that before calling it, the array $a[]$ is already sorted by $x$-coordinate. In recursion we pass just two pointers $l, r$, which indicate that it should look for the answer for $a[l \ldots r)$. If the distance between $r$ and $l$ is too small, the recursion must be stopped, and perform a trivial algorithm to find the nearest pair and then sort the subarray by $y$-coordinate.
To merge two sets of points received from recursive calls into one (ordered by $y$-coordinate), we use the standard STL $merge()$ function, and create an auxiliary buffer $t[]$(one for all recursive calls). (Using inplace_merge () is impractical because it generally does not work in linear time.)
Finally, the set $B$ is stored in the same array $t$.
vector<pt> t;
void rec(int l, int r) {
if (r - l <= 3) {
for (int i = l; i < r; ++i) {
for (int j = i + 1; j < r; ++j) {
upd_ans(a[i], a[j]);
}
}
sort(a.begin() + l, a.begin() + r, cmp_y());
return;
}
int m = (l + r) >> 1;
int midx = a[m].x;
rec(l, m);
rec(m, r);
merge(a.begin() + l, a.begin() + m, a.begin() + m, a.begin() + r, t.begin(), cmp_y());
copy(t.begin(), t.begin() + r - l, a.begin() + l);
int tsz = 0;
for (int i = l; i < r; ++i) {
if (abs(a[i].x - midx) < mindist) {
for (int j = tsz - 1; j >= 0 && a[i].y - t[j].y < mindist; --j)
upd_ans(a[i], t[j]);
t[tsz++] = a[i];
}
}
}
By the way, if all the coordinates are integer, then at the time of the recursion you can not move to fractional values, and store in $mindist$ the square of the minimum distance.
In the main program, recursion should be called as follows:
t.resize(n);
sort(a.begin(), a.end(), cmp_x());
mindist = 1E20;
rec(0, n);
Шугаман хугацааны санамсаргүй алгоритмууд¶
Шугаман хүлээгдэх хугацаатай санамсаргүй алгоритм¶
1976 онд Rabin-ийн анх санал болгосон өөр нэг арга нь ажиллах хугацааг эвристикээр сайжруулах маш энгийн санаанаас үүдэлтэй: Бид хавтгайг $d \times d$ квадратуудын тор болгон хувааж болох ба тэгвэл зөвхөн ижил блок эсвэл зэргэлдээ блокийн цэгүүдийн хоорондох зайг шалгах шаардлагатай болно (бүх квадрат бие биенээсээ салангид байхаас бусад тохиолдолд, гэвч бид үүнээс зохиомжоороо зайлсхийнэ), учир нь бусад дурын хос ижил квадрат дахь хоёр цэгээс их зайтай байна.
Бид дор хаяж нэг цэг агуулсан квадратуудыг л авч үзнэ. Үлдсэн $k$ квадрат тус бүр дэх цэгүүдийн тоог $n_1, n_2, \dots, n_k$ гэж тэмдэглэе. Дор хаяж хоёр цэг ижил эсвэл зэргэлдээ квадратад байгаа бөгөөд давхардсан цэг байхгүй гэж үзвэл time complexity нь $\Theta\!\left(\sum\limits_{i=1}^k n_i^2\right)$ болно. Бид давхардсан цэгүүдийг хэш хүснэгт ашиглан хүлээгдэх шугаман хугацаанд хайж болох ба хэрэв байвал хариулт нь энэ хос юм.
Баталгаа
$n_i$ цэг агуулсан $i$-р квадратын хувьд доторх хосуудын тоо $\Theta(n_i^2)$ байна. Хэрэв $i$-р квадрат $j$-р квадраттай зэргэлдээ бол бид мөн $n_i n_j \le \max(n_i, n_j)^2 \le n_i^2 + n_j^2$ зайн харьцуулалт хийнэ. Квадрат бүр хамгийн ихдээ $8$ зэргэлдээ квадраттай болохыг анхаарна уу, тиймээс бид бүх харьцуулалтын нийлбэрийг $\Theta(\sum_{i=1}^{k} n_i^2)$-ээр хязгаарлаж болно. $\quad \blacksquare$
Одоо бид $\Theta\!\left(\sum\limits_{i=1}^k n_i^2\right)$-г минимумчлахаар $d$-г хэрхэн тохируулахыг шийдэх хэрэгтэй.
$d$-г сонгох¶
Бидэнд $d$ нь хамгийн бага зай $d$-ийн ойролцоолол байх хэрэгтэй. Ричард Липтон $n$ зайг санамсаргүйгээр түүвэрлэж, $d$-ийн ойролцоолол болгон эдгээр зайнуудын хамгийн багыг $d$ гэж сонгохыг санал болгосон. Одоо бид алгоритмын хүлээгдэх ажиллах хугацаа шугаман болохыг батална.
Баталгаа
$d$-г тодорхой байдлаар, жишээ нь $x$ гэж сонгосон үеийн квадрат дахь цэгүүдийн байрлалыг төсөөл. $d$-г бидний зайн түүврээс үүсэх санамсаргүй хэмжигдэхүүн гэж үз. Бид $d=x$ гэж сонгох үеийн тодорхой байрлалын өртгийн үнэлгээ болгон $C(x) := \sum_{i=1}^{k(x)} n_i(x)^2$ гэж тодорхойлъё. Одоо $C(x) = \lambda(x) \, n$ байхаар $\lambda(x)$-г тодорхойлъё. Ийм $x$ сонголт $n$ хамааралгүй зайн түүврийг даван гарах магадлал хэд вэ? Хэрэв түүвэрлэсэн хосуудын дундаас ганц хос $x$-ээс бага зайтай байвал энэ байрлалыг илүү бага $d$-ээр солино. Квадратын дотор хосуудын ойролцоогоор $1/16$ нь илүү бага зай өгнө (квадрат бүрд дөрвөн дэд квадрат байгааг төсөөл; тагтааны үүрний зарчмаар дор хаяж нэг дэд квадрат $n_i/4$ цэгтэй), тиймээс бидэнд илүү бага эцсийн $d$ өгөх ойролцоогоор $\sum_{i=1}^{k} {n_i/4 \choose 2} \approx \sum_{i=1}^{k} \frac{1}{16} {n_i \choose 2}$ хос байна. Энэ нь ойролцоогоор $\frac{1}{32} \sum_{i=1}^{k} n_i^2 = \frac{1}{32} \lambda(x) n$ юм. Нөгөө талаас түүвэрлэж болох ойролцоогоор $\frac{1}{2} n^2$ хос байна. Бидэнд $x$-ээс бага зайтай хос түүвэрлэх магадлал дор хаяж (ойролцоогоор) дараах байна
тиймээс $n$ раундын явцад ийм дор хаяж нэг хос сонгогдох (улмаар илүү бага $d$ олох) магадлал нь
(бид дурын бодит тоо $x$-ийн хувьд $(1 + x)^n \le e^{xn}$ гэдгийг ашигласан, Бернуллийн тэнцэтгэл бишүүдийг үз).
$\lambda(x)$ өсөх тусам энэ нь экспоненциалаар $1$ рүү тэмүүлэхийг анхаарна уу. Энэ нь муу сонгосон $d$-ийн хувьд $\lambda$ бага байхыг илтгэнэ.
Бид $\Pr(d \le x) \ge 1 - e^{-\lambda(x)/16}$, эсвэл үүнтэй эквивалентээр $\Pr(d \ge x) \le e^{-\lambda(x)/16}$ болохыг харууллаа. Түүний хүлээгдэх утгыг үнэлж чадахын тулд бид $\Pr(\lambda(d) \ge \text{ямар нэг зүйл})$-г мэдэх хэрэгтэй. Бид $\lambda(d) \ge \lambda(x) \iff d \ge x$ болохыг анзаарна. Энэ нь квадратуудыг жижигрүүлэх нь квадрат бүр дэх цэгүүдийн тоог зөвхөн багасгах (цэгүүдийг бусад квадрат руу хуваах) бөгөөд энэ нь квадратуудын нийлбэрийг үргэлжлүүлэн багасгадагтай холбоотой. Тиймээс,
(бид $E[X] = \int_0^{+\infty} \Pr(X \ge x) \, \mathrm{d}x$ гэдгийг ашигласан, Stackexchange дээрх баталгааг үз).
Эцэст нь $\mathbb{E}[C(d)] = \mathbb{E}[\lambda(d) \, n] \le 16n$ бөгөөд хүлээгдэх ажиллах хугацаа нь боломжийн тогтмол үржүүлэгчтэйгээр $O(n)$ болно. $\quad \blacksquare$
Implementation of the algorithm¶
The advantage of this algorithm is that it is straightforward to implement, but still has good performance in practise. We first sample $n$ distances and set $d$ as the minimum of the distances. Then we insert points into the "blocks" by using a hash table from 2D coordinates to a vector of points. Finally, just compute distances between same-block pairs and adjacent-block pairs. Hash table operations have $O(1)$ expected time cost, and therefore our algorithm retains the $O(n)$ expected time cost with an increased constant.
Check out this submission to Library Checker.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
struct pt {
ll x, y;
pt() {}
pt(ll x_, ll y_) : x(x_), y(y_) {}
void read() {
cin >> x >> y;
}
};
bool operator==(const pt& a, const pt& b) {
return a.x == b.x and a.y == b.y;
}
struct CustomHashPoint {
size_t operator()(const pt& p) const {
static const uint64_t C = chrono::steady_clock::now().time_since_epoch().count();
return C ^ ((p.x << 32) ^ p.y);
}
};
ll dist2(pt a, pt b) {
ll dx = a.x - b.x;
ll dy = a.y - b.y;
return dx*dx + dy*dy;
}
pair<int,int> closest_pair_of_points(vector<pt> P) {
int n = int(P.size());
assert(n >= 2);
// if there is a duplicated point, we have the solution
unordered_map<pt,int,CustomHashPoint> previous;
for (int i = 0; i < int(P.size()); ++i) {
auto it = previous.find(P[i]);
if (it != previous.end()) {
return {it->second, i};
}
previous[P[i]] = i;
}
unordered_map<pt,vector<int>,CustomHashPoint> grid;
grid.reserve(n);
mt19937 rd(chrono::system_clock::now().time_since_epoch().count());
uniform_int_distribution<int> dis(0, n-1);
ll d2 = dist2(P[0], P[1]);
pair<int,int> closest = {0, 1};
auto candidate_closest = [&](int i, int j) -> void {
ll ab2 = dist2(P[i], P[j]);
if (ab2 < d2) {
d2 = ab2;
closest = {i, j};
}
};
for (int i = 0; i < n; ++i) {
int j = dis(rd);
int k = dis(rd);
while (j == k) k = dis(rd);
candidate_closest(j, k);
}
ll d = ll( sqrt(ld(d2)) + 1 );
for (int i = 0; i < n; ++i) {
grid[{P[i].x/d, P[i].y/d}].push_back(i);
}
// same block
for (const auto& it : grid) {
int k = int(it.second.size());
for (int i = 0; i < k; ++i) {
for (int j = i+1; j < k; ++j) {
candidate_closest(it.second[i], it.second[j]);
}
}
}
// adjacent blocks
for (const auto& it : grid) {
auto coord = it.first;
for (int dx = 0; dx <= 1; ++dx) {
for (int dy = -1; dy <= 1; ++dy) {
if (dx == 0 and dy == 0) continue;
pt neighbour = pt(
coord.x + dx,
coord.y + dy
);
for (int i : it.second) {
if (not grid.count(neighbour)) continue;
for (int j : grid.at(neighbour)) {
candidate_closest(i, j);
}
}
}
}
}
return closest;
}
Шугаман хүлээгдэх хугацаатай өөр нэг санамсаргүй алгоритм¶
Одоо бид практик талаасаа арай дутуу боловч хүлээгдэх шугаман хугацаанд ажилладгийг харуулахад маш амархан өөр нэг санамсаргүй алгоритмыг танилцуулна.
- $n$ цэгийг санамсаргүйгээр сэлгэ
- $\delta := \operatorname{dist}(p_1, p_2)$ гэж ав
- Хавтгайг $\delta/2$ талтай квадратууд болгон хуваа
- $i = 1,2,\dots,n$-ийн хувьд:
- $p_i$-д харгалзах квадратыг ав
- Хавтгайг хуваасан квадратуудын тор дахь бидний квадратаас хоёр алхмын дотор байгаа $25$ квадратыг тойр
- Хэрэв тэдгээр квадрат дахь ямар нэг $p_j$ нь $\operatorname{dist}(p_j, p_i) < \delta$ байвал
- $\delta := \operatorname{dist}(p_j, p_i)$-тэйгээр хуваалт ба квадратуудыг дахин тооцоол
- $p_1, \dots, p_i$ цэгүүдийг харгалзах квадратуудад хадгал
- эс бөгөөс $p_i$-г харгалзах квадратад хадгал
- $\delta$-г гарга
Зөв байдал нь дурын мөчид бидэнд $\delta$ зайтай ямар нэг хос аль хэдийн байгаа тул бид зөвхөн $\delta$-ээс бага зайтай шинэ хосуудыг олохыг оролддог гэсэн баримтаас гарна. Квадрат бүр $\delta/2$ талтай тул нэр дэвшигч хос хамгийн ихдээ $2$ квадратын зайд байж болох тул өгөгдсөн цэгийн хувьд бид эргэн тойрны $25$ квадрат дахь нэр дэвшигчдийг шалгана. Түүнээс хол квадрат дахь дурын цэг үргэлж $\delta$-ээс их зай өгнө.
Энэ алгоритм бүх зүйлийг олон удаа дахин тооцоолдог тул удаан мэт харагдаж болох ч бид нийт хүлээгдэх өртөг шугаман болохыг харуулж чадна.
Баталгаа
$X_i$ нь $p_i$ цэг $\delta$-г өөрчилж, өгөгдлийн бүтцийг дахин тооцоолоход хүргэх үед $1$, эс бөгөөс $0$ байх санамсаргүй хэмжигдэхүүн байг. $i$-р алхамд бид зөвхөн эхний $i$ цэгийг авч үзэж байгаа тул өртөг нь $O(n + \sum_{i=1}^{n} i X_i)$ болохыг харуулахад амархан. Гэвч $\Pr(X_i = 1) \le \frac{2}{i}$ болох нь тогтоогддог. Энэ нь $i$-р алхамд $\delta$ нь $\{p_1,\dots,p_i\}$ дахь хамгийн ойрхон хосын зай байх ба $\Pr(X_i = 1)$ нь $p_i$ хамгийн ойрхон хост харьяалагдах магадлал бөгөөд энэ нь боломжит $i(i-1)$ хосын дундаас зөвхөн $2(i-1)$ хост тохиолддог (бүх зай ялгаатай гэж үзвэл), тиймээс бид цэгүүдийг өмнө нь жигд холисон тул магадлал хамгийн ихдээ $\frac{2(i-1)}{i(i-1)} = \frac{2}{i}$ байна.
Тиймээс бид хүлээгдэх өртөг нь дараах болохыг харж болно
Ерөнхийлөлт: хамгийн бага периметртэй гурвалжныг олох¶
Дээр тайлбарласан алгоритмыг энэ бодлогод сонирхолтойгоор ерөнхийлдөг: өгөгдсөн цэгүүдийн олонлогийн дундаас хоорондох хос хосын зайнуудын нийлбэр хамгийн бага байх гурван өөр цэгийг сонго.
Үнэндээ энэ бодлогыг бодохын тулд алгоритм ижил хэвээр байна: бид талбарыг босоо шулуунаар хоёр хагас болгон хувааж, хоёр хагас дээр шийдийг рекурсивээр дуудаж, олсон периметрүүдээс хамгийн бага $minper$-г сонгож, $minper / 2$ зузаантай зурвас байгуулж, хариултыг сайжруулж чадах бүх гурвалжныг тойрно. ($\le minper$ периметртэй гурвалжин $\le minper / 2$ хамгийн урт талтай болохыг анхаарна уу.)
Дасгал бодлогууд¶
- UVA 10245 "The Closest Pair Problem" [difficulty: low]
- SPOJ #8725 CLOPPAIR "Closest Point Pair" [difficulty: low]
- CODEFORCES Team Olympiad Saratov - 2011 "Minimum amount" [difficulty: medium]
- Google CodeJam 2009 Final "Min Perimeter" [difficulty: medium]
- SPOJ #7029 CLOSEST "Closest Triple" [difficulty: medium]
- TIMUS 1514 National Park [difficulty: medium]