Π”ΠΎΠΏΠΎΠΌΠΎΠ³Π° Ρƒ написанні освітніх Ρ€ΠΎΠ±Ρ–Ρ‚...
Π”ΠΎΠΏΠΎΠΌΠΎΠΆΠ΅ΠΌΠΎ швидко Ρ‚Π° Π· Π³Π°Ρ€Π°Π½Ρ‚Ρ–Ρ”ΡŽ якості!

Π’ΠΈΠΏΡƒΠΊΠ»Π° ΠΎΠ±ΠΎΠ»ΠΎΡ‡ΠΊΠ° (Ρ€Π΅Ρ„Π΅Ρ€Π°Ρ‚)

Π Π΅Ρ„Π΅Ρ€Π°Ρ‚Π”ΠΎΠΏΠΎΠΌΠΎΠ³Π° Π² написанніДізнатися Π²Π°Ρ€Ρ‚Ρ–ΡΡ‚ΡŒΠΌΠΎΡ”Ρ— Ρ€ΠΎΠ±ΠΎΡ‚ΠΈ

Π—Π½Π°ΠΉΠ΄Π΅ΠΌΠΎ ΠΌΡ–Π½Ρ–ΠΌΠ°Π»ΡŒΠ½Π΅ Ρ‚Π° ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡŒΠ½Π΅ значСння Ρ… ΠΊΠΎΠΎΡ€Π΄ΠΈΠ½Π°Ρ‚ΠΈ Ρ‚ΠΎΡ‡ΠΎΠΊ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S Ρ‚Π° Ρ€ΠΎΠ·Ρ–Π±'Ρ”ΠΌΠΎ Π²Π΅Ρ€Ρ‚ΠΈΠΊΠ°Π»ΡŒΠ½Ρƒ полосу ΠΌΡ–ΠΆ Π½ΠΈΠΌΠΈ Π½Π° k ΠΏΠΎΠ»ΠΎΡ Ρ€Ρ–Π²Π½ΠΎΡ— ΡˆΠΈΡ€ΠΈΠ½ΠΈ. Π’ ΠΊΠΎΠΆΠ½Ρ–ΠΉ Ρ–Π· Ρ†ΠΈΡ… k ΠΏΠΎΠ»ΠΎΡ ΡˆΡƒΠΊΠ°ΡŽΡ‚ΡŒΡΡ Π΄Π²Ρ– Ρ‚ΠΎΡ‡ΠΊΠΈ, які ΠΌΠ°ΡŽΡ‚ΡŒ ΠΌΡ–Π½Ρ–ΠΌΠ°Π»ΡŒΠ½Ρƒ Ρ‚Π° ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡŒΠ½Ρƒ Ρƒ ΠΊΠΎΠΎΡ€Π΄ΠΈΠ½Π°Ρ‚Ρƒ (ΠΎΠ±ΠΈΡ€Π°Ρ”Ρ‚ΡŒΡΡ 2k Ρ‚ΠΎΡ‡ΠΎΠΊ). ΠžΠ±ΠΈΡ€Π°ΡŽΡ‚ΡŒΡΡ Ρ‚Π°ΠΊΠΎΠΆ Ρ‚ΠΎΡ‡ΠΊΠΈ Π· Π΅ΠΊΡΡ‚Ρ€Π΅ΠΌΠ°Π»ΡŒΠ½ΠΈΠΌΠΈ значСннями Ρ… ΠΊΠΎΠΎΡ€Π΄ΠΈΠ½Π°Ρ‚иякщо Ρ—Ρ… Π΄Π΅ΠΊΡ–Π»ΡŒΠΊΠ°, Ρ‚ΠΎ ΠΎΠ±ΠΈΡ€Π°ΡŽΡ‚ΡŒΡΡ Π΄Π²Ρ– Ρ‚ΠΎΡ‡ΠΊΠΈ Π· Π΅ΠΊΡΡ‚Ρ€Π΅ΠΌΠ°Π»ΡŒΠ½ΠΈΠΌΠΈ значСннями… Π§ΠΈΡ‚Π°Ρ‚ΠΈ Ρ‰Π΅ >

Π’ΠΈΠΏΡƒΠΊΠ»Π° ΠΎΠ±ΠΎΠ»ΠΎΡ‡ΠΊΠ° (Ρ€Π΅Ρ„Π΅Ρ€Π°Ρ‚) (Ρ€Π΅Ρ„Π΅Ρ€Π°Ρ‚, курсова, Π΄ΠΈΠΏΠ»ΠΎΠΌ, ΠΊΠΎΠ½Ρ‚Ρ€ΠΎΠ»ΡŒΠ½Π°)

Π Π΅Ρ„Π΅Ρ€Π°Ρ‚ Π½Π° Ρ‚Π΅ΠΌΡƒ:

ΠžΠΏΡƒΠΊΠ»Π° ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠ°

ΠžΠ·Π½Π°Ρ‡Π΅Π½Π½Ρ. Афінна гСомСтрія ΡΠΊΠ»Π°Π΄Π°Ρ”Ρ‚ΡŒΡΡ Π· ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ скалярів S (дійсних чисСл), ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ Ρ‚ΠΎΡ‡ΠΎΠΊ P Ρ‚Π° ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ Π²Ρ–Π»ΡŒΠ½ΠΈΡ… Π²Π΅ΠΊΡ‚ΠΎΡ€Ρ–Π² V (Π°Π±ΠΎ просто Π²Π΅ΠΊΡ‚ΠΎΡ€Ρ–Π²). Π’ΠΎΡ‡ΠΊΠΈ Π²ΠΈΠΊΠΎΡ€ΠΈΡΡ‚ΠΎΠ²ΡƒΡŽΡ‚ΡŒΡΡ для задання полоТСння, Π° Π²Π΅ΠΊΡ‚ΠΎΡ€ΠΈ — для задання напрямку Ρ‚Π° Π²Π΅Π»ΠΈΡ‡ΠΈΠ½, Ρ…ΠΎΡ‡Π° Π²ΠΎΠ½ΠΈ Ρ– Π½Π΅ ΠΌΠ°ΡŽΡ‚ΡŒ фіксованого полоТСння Ρƒ ΠΏΡ€ΠΎΡΡ‚ΠΎΡ€Ρ–.

ΠžΠΏΠ΅Ρ€Π°Ρ†Ρ–Ρ— Π°Ρ„Ρ–Π½Π½ΠΎΡ— Π³Π΅ΠΎΠΌΠ΅Ρ‚Ρ€Ρ–Ρ—:

1. Π΄ΠΎΠ±ΡƒΡ‚ΠΎΠΊ скаляра Π½Π° Π²Π΅ΠΊΡ‚ΠΎΡ€: S * V V;

2. додавання Π²Π΅ΠΊΡ‚ΠΎΡ€Ρ–Π²: V + V V;

3. віднімання Ρ‚ΠΎΡ‡ΠΎΠΊ: P — P V;

4. додавання Ρ‚ΠΎΡ‡ΠΊΠΈ Ρ‚Π° Π²Π΅ΠΊΡ‚ΠΎΡ€Π°: P + V P;

додавання Π²Π΅ΠΊΡ‚ΠΎΡ€Ρ–Π² віднімання Ρ‚ΠΎΡ‡ΠΎΠΊ додавання Ρ‚ΠΎΡ‡ΠΎΠΊ Ρ‚Π° Π²Π΅ΠΊΡ‚ΠΎΡ€Π° Π Ρ–Π·Π½ΠΈΡ†Π΅ΡŽ Π΄Π²ΠΎΡ… Ρ‚ΠΎΡ‡ΠΎΠΊ p Ρ‚Π° q Π±ΡƒΠ΄Π΅ Π²Π΅ΠΊΡ‚ΠΎΡ€, який Π½Π°ΠΏΡ€Π°Π²Π»Π΅Π²ΠΎ Π· q Π΄ΠΎ p.

ΠšΡ–Π»ΡŒΠΊΡ–ΡΡ‚ΡŒ ΠΎΠΏΠ΅Ρ€Π°Ρ†Ρ–ΠΉ ΠΌΠΎΠΆΠ½Π° Ρ€ΠΎΠ·ΡˆΠΈΡ€ΠΈΡ‚ΠΈ. Наприклад, Ρ€Ρ–Π·Π½ΠΈΡ†ΡŽ Π²Π΅ΠΊΡ‚ΠΎΡ€Ρ–Π² ΠΌΠΎΠΆΠ½Π° Π²ΠΈΠ·Π½Π°Ρ‡ΠΈΡ‚ΠΈ як u — v = u + (-1) * v, Π° ділСння Π²Π΅ΠΊΡ‚ΠΎΡ€Π° Π½Π° ΡΠΊΠ°Π»ΡΡ€ як v / a = (1 / a) * v. АлС Π½Π΅ ΠΌΠΎΠΆΠ½Π° Π΄ΠΎΠ΄Π°Π²Π°Ρ‚ΠΈ Π΄Π²Ρ– Ρ‚ΠΎΡ‡ΠΊΠΈ Π°Π±ΠΎ ΠΌΠ½ΠΎΠΆΠΈΡ‚ΠΈ Ρ‚ΠΎΡ‡ΠΊΡƒ Π½Π° ΡΠΊΠ°Π»ΡΡ€.

ΠžΠ·Π½Π°Ρ‡Π΅Π½Π½Ρ. НСхай Π² Ed Π·Π°Π΄Π°Π½ΠΎ k Ρ€Ρ–Π·Π½ΠΈΡ… Ρ‚ΠΎΡ‡ΠΎΠΊ p1, p2, …, pk. МноТина Ρ‚ΠΎΡ‡ΠΎΠΊ p Ρ‚Π°ΠΊΠΈΡ… Ρ‰ΠΎ.

p = a1p1 + a2p2 + … + akpk (ai R, a1 + a2 + …+ ak = 1).

Π½Π°Π·ΠΈΠ²Π°Ρ”Ρ‚ΡŒΡΡ Π°Ρ„Ρ–Π½Π½ΠΎΡŽ мноТиною, ΠΏΠΎΡ€ΠΎΠ΄ΠΆΠ΅Π½ΠΎΡŽ Ρ‚ΠΎΡ‡ΠΊΠ°ΠΌΠΈ p1, p2, …, pk, Π° p Π½Π°Π·ΠΈΠ²Π°Ρ”Ρ‚ΡŒΡΡ Π°Ρ„Ρ–Π½Π½ΠΎΡŽ ΠΊΠΎΠΌΠ±Ρ–Π½Π°Ρ†Ρ–Ρ”ΡŽ Ρ‚ΠΎΡ‡ΠΎΠΊ p1, p2, …, pk.

Афінна комбінація Ρ” частковим Π²ΠΈΠΏΠ°Π΄ΠΊΠΎΠΌ Π»Ρ–Π½Ρ–ΠΉΠ½ΠΎΡ— ΠΊΠΎΠΌΠ±Ρ–Π½Π°Ρ†Ρ–Ρ— (Π²Π²ΠΎΠ΄ΠΈΡ‚ΡŒΡΡ Π΄ΠΎΠ΄Π°Ρ‚ΠΊΠΎΠ²Π° ΡƒΠΌΠΎΠ²Π° a1 + a2 + …+ ak = 1). ΠŸΡ€ΠΈ k = 2 Π°Ρ„Ρ–Π½Π½Π° ΠΌΠ½ΠΎΠΆΠΈΠ½Π° — Ρ†Π΅ ΠΏΡ€ΡΠΌΠ°, Ρ‰ΠΎ ΠΏΡ€ΠΎΡ…ΠΎΠ΄ΠΈΡ‚ΡŒ Ρ‡Π΅Ρ€Π΅Π· Π΄Π²Ρ– Ρ‚ΠΎΡ‡ΠΊΠΈ p1 Ρ‚Π° p2.

ΠŸΡ€ΠΈΠΊΠ»Π°Π΄. НСхай Π΄Π°Π½ΠΎ Π΄Π²Ρ– Ρ‚ΠΎΡ‡ΠΊΠΈ p1, p2 Ρ‚Π° Ρ‡ΠΈΡΠ»ΠΎ Π°. ΠŸΠΎΠ·Π½Π°Ρ‡ΠΈΠΌΠΎ Ρ‡Π΅Ρ€Π΅Π· Aff (p0, p1, a) ΠΊΠΎΠΌΠ±Ρ–Π½Π°Ρ†Ρ–ΡŽ (1 — a) * p1 + a * p2 = p1 + a * (p2 — p1). Π›Ρ–Π²Π° частина рівності ΠΌΡ–ΡΡ‚ΠΈΡ‚ΡŒ нСдопустиму ΠΎΠΏΠ΅Ρ€Π°Ρ†Ρ–ΡŽ (додавання Ρ‚ΠΎΡ‡ΠΎΠΊ), Π°Π»Π΅ Π΅ΠΊΠ²Ρ–Π²Π°Π»Π΅Π½Ρ‚Π½ΠΈΠΉ Ρ—ΠΉ Π°Π»Π³Π΅Π±Ρ€Π°Ρ—Ρ‡Π½ΠΈΠΉ Π²ΠΈΡ€Π°Π· ΠΏΡ€Π°Π²ΠΎΡ— частини Ρ” допустимим. Π―ΠΊΡ‰ΠΎ p1 p2, Ρ‚ΠΎ Aff (p0, p1, a) Π»Π΅ΠΆΠΈΡ‚ΡŒ Π½Π° ΠΏΡ€ΡΠΌΡ–ΠΉ p1p2. Коли, Π° ΠΏΡ€ΠΎΠ±Ρ–Π³Π°Ρ” всі дійсні значСння, Ρ‚ΠΎ Π²ΠΈΡ€Π°Π· Aff (p0, p1, a) ΠΏΡ€ΠΎΠ±Ρ–Π³Π°Ρ” всі Ρ‚ΠΎΡ‡ΠΊΠΈ прямої p1p2. ΠŸΡ€ΠΈ a [0- 1] значСння Aff (p0, p1, a) ΠΏΡ€ΠΎΠ±Ρ–Π³Π°Ρ” всі Ρ‚ΠΎΡ‡ΠΊΠΈ Π²Ρ–Π΄Ρ€Ρ–Π·ΠΊΡƒ [pq].

Для прСдставлСння Π²Π΅ΠΊΡ‚ΠΎΡ€Ρ–Π² Ρ‚Π° Ρ‚ΠΎΡ‡ΠΎΠΊ Π² Π°Ρ„Ρ–Π½Π½ΠΎΠΌΡƒ просторі Π²ΠΈΠΊΠΎΡ€ΠΈΡΡ‚ΠΎΠ²ΡƒΡŽΡ‚ΡŒΡΡ Π³ΠΎΠΌΠΎΠ³Π΅Π½Π½Ρ– ΠΊΠΎΠΎΡ€Π΄ΠΈΠ½Π°Ρ‚ΠΈ. ΠŸΡ€ΠΈ Ρ€ΠΎΠ±ΠΎΡ‚Ρ– Π· d Π²ΠΈΠΌΡ–Ρ€Π½ΠΈΠΌ Π°Ρ„Ρ–Π½Π½ΠΈΠΌ простором ΠΊΠΎΠΎΡ€Π΄ΠΈΠ½Π°Ρ‚ΠΈ Π±ΡƒΠ΄Π΅ΠΌΠΎ прСдставляти (d + 1) — ΠΊΠΎΡ€Ρ‚Π΅ΠΆΠ°ΠΌΠΈ дійсних чисСл. ΠŸΠ΅Ρ€ΡˆΠΈΠΉ Π΅Π»Π΅ΠΌΠ΅Π½Ρ‚ ΠΊΠΎΡ€Ρ‚Π΅ΠΆΠ° Π΄ΠΎΡ€Ρ–Π²Π½ΡŽΡ” 1 для Ρ‚ΠΎΡ‡ΠΊΠΈ Ρ– 0 для Π²Π΅ΠΊΡ‚ΠΎΡ€Π°. Π†Π½ΡˆΡ– d Π΅Π»Π΅ΠΌΠ΅Π½Ρ‚Ρ–Π² ΠΊΠΎΡ€Ρ‚Π΅ΠΆΠ° Π²Ρ–Π΄ΠΏΠΎΠ²Ρ–Π΄Π°ΡŽΡ‚ΡŒ Π±Π΅Π·ΠΏΠΎΡΠ΅Ρ€Π΅Π΄Π½ΡŒΠΎ ΠΊΠΎΠΎΡ€Π΄ΠΈΠ½Π°Ρ‚Π°ΠΌ.

P (1- 1- 3), Q (1- 4- 1), u (0- 1- 2).

P — Q = (1−1- 1−4- 3−1) = (0- -3- 2).

ΠžΠ·Π½Π°Ρ‡Π΅Π½Π½Ρ. Π’Ρ€ΠΈ Ρ‚ΠΎΡ‡ΠΊΠΈ p, q, r Π½Π° ΠΏΠ»ΠΎΡ‰ΠΈΠ½Ρ– ΠΌΠ°ΡŽΡ‚ΡŒ Π΄ΠΎΠ΄Π°Ρ‚Π½ΡŽ ΠΎΡ€Ρ–Ρ”Π½Ρ‚Π°Ρ†Ρ–ΡŽ, якщо Π²ΠΎΠ½ΠΈ ΡƒΡ‚Π²ΠΎΡ€ΡŽΡŽΡ‚ΡŒ Ρ‚Ρ€ΠΈΠΊΡƒΡ‚Π½ΠΈΠΊ, ΠΎΡ€Ρ–Ρ”Π½Ρ‚ΠΎΠ²Π°Π½ΠΈΠΉ ΠΏΡ€ΠΎΡ‚ΠΈ Π³ΠΎΠ΄ΠΈΠ½Π½ΠΈΠΊΠΎΠ²ΠΎΡ— стрілки Ρ‚Π° Π²Ρ–Π΄'Ρ”ΠΌΠ½Ρƒ ΠΎΡ€Ρ–Ρ”Π½Ρ‚Π°Ρ†Ρ–ΡŽ, якщо ΠΎΠ±Ρ…Ρ–Π΄ Ρ‚Ρ€ΠΈΠΊΡƒΡ‚Π½ΠΈΠΊΠ° pqr Π²Ρ–Π΄Π±ΡƒΠ²Π°Ρ”Ρ‚ΡŒΡΡ Π·Π° Π³ΠΎΠ΄ΠΈΠ½Π½ΠΈΠΊΠΎΠ²ΠΎΡŽ ΡΡ‚Ρ€Ρ–Π»ΠΊΠΎΡŽ. Π’Ρ€ΠΈ Ρ‚ΠΎΡ‡ΠΊΠΈ p, q, r ΠΌΠ°ΡŽΡ‚ΡŒ Π½ΡƒΠ»ΡŒΠΎΠ²Ρƒ ΠΎΡ€Ρ–Ρ”Π½Ρ‚Π°Ρ†Ρ–ΡŽ, якщо Π²ΠΎΠ½ΠΈ Π»Π΅ΠΆΠ°Ρ‚ΡŒ Π½Π° ΠΎΠ΄Π½Ρ–ΠΉ прямій.

додатня Π½ΡƒΠ»ΡŒΠΎΠ²Π° Π²Ρ–Π΄'Ρ”ΠΌΠ½Π° ΠžΡ€Ρ–Ρ”Π½Ρ‚Π°Ρ†Ρ–Ρ Π²ΠΈΠ·Π½Π°Ρ‡Π°Ρ”Ρ‚ΡŒΡΡ Π·Π½Π°ΠΊΠΎΠΌ Π΄Π΅Ρ‚Π΅Ρ€ΠΌΡ–Π½Π°Π½Ρ‚Π°, Π²ΠΈΠ·Π½Π°Ρ‡Π΅Π½ΠΎΠ³ΠΎ ΠΊΠΎΠΎΡ€Π΄ΠΈΠ½Π°Ρ‚Π°ΠΌΠΈ Ρ‚Ρ€ΡŒΠΎΡ… Ρ‚ΠΎΡ‡ΠΎΠΊ Π² Π³ΠΎΠΌΠΎΠ³Π΅Π½Π½ΠΈΡ… ΠΊΠΎΠΎΡ€Π΄ΠΈΠ½Π°Ρ‚Π°Ρ…:

Orient (p, q, r) = | 1 p x p y 1 q x q y 1 r x r y | .

ΠžΠ·Π½Π°Ρ‡Π΅Π½Π½Ρ. НСхай Π² ΠΏΡ€ΠΎΡΡ‚ΠΎΡ€Ρ– Ed Π·Π°Π΄Π°Π½Π° ΠΏΡ–Π΄ΠΌΠ½ΠΎΠΆΠΈΠ½Π° L. ΠΡ„Ρ–Π½Π½ΠΎΡŽ оболонкою aff (L) ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ L Π½Π°Π·ΠΈΠ²Π°Ρ”Ρ‚ΡŒΡΡ наймСнша Π°Ρ„Ρ–Π½Π½Π° ΠΌΠ½ΠΎΠΆΠΈΠ½Π°, яка ΠΌΡ–ΡΡ‚ΠΈΡ‚ΡŒ L.

ΠΡ„Ρ–Π½Π½ΠΎΡŽ оболонкою Π²Ρ–Π΄Ρ€Ρ–Π·ΠΊΠ° Ρ” пряма, Π°Ρ„Ρ–Π½Π½ΠΎΡŽ оболонкою плоского ΠΌΠ½ΠΎΠ³ΠΎΠΊΡƒΡ‚Π½ΠΈΠΊΠ° Ρ” ΠΏΠ»ΠΎΡ‰ΠΈΠ½Π°.

ΠžΠ·Π½Π°Ρ‡Π΅Π½Π½Ρ. НСхай Π² Ed Π·Π°Π΄Π°Π½ΠΎ k Ρ€Ρ–Π·Π½ΠΈΡ… Ρ‚ΠΎΡ‡ΠΎΠΊ p1, p2, …, pk. МноТина Ρ‚ΠΎΡ‡ΠΎΠΊ p Ρ‚Π°ΠΊΠΈΡ… Ρ‰ΠΎ.

p = a1p1 + a2p2 + … + akpk (ai R, ai 0, a1 + a2 + …+ ak = 1).

Π½Π°Π·ΠΈΠ²Π°Ρ”Ρ‚ΡŒΡΡ ΠΎΠΏΡƒΠΊΠ»ΠΎΡŽ мноТиною, ΠΏΠΎΡ€ΠΎΠ΄ΠΆΠ΅Π½ΠΎΡŽ Ρ‚ΠΎΡ‡ΠΊΠ°ΠΌΠΈ p1, p2, …, pk, Π° p Π½Π°Π·ΠΈΠ²Π°Ρ”Ρ‚ΡŒΡΡ ΠΎΠΏΡƒΠΊΠ»ΠΎΡŽ ΠΊΠΎΠΌΠ±Ρ–Π½Π°Ρ†Ρ–Ρ”ΡŽ Ρ‚ΠΎΡ‡ΠΎΠΊ p1, p2, …, pk.

ΠžΠΏΡƒΠΊΠ»Π° комбінація Ρ” звуТСнням Π°Ρ„Ρ–Π½Π½ΠΎΡ— ΠΊΠΎΠΌΠ±Ρ–Π½Π°Ρ†Ρ–Ρ—. ΠŸΡ€ΠΈ k = 2 ΠΎΠΏΡƒΠΊΠ»ΠΎΡŽ мноТиною Ρ” Π²Ρ–Π΄Ρ€Ρ–Π·ΠΎΠΊ, який сполучає Π·Π°Π΄Π°Π½Ρ– Ρ‚ΠΎΡ‡ΠΊΠΈ.

ΠžΠ·Π½Π°Ρ‡Π΅Π½Π½Ρ. НСхай Π² ΠΏΡ€ΠΎΡΡ‚ΠΎΡ€Ρ– Ed Π·Π°Π΄Π°Π½Π° ΠΏΡ–Π΄ΠΌΠ½ΠΎΠΆΠΈΠ½Π° L. ΠžΠΏΡƒΠΊΠ»ΠΎΡŽ оболонкою conv (L) ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ L Π½Π°Π·ΠΈΠ²Π°Ρ”Ρ‚ΡŒΡΡ наймСнша ΠΎΠΏΡƒΠΊΠ»Π° ΠΌΠ½ΠΎΠΆΠΈΠ½Π°, яка ΠΌΡ–ΡΡ‚ΠΈΡ‚ΡŒ L.

ΠžΠ·Π½Π°Ρ‡Π΅Π½Π½Ρ. ΠŸΠΎΠ»Ρ–Π΅Π΄Ρ€Π°Π»ΡŒΠ½ΠΎΡŽ мноТиною Π² Π½Π°Π·ΠΈΠ²Π°Ρ”Ρ‚ΡŒΡΡ ΠΏΠ΅Ρ€Π΅Ρ‚ΠΈΠ½ скінчСнної ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ Π·Π°ΠΌΠΊΠ½Π΅Π½ΠΈΡ… півпросторів (півпростір — Ρ†Π΅ Ρ‡Π°ΡΡ‚ΠΈΠ½Π° Ed, Ρ€ΠΎΠ·Ρ‚Π°ΡˆΠΎΠ²Π°Π½Π° ΠΏΠΎ ΠΎΠ΄Π½Ρƒ сторону Π²Ρ–Π΄ дСякої Π³Ρ–ΠΏΠ΅Ρ€ΠΏΠ»ΠΎΡ‰ΠΈΠ½ΠΈ).

ΠŸΠΎΠ»Ρ–Π΅Π΄Ρ€Π°Π»ΡŒΠ½Π° ΠΌΠ½ΠΎΠΆΠΈΠ½Π° Ρ” ΠΎΠΏΡƒΠΊΠ»ΠΎΡŽ, ΠΎΡΠΊΡ–Π»ΡŒΠΊΠΈ півпростір Ρ” ΠΎΠΏΡƒΠΊΠ»ΠΈΠΌ Ρ‚Π° ΠΏΠ΅Ρ€Π΅Ρ‚ΠΈΠ½ ΠΎΠΏΡƒΠΊΠ»ΠΈΡ… ΠΌΠ½ΠΎΠΆΠΈΠ½ Ρ” ΠΎΠΏΡƒΠΊΠ»ΠΎΡŽ мноТиною. ΠŸΠ»ΠΎΡΠΊΡ– ΠΌΠ½ΠΎΠ³ΠΎΠΊΡƒΡ‚Π½ΠΈΠΊΠΈ Ρ‚Π° Ρ‚Ρ€ΠΈΠ²ΠΈΠΌΡ–Ρ€Π½Ρ– ΠΌΠ½ΠΎΠ³ΠΎΠ³Ρ€Π°Π½Π½ΠΈΠΊΠΈ Ρ” ΠΏΡ€ΠΈΠΊΠ»Π°Π΄Π°ΠΌΠΈ скінчСнних ΠΏΠΎΠ»Ρ–Π΅Π΄Ρ€Π°Π»ΡŒΠ½ΠΈΡ… ΠΌΠ½ΠΎΠΆΠΈΠ½. Π‘ΠΊΡ–Π½Ρ‡Π΅Π½Π½Ρƒ d — ΠΌΡ–Ρ€Π½Ρƒ ΠΏΠΎΠ»Ρ–Π΅Π΄Ρ€Π°Π»ΡŒΠ½Ρƒ ΠΌΠ½ΠΎΠΆΠΈΠ½Ρƒ Π±ΡƒΠ΄Π΅ΠΌΠΎ Π½Π°Π·ΠΈΠ²Π°Ρ‚ΠΈ ΠΎΠΏΡƒΠΊΠ»ΠΈΠΌ d — ΠΏΠΎΠ»Ρ–Ρ‚ΠΎΠΏΠΎΠΌ (Π°Π±ΠΎ просто ΠΏΠΎΠ»Ρ–Ρ‚ΠΎΠΏΠΎΠΌ).

Π’Π΅ΠΎΡ€Π΅ΠΌΠ°. ΠžΠΏΡƒΠΊΠ»Π° ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠ° скінчСнної ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ Ρ‚ΠΎΡ‡ΠΎΠΊ Π² Ρ” ΠΎΠΏΡƒΠΊΠ»ΠΈΠΌ ΠΏΠΎΠ»Ρ–Ρ‚ΠΎΠΏΠΎΠΌ. КоТний ΠΎΠΏΡƒΠΊΠ»ΠΈΠΉ ΠΏΠΎΠ»Ρ–Ρ‚ΠΎΠΏ Ρ” ΠΎΠΏΡƒΠΊΠ»ΠΎΡŽ оболонкою дСякої скінчСнної ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ Ρ‚ΠΎΡ‡ΠΎΠΊ.

ΠžΠΏΡƒΠΊΠ»ΠΈΠΉ ΠΏΠΎΠ»Ρ–Ρ‚ΠΎΠΏ Π·Π°Π΄Π°Ρ”Ρ‚ΡŒΡΡ описом ΠΉΠΎΠ³ΠΎ Π³Ρ€Π°Π½ΠΈΡ†Ρ–, яка ΡΠΊΠ»Π°Π΄Π°Ρ”Ρ‚ΡŒΡΡ Π· Π³Ρ€Π°Π½Π΅ΠΉ. КоТна Π³Ρ€Π°Π½ΡŒ ΠΎΠΏΡƒΠΊΠ»ΠΎΠ³ΠΎ ΠΏΠΎΠ»Ρ–Ρ‚ΠΎΠΏΠ° Ρ” ΠΎΠΏΡƒΠΊΠ»ΠΎΡŽ мноТиною (ΠΏΠΎΠ»Ρ–Ρ‚ΠΎΠΏΠΎΠΌ Π½ΠΈΠ·ΡŒΠΊΠΎΡ— розмірності). Π―ΠΊΡ‰ΠΎ ΠΏΠΎΠ»Ρ–Ρ‚ΠΎΠΌ ΠΌΠ°Ρ” Π²ΠΈΠΌΡ–Ρ€Π½Ρ–ΡΡ‚ΡŒ d, Ρ‚ΠΎ ΠΉΠΎΠ³ΠΎ d — 1 Π³Ρ€Π°Π½Ρ– Π½Π°Π·ΠΈΠ²Π°ΡŽΡ‚ΡŒΡΡ гіпСргранями, d — 2 Π³Ρ€Π°Π½Ρ– - підгранями, 1 — Π³Ρ€Π°Π½Ρ– - Ρ€Π΅Π±Ρ€Π°ΠΌΠΈ, 0 — Π³Ρ€Π°Π½Ρ– - Π²Π΅Ρ€ΡˆΠΈΠ½Π°ΠΌΠΈ. Для 3 ΠΏΠΎΠ»Ρ–Ρ‚ΠΎΠΏΠ° гіпСргранями Ρ” плоскі ΠΌΠ½ΠΎΠ³ΠΎΠΊΡƒΡ‚Π½ΠΈΠΊΠΈ, Π° ΠΏΡ–Π΄Π³Ρ€Π°Π½Ρ– Ρ‚Π° Ρ€Π΅Π±Ρ€Π° ΡΠΏΡ–Π²ΠΏΠ°Π΄Π°ΡŽΡ‚ΡŒ. Π’ Ρ†Ρ–ΠΉ Ρ‚Π΅Ρ€ΠΌΡ–Π½ΠΎΠ»ΠΎΠ³Ρ–Ρ— пороТня ΠΌΠ½ΠΎΠΆΠΈΠ½Π° Ρ‚Ρ€Π°ΠΊΡ‚ΡƒΡ”Ρ‚ΡŒΡΡ як (-1) Π³Ρ€Π°Π½ΡŒ.

ΠžΠ·Π½Π°Ρ‡Π΅Π½Π½Ρ. d ΠΏΠΎΠ»Ρ–Ρ‚ΠΎΠΏ Π½Π°Π·ΠΈΠ²Π°Ρ”Ρ‚ΡŒΡΡ d ΡΠΈΠΌΠΏΠ»Π΅ΠΊΡΠΎΠΌ, якщо Π²Ρ–Π½ Ρ” ΠΎΠΏΡƒΠΊΠ»ΠΎΡŽ оболонкою (d + 1) Π°Ρ„Ρ–Π½Π½ΠΎ Π½Π΅Π·Π°Π»Π΅ΠΆΠ½ΠΈΡ… Ρ‚ΠΎΡ‡ΠΎΠΊ. КоТна ΠΏΡ–Π΄ΠΌΠ½ΠΎΠΆΠΈΠ½Π° Π· Ρ†ΠΈΡ… d Π²Π΅Ρ€ΡˆΠΈΠ½ Ρ” симплСксом Ρ– Ρ” Π³Ρ€Π°Π½Π½ΡŽ. КоТна k Π³Ρ€Π°Π½ΡŒ ΠΌΡ–ΡΡ‚ΠΈΡ‚ΡŒ 2k+1 Π³Ρ€Π°Π½Π΅ΠΉ розмірностСй k, k-1, k-2, …, 0, -1.

ΠŸΡ€ΠΈ d = 0, 1, 2, 3 Π²Ρ–Π΄ΠΏΠΎΠ²Ρ–Π΄Π½ΠΈΠΉ симплСкс Ρ” Ρ‚ΠΎΡ‡ΠΊΠΎΡŽ, Ρ€Π΅Π±Ρ€ΠΎΠΌ, Ρ‚Ρ€ΠΈΠΊΡƒΡ‚Π½ΠΈΠΊΠΎΠΌ Ρ‚Π° Ρ‚Ρ€ΠΈΠΊΡƒΡ‚Π½ΠΎΡŽ ΠΏΡ–Ρ€Π°ΠΌΡ–Π΄ΠΎΡŽ.

Наприклад, Ρ‚Ρ€ΠΈΠΊΡƒΡ‚Π½Π° ΠΏΡ–Ρ€Π°ΠΌΡ–Π΄Π° (3 Π³Ρ€Π°Π½ΡŒ) ΠΌΡ–ΡΡ‚ΠΈΡ‚ΡŒ ΠΎΠ΄Π½Ρƒ 3 Π³Ρ€Π°Π½ΡŒ (сама ΠΏΡ–Ρ€Π°ΠΌΡ–Π΄Π°), Ρ‡ΠΎΡ‚ΠΈΡ€ΠΈ 2 Π³Ρ€Π°Π½Ρ– (Ρ‚Ρ€ΠΈΠΊΡƒΡ‚Π½ΠΈΠΊΠΈ), ΡˆΡ–ΡΡ‚ΡŒ 1 Π³Ρ€Π°Π½Π΅ΠΉ (Ρ€Π΅Π±Ρ€Π°), Ρ‡ΠΎΡ‚ΠΈΡ€ΠΈ 0 Π³Ρ€Π°Π½Π΅ΠΉ (Π²Π΅Ρ€ΡˆΠΈΠ½ΠΈ) Ρ‚Π° ΠΎΠ΄Π½Ρƒ (-1) Π³Ρ€Π°Π½ΡŒ (пороТня ΠΌΠ½ΠΎΠΆΠΈΠ½Π°), Ρ‰ΠΎ Ρ€Π°Π·ΠΎΠΌ складає 16 = 24 Π³Ρ€Π°Π½Π΅ΠΉ.

ΠžΠ·Π½Π°Ρ‡Π΅Π½Π½Ρ. d ΠΏΠΎΠ»Ρ–Ρ‚ΠΎΠΏ Π½Π°Π·ΠΈΠ²Π°Ρ”Ρ‚ΡŒΡΡ ΡΠΈΠΌΠΏΠ»Ρ–Ρ†ΠΈΠ°Π»ΡŒΠ½ΠΈΠΌ, якщо ΠΉΠΎΠ³ΠΎ ΠΊΠΎΠΆΠ½Π° Π³Ρ–ΠΏΠ΅Ρ€Π³Ρ€Π°Π½ΡŒ Ρ” симплСксом.

Π—Π°Π΄Π°Ρ‡Π° 1. ΠžΠΏΡƒΠΊΠ»Π° ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠ°. Π’ Ed Π·Π°Π΄Π°Π½ΠΎ ΠΌΠ½ΠΎΠΆΠΈΠ½Ρƒ S, Ρ‰ΠΎ ΠΌΡ–ΡΡ‚ΠΈΡ‚ΡŒ N Ρ‚ΠΎΡ‡ΠΎΠΊ. НСобхідно ΠΏΠΎΠ±ΡƒΠ΄ΡƒΠ²Π°Ρ‚ΠΈ Ρ—Ρ… ΠΎΠΏΡƒΠΊΠ»Ρƒ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΡƒ (ΠΏΠΎΠ²Π½ΠΈΠΉ опис Π³Ρ€Π°Π½ΠΈΡ†Ρ– CH (S)).

Π—Π°Π΄Π°Ρ‡Π° 2. ΠšΡ€Π°ΠΉΠ½Ρ– Ρ‚ΠΎΡ‡ΠΊΠΈ. Π’ Ed Π·Π°Π΄Π°Π½ΠΎ ΠΌΠ½ΠΎΠΆΠΈΠ½Ρƒ S, Ρ‰ΠΎ ΠΌΡ–ΡΡ‚ΠΈΡ‚ΡŒ N Ρ‚ΠΎΡ‡ΠΎΠΊ. НСобхідно Π²ΠΈΠ·Π½Π°Ρ‡ΠΈΡ‚ΠΈ Ρ‚Ρ– Π· Π½ΠΈΡ…, які Ρ” Π²Π΅Ρ€ΡˆΠΈΠ½Π°ΠΌΠΈ ΠΎΠΏΡƒΠΊΠ»ΠΎΡ— ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ conv (S).

Π—Π°Π΄Π°Ρ‡Π° 3. ΠŸΠ΅Ρ€Π΅Π²Ρ–Ρ€ΠΊΠ° крайності Ρ‚ΠΎΡ‡ΠΎΠΊ ΠΏΠ»ΠΎΡ‰ΠΈΠ½ΠΈ. На ΠΏΠ»ΠΎΡ‰ΠΈΠ½Ρ– Π·Π°Π΄Π°Π½ΠΎ N Ρ‚ΠΎΡ‡ΠΎΠΊ. Π’ΠΈΠ·Π½Π°Ρ‡ΠΈΡ‚ΠΈ, Ρ‡ΠΈ Ρ” Π²ΠΎΠ½ΠΈ Π²Π΅Ρ€ΡˆΠΈΠ½Π°ΠΌΠΈ своєї власної ΠΎΠΏΡƒΠΊΠ»ΠΎΡ— ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ.

Π’Π΅ΠΎΡ€Π΅ΠΌΠ°. Π—Π°Π΄Π°Ρ‡Π° сортування Π·Π²ΠΎΠ΄ΠΈΡ‚ΡŒΡΡ Π·Π° Π»Ρ–Π½Ρ–ΠΉΠ½ΠΈΠΉ час Π΄ΠΎ Π·Π°Π΄Π°Ρ‡Ρ– ΠΏΠΎΠ±ΡƒΠ΄ΠΎΠ²ΠΈ ΠΎΠΏΡƒΠΊΠ»ΠΎΡ— ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ. Для знаходТСння впорядкованих N Ρ‚ΠΎΡ‡ΠΎΠΊ ΠΎΠΏΡƒΠΊΠ»ΠΎΡ— ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ ΠΏΠΎΡ‚Ρ€Ρ–Π±Π΅Π½ час O (N log N).

ДовСдСння. НСхай Π΄Π°Π½ΠΎ N Π΄ΠΎΠ΄Π°Ρ‚Π½ΠΈΡ… дійсних чисСл x1, x2, …, xN. ΠŸΠΎΡΡ‚Π°Π²ΠΈΠΌΠΎ Ρƒ Π²Ρ–Π΄ΠΏΠΎΠ²Ρ–Π΄Π½Ρ–ΡΡ‚ΡŒ Ρ‚ΠΎΡ‡Ρ†Ρ– xi Ρ‚ΠΎΡ‡ΠΊΡƒ (xi, xi+1) Ρ– присвоємо Ρ—ΠΉ Π½ΠΎΠΌΠ΅Ρ€ i. Π£Ρ‚Π²ΠΎΡ€Π΅Π½Ρ– Ρ‚ΠΎΡ‡ΠΊΠΈ Π»Π΅ΠΆΠ°Ρ‚ΡŒ Π½Π° ΠΏΠ°Ρ€Π°Π±ΠΎΠ»Ρ– y = x2. ΠžΠΏΡƒΠΊΠ»Π° ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠ° Ρ†Ρ–Ρ”Ρ— ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ Ρ‚ΠΎΡ‡ΠΎΠΊ Π±ΡƒΠ΄Π΅ складатися Π·Ρ– списку Ρ‚ΠΎΡ‡ΠΎΠΊ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ, впорядкованому Π·Π° Π·Π½Π°Ρ‡Π΅Π½Π½ΡΠΌ абсциси.

ΠžΠ·Π½Π°Ρ‡Π΅Π½Π½Ρ. Π’ΠΎΡ‡ΠΊΠ° p ΠΎΠΏΡƒΠΊΠ»ΠΎΡ— ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S Π½Π°Π·ΠΈΠ²Π°Ρ”Ρ‚ΡŒΡΡ ΠΊΡ€Π°ΠΉΠ½ΡŒΠΎΡŽ, якщо Π½Π΅ існує ΠΏΠ°Ρ€ΠΈ Ρ‚ΠΎΡ‡ΠΎΠΊ a, b S Ρ‚Π°ΠΊΠΈΡ…, Ρ‰ΠΎ Π»Π΅ΠΆΠΈΡ‚ΡŒ Π½Π° Π²Ρ–Π΄ΠΊΡ€ΠΈΡ‚ΠΎΠΌΡƒ Π²Ρ–Π΄Ρ€Ρ–Π·ΠΊΡƒ ab.

МноТина E ΠΊΡ€Π°ΠΉΠ½Ρ–Ρ… Ρ‚ΠΎΡ‡ΠΎΠΊ S ΠΏΡ€Π΅Π΄ΡΡ‚авляє собою Π½Π°ΠΉΠΌΠ΅Π½ΡˆΡƒ ΠΏΡ–Π΄ΠΌΠ½ΠΎΠΆΠΈΠ½Ρƒ S, яка ΠΌΠ°Ρ” Π²Π»Π°ΡΡ‚ΠΈΠ²Ρ–ΡΡ‚ΡŒ: conv (E) = conv (S), ΠΏΡ€ΠΈ Ρ‡ΠΎΠΌΡƒ Π• Π² Ρ‚очності співпадає Π· ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΎΡŽ Π²Π΅Ρ€ΡˆΠΈΠ½ conv (S).

Для знаходТСння ΠΎΠΏΡƒΠΊΠ»ΠΎΡ— ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ скінчСнної ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ Π½Π΅ΠΎΠ±Ρ…Ρ–Π΄Π½ΠΎ Π²ΠΈΠΊΠΎΠ½Π°Ρ‚ΠΈ наступнС:

1. Π’ΠΈΠ·Π½Π°Ρ‡ΠΈΡ‚ΠΈ ΠΊΡ€Π°ΠΉΠ½Ρ– Ρ‚ΠΎΡ‡ΠΊΠΈ;

2. Впорядкувати Ρ†Ρ– Ρ‚ΠΎΡ‡ΠΊΠΈ Ρ‚Π°ΠΊ, Ρ‰ΠΎΠ± Π²ΠΎΠ½ΠΈ ΡƒΡ‚Π²ΠΎΡ€ΡŽΠ²Π°Π»ΠΈ ΠΎΠΏΡƒΠΊΠ»ΠΈΠΉ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡƒΡ‚Π½ΠΈΠΊ.

Π’Π΅ΠΎΡ€Π΅ΠΌΠ°. Π’ΠΎΡ‡ΠΊΠ° p Π½Π΅ Ρ” ΠΊΡ€Π°ΠΉΠ½ΡŒΠΎΡŽ плоскої ΠΎΠΏΡƒΠΊΠ»ΠΎΡ— ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S Ρ‚ΠΎΠ΄Ρ– Ρ– Ρ‚Ρ–Π»ΡŒΠΊΠΈ Ρ‚ΠΎΠ΄Ρ–, ΠΊΠΎΠ»ΠΈ Π²ΠΎΠ½Π° Π»Π΅ΠΆΠΈΡ‚ΡŒ Π² Π΄Π΅ΡΠΊΠΎΠΌΡƒ Ρ‚Ρ€ΠΈΠΊΡƒΡ‚Π½ΠΈΠΊΡƒ, Π²Π΅Ρ€ΡˆΠΈΠ½Π°ΠΌΠΈ якого Ρ” Ρ‚ΠΎΡ‡ΠΊΠΈ Π· S, Π°Π»Π΅ сама Π²ΠΎΠ½Π° Π½Π΅ Ρ” Π²Π΅Ρ€ΡˆΠΈΠ½ΠΎΡŽ Ρ†ΡŒΠΎΠ³ΠΎ Ρ‚Ρ€ΠΈΠΊΡƒΡ‚Π½ΠΈΠΊΠ°.

Існує O (N3) Ρ‚Ρ€ΠΈΠΊΡƒΡ‚Π½ΠΈΠΊΡ–Π², які Π²ΠΈΠ·Π½Π°Ρ‡Π°ΡŽΡ‚ΡŒΡΡ N Ρ‚ΠΎΡ‡ΠΊΠ°ΠΌΠΈ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S. ΠžΡ‚ΠΆΠ΅ Π·Π° Ρ‡Π°Ρ O (N3) ΠΌΠΎΠΆΠ½Π° Π²ΠΈΠ·Π½Π°Ρ‡ΠΈΡ‚ΠΈ, Ρ‡ΠΈ Ρ” Π·Π°Π΄Π°Π½Π° Ρ‚ΠΎΡ‡ΠΊΠ° ΠΊΡ€Π°ΠΉΠ½ΡŒΠΎΡŽ. ΠŸΠΎΠ²Ρ‚ΠΎΡ€Π΅Π½Π½Ρ Ρ†Ρ–Ρ”Ρ— ΠΏΡ€ΠΎΡ†Π΅Π΄ΡƒΡ€ΠΈ для всіх N Ρ‚ΠΎΡ‡ΠΎΠΊ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S Π²ΠΈΠΌΠ°Π³Π°Ρ” часу O (N4).

Π’ΠΎΡ‡ΠΊΠ° P Π½Π΅ Ρ” ΠΊΡ€Π°ΠΉΠ½ΡŒΠΎΡŽ, ΠΎΡΠΊΡ–Π»ΡŒΠΊΠΈ Π²ΠΎΠ½Π° Π»Π΅ΠΆΠΈΡ‚ΡŒ всСрСдині Ρ‚Ρ€ΠΈΠΊΡƒΡ‚Π½ΠΈΠΊΠ° P1P2P3.

Π’Π΅ΠΎΡ€Π΅ΠΌΠ°. ΠŸΡ€ΠΎΠΌΡ–Π½ΡŒ, який Π²ΠΈΡ…ΠΎΠ΄ΠΈΡ‚ΡŒ Ρ–Π· Π²Π½ΡƒΡ‚Ρ€Ρ–ΡˆΠ½ΡŒΠΎΡ— Ρ‚ΠΎΡ‡ΠΊΠΈ ΠΎΠ±ΠΌΠ΅ΠΆΠ΅Π½ΠΎΡ— Π·Π°ΠΌΠΊΠ½Π΅Π½ΠΎΡ— Ρ„Ρ–Π³ΡƒΡ€ΠΈ F, ΠΏΠ΅Ρ€Π΅Ρ‚ΠΈΠ½Π°Ρ” Π³Ρ€Π°Π½ΠΈΡ†ΡŽ F Ρ€Ρ–Π²Π½ΠΎ Π² ΠΎΠ΄Π½Ρ–ΠΉ Ρ‚ΠΎΡ‡Ρ†Ρ–.

Π’Π΅ΠΎΡ€Π΅ΠΌΠ°. ΠŸΠΎΡΠ»Ρ–Π΄ΠΎΠ²Π½Ρ– Π²Π΅Ρ€ΡˆΠΈΠ½ΠΈ ΠΎΠΏΡƒΠΊΠ»ΠΎΠ³ΠΎ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡƒΡ‚Π½ΠΈΠΊΠ° Ρ€ΠΎΠ·Ρ‚Π°ΡˆΠΎΠ²Π°Π½Ρ– Π² ΠΏΠΎΡ€ΡΠ΄ΠΊΡƒ, якому Π²Ρ–Π΄ΠΏΠΎΠ²Ρ–Π΄Π°Ρ” Π·ΠΌΡ–Π½Π° ΠΊΡƒΡ‚Π° відносно Π΄ΠΎΠ²Ρ–Π»ΡŒΠ½ΠΎΡ— Π²Π½ΡƒΡ‚Ρ€Ρ–ΡˆΠ½ΡŒΠΎΡ— Ρ‚ΠΎΡ‡ΠΊΠΈ.

Π’Π΅ΠΎΡ€Π΅ΠΌΠ°. Π’ ΡΠΊΠΎΡΡ‚Ρ– Π²Π½ΡƒΡ‚Ρ€Ρ–ΡˆΠ½ΡŒΠΎΡ— Ρ‚ΠΎΡ‡ΠΊΠΈ q ΠΌΠΎΠΆΠ½Π° взяти Ρ†Π΅Π½Ρ‚Ρ€ΠΎΡ—Π΄ Π΄ΠΎΠ²Ρ–Π»ΡŒΠ½ΠΈΡ… Ρ‚Ρ€ΡŒΠΎΡ… Π½Π΅ΠΊΠΎΠ»Ρ–Π½Π΅Π°Ρ€Π½ΠΈΡ… Ρ‚ΠΎΡ‡ΠΎΠΊ.

Для Ρ†ΡŒΠΎΠ³ΠΎ Π±Π΅Ρ€ΡƒΡ‚ΡŒΡΡ Π΄Π²Ρ– Π΄ΠΎΠ²Ρ–Π»ΡŒΠ½Ρ– Ρ‚ΠΎΡ‡ΠΊΠΈ Ρ‚Π° ΡˆΡƒΠΊΠ°Ρ”Ρ‚ΡŒΡΡ Ρ‚Π°ΠΊΠ° трСтя Ρ‚ΠΎΡ‡ΠΊΠ° Π· Ρ–Π½ΡˆΠΈΡ… N — 2 Ρ‚ΠΎΡ‡ΠΎΠΊ, яка Π½Π΅ Π»Π΅ΠΆΠΈΡ‚ΡŒ Π½Π° ΠΏΡ€ΡΠΌΡ–ΠΉ, Ρ‰ΠΎ Π²ΠΈΠ·Π½Π°Ρ‡Π°Ρ”Ρ‚ΡŒΡΡ ΠΏΠ΅Ρ€ΡˆΠΈΠΌΠΈ Π΄Π²ΠΎΠΌΠ°.

Π—Π°Π΄Π°Ρ‡Π°. На ΠΏΠ»ΠΎΡ‰ΠΈΠ½Ρ– Π΄Π°Π½ΠΎ Π΄Π²Ρ– Ρ‚ΠΎΡ‡ΠΊΠΈ p1 Ρ‚Π° p2. Π―ΠΊΠ° Π· Ρ†ΠΈΡ… Ρ‚ΠΎΡ‡ΠΎΠΊ ΠΌΠ°Ρ” Π±Ρ–Π»ΡŒΡˆΠΈΠΉ полярний ΠΊΡƒΡ‚?

p2 ΡƒΡ‚Π²ΠΎΡ€ΡŽΡ” Π· Π²Ρ–ΡΡΡŽ ΠžΡ… ΡΡ‚Ρ€ΠΎΠ³ΠΎ мСнший полярний ΠΊΡƒΡ‚, Π½Ρ–ΠΆ p1 Ρ‚ΠΎΠ΄Ρ– Ρ– Ρ‚Ρ–Π»ΡŒΠΊΠΈ Ρ‚ΠΎΠ΄Ρ–, ΠΊΠΎΠ»ΠΈ Ρ‚Ρ€ΠΈΠΊΡƒΡ‚Π½ΠΈΠΊ (O, p2, p1) ΠΌΠ°Ρ” строго Π΄ΠΎΠ΄Π°Ρ‚Π½ΡŽ ΠΏΠ»ΠΎΡ‰Ρƒ (Π°Π±ΠΎ Ρ‚ΠΎΡ‡ΠΊΠ° P1 Π»Π΅ΠΆΠΈΡ‚ΡŒ Π·Π»Ρ–Π²Π° Π²Ρ–Π΄ прямої OP2).

ΠŸΡ€ΠΈΠΊΠ»Π°Π΄. ΠŸΠ»ΠΎΡ‰Π° Ρ‚Ρ€ΠΈΠΊΡƒΡ‚Π½ΠΈΠΊΠ° OP2P1 Π΄ΠΎΡ€Ρ–Π²Π½ΡŽΡ” Π… * P2 = Π… * | 6 2 3 5 | = Π… * (30 — 6) = 12.

ΠœΠ΅Ρ‚ΠΎΠ΄ ΠΎΠ±Ρ…ΠΎΠ΄Π° Π“Ρ€Π΅Ρ…Π΅ΠΌΠ° Π—Π½Π°ΠΉΠ΄Π΅ΠΌΠΎ Π²Π½ΡƒΡ‚Ρ€Ρ–ΡˆΠ½ΡŽ Ρ‚ΠΎΡ‡ΠΊΡƒ O ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ Ρ‚ΠΎΡ‡ΠΎΠΊ S Ρ‚Π° ΠΏΠ΅Ρ€Π΅Ρ‚Π²ΠΎΡ€ΠΈΠΌΠΎ ΠΊΠΎΠΎΡ€Π΄ΠΈΠ½Π°Ρ‚ΠΈ Ρ–Π½ΡˆΠΈΡ… Ρ‚ΠΎΡ‡ΠΎΠΊ Ρ‚Π°ΠΊ, Ρ‰ΠΎΠ± Π·Π½Π°ΠΉΠ΄Π΅Π½Π° Π²Π½ΡƒΡ‚Ρ€Ρ–ΡˆΠ½Ρ Ρ‚ΠΎΡ‡ΠΊΠ° стала ΠΏΠΎΡ‡Π°Ρ‚ΠΊΠΎΠΌ ΠΊΠΎΠΎΡ€Π΄ΠΈΠ½Π°Ρ‚. Впорядкуємо лСксикографічно N Ρ‚ΠΎΡ‡ΠΎΠΊ Ρƒ відповідності Π·Ρ– значСннями полярного ΠΊΡƒΡ‚Π° Ρ‚Π° відстані Π²Ρ–Π΄ ΠΏΠΎΡ‡Π°Ρ‚ΠΊΡƒ ΠΊΠΎΠΎΡ€Π΄ΠΈΠ½Π°Ρ‚ (ΠΏΡ€ΠΈ Ρ†ΡŒΠΎΠΌΡƒ ΠΏΠ΅Ρ€Π΅Π²ΠΎΠ΄ΠΈΡ‚ΠΈ ΠΊΠΎΠΎΡ€Π΄ΠΈΠ½Π°Ρ‚ΠΈ Ρ‚ΠΎΡ‡ΠΎΠΊ Π΄ΠΎ ΠΏΠΎΠ»ΡΡ€Π½ΠΎΡ— систСми ΠΊΠΎΠΎΡ€Π΄ΠΈΠ½Π°Ρ‚ Π½Π΅ Ρ‚Ρ€Π΅Π±Π°).

Алгоритм Π“Ρ€Π΅Ρ…Π΅ΠΌΠ° полягає Π² ΠΎΠ΄Π½ΠΎΠΊΡ€Π°Ρ‚Π½ΠΎΠΌΡƒ пСрСгляді впорядкованої послідовності Ρ‚ΠΎΡ‡ΠΎΠΊ, Π² ΠΏΡ€ΠΎΡ†Π΅ΡΡ– якої Π²ΠΈΠ΄Π°Π»ΡΡŽΡ‚ΡŒΡΡ Π²Π½ΡƒΡ‚Ρ€Ρ–ΡˆΠ½Ρ– Ρ‚ΠΎΡ‡ΠΊΠΈ. ΠŸΠ΅Ρ€Π΅Π³Π»ΡΠ΄ ΠΏΠΎΡ‡ΠΈΠ½Π°Ρ”Ρ‚ΡŒΡΡ Π· Ρ‚ΠΎΡ‡ΠΊΠΈ p0, Π² ΡΠΊΠΎΡΡ‚Ρ– якої ΠΌΠΎΠΆΠ½Π° взяти саму ΠΏΡ€Π°Π²Ρƒ (Π· ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΡŽ Π°Π±ΡΡ†ΠΈΡΠΎΡŽ) Π· Π½Π°ΠΉΠΌΠ΅Π½ΡˆΠΎΡŽ ΠΎΡ€Π΄ΠΈΠ½Π°Ρ‚ΠΎΡŽ (Π²ΠΎΠ½Π° Ρ‚ΠΎΡ‡Π½ΠΎ Π½Π°Π»Π΅ΠΆΠΈΡ‚ΡŒ ΠΎΠΏΡƒΠΊΠ»Ρ–ΠΉ ΠΎΠ±ΠΎΠ»ΠΎΠ½Ρ†Ρ–). ΠŸΠΎΡΠ»Ρ–Π΄ΠΎΠ²Π½ΠΎ ΠΏΠ΅Ρ€Π΅Π²Ρ–Ρ€ΡΡŽΡ‚ΡŒΡΡ Ρ‚Ρ€Ρ–ΠΉΠΊΠΈ Ρ‚ΠΎΡ‡ΠΎΠΊ p1p2p3, ΠΏΡ€ΠΈ Ρ‡ΠΎΠΌΡƒ.

1. Π―ΠΊΡ‰ΠΎ Ρ‚Ρ€Ρ–ΠΉΠΊΠ° p1p2p3 ΡƒΡ‚Π²ΠΎΡ€ΡŽΡ” ΠΏΡ€Π°Π²ΠΈΠΉ ΠΏΠΎΠ²ΠΎΡ€ΠΎΡ‚, Ρ‚ΠΎ Π²ΠΈΠ΄Π°Π»ΠΈΡ‚ΠΈ Π²Π΅Ρ€ΡˆΠΈΠ½Ρƒ p2 Ρ‚Π° ΠΏΠ΅Ρ€Π΅Π²Ρ–Ρ€ΠΈΡ‚ΠΈ Ρ‚Ρ€Ρ–ΠΉΠΊΡƒ p0p1p3.

2. Π―ΠΊΡ‰ΠΎ Ρ‚Ρ€Ρ–ΠΉΠΊΠ° p1p2p3 ΡƒΡ‚Π²ΠΎΡ€ΡŽΡ” Π»Ρ–Π²ΠΈΠΉ ΠΏΠΎΠ²ΠΎΡ€ΠΎΡ‚, Ρ‚ΠΎ ΠΏΡ€ΠΎΠ΄ΠΎΠ²ΠΆΡƒΠ²Π°Ρ‚ΠΈ пСрСгляд, ΠΏΠ΅Ρ€Π΅ΠΉΡˆΠΎΠ²ΡˆΠΈ Π΄ΠΎ Ρ‚Ρ€Ρ–ΠΉΠΊΠΈ p2p3p4.

Оболонка Π“Ρ€Π΅Ρ…Π΅ΠΌΠ°.

1. Π—Π½Π°ΠΉΡ‚ΠΈ Π²Π½ΡƒΡ‚Ρ€Ρ–ΡˆΠ½ΡŽ Ρ‚ΠΎΡ‡ΠΊΡƒ q.

2. Π’ΠΈΠΊΠΎΡ€ΠΈΡΡ‚ΠΎΠ²ΡƒΡŽΡ‡ΠΈ q ΡΠΊ ΠΏΠΎΡ‡Π°Ρ‚ΠΎΠΊ ΠΊΠΎΠΎΡ€Π΄ΠΈΠ½Π°Ρ‚, впорядкувати лСксикографічно Ρ‚ΠΎΡ‡ΠΊΠΈ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S Ρƒ відповідності Π· ΠΏΠΎΠ»ΡΡ€Π½ΠΈΠΌ ΠΊΡƒΡ‚ΠΎΠΌ Ρ‚Π° Π²Ρ–Π΄ΡΡ‚Π°Π½Π½ΡŽ Π²Ρ–Π΄ q. ΠžΡ€Π³Π°Π½Ρ–Π·ΡƒΠ²Π°Ρ‚ΠΈ Ρ‚ΠΎΡ‡ΠΊΠΈ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ Ρƒ Π²ΠΈΠ³Π»ΡΠ΄Ρ– ΠΊΡ–Π»ΡŒΡ†Π΅Π²ΠΎΠ³ΠΎ списку Ρ–Π· Π²ΠΊΠ°Π·Ρ–Π²Π½ΠΈΠΊΠ°ΠΌΠΈ NEXT, PREV Ρ‚Π° Π²ΠΊΠ°Π·Ρ–Π²Π½ΠΈΠΊΠΎΠΌ ПОЧАВОК Π½Π° ΠΏΠ΅Ρ€ΡˆΡƒ Π²Π΅Ρ€ΡˆΠΈΠ½Ρƒ. ЗначСння TRUE Π»ΠΎΠ³Ρ–Ρ‡Π½ΠΎΡ— Π·ΠΌΡ–Π½Π½ΠΎΡ— f Π²ΠΊΠ°Π·ΡƒΡ” Π½Π° Ρ‚Π΅, Ρ‰ΠΎ Π²Π΅Ρ€ΡˆΠΈΠ½Π° ПОЧАВОК досягнута ΠΏΡ€ΠΈ прямому русі ΠΏΠΎ ΠΎΠ±ΠΎΠ»ΠΎΠ½Ρ†Ρ–, Π° Π½Π΅ Π² Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Ρ– повСртання.

3. ΠžΠ±Ρ…Ρ–Π΄.

begin.

v ΠŸΠžΠ§ΠΠ’ОКw NEXT[v]- f FALSE;

while (NEXT[v] ПОЧАВОК or f = FALSE) do.

begin.

if NEXT[v] = w then f E;

if (Ρ‚Ρ€ΠΈ Ρ‚ΠΎΡ‡ΠΊΠΈ v, NEXT[v], NEXT[NEXT[v]] ΡƒΡ‚Π²ΠΎΡ€ΡŽΡŽΡ‚ΡŒ Π»Ρ–Π²ΠΈΠΉ ΠΏΠΎΠ²ΠΎΡ€ΠΎΡ‚) then v NEXT[v];

else.

begin.

Π’Π˜Π”ΠΠ›Π˜Π’Π˜ NEXT[v];

v PREV[v];

end;

end;

end.

Π’Π΅ΠΎΡ€Π΅ΠΌΠ°. ΠžΠΏΡƒΠΊΠ»Π° ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠ° N Ρ‚ΠΎΡ‡ΠΎΠΊ Π½Π° ΠΏΠ»ΠΎΡ‰ΠΈΠ½Ρ– ΠΌΠΎΠΆΠ΅ Π±ΡƒΡ‚ΠΈ Π·Π½Π°ΠΉΠ΄Π΅Π½Π° Π·Π° Ρ‡Π°Ρ O (N * logN) ΠΏΡ€ΠΈ Π²ΠΈΡ‚Ρ€Π°Ρ‚Π°Ρ… ΠΏΠ°ΠΌ’яті O (N).

ΠœΠ΅Ρ‚ΠΎΠ΄ ΠΎΠ±Ρ…ΠΎΠ΄Π° ДТарвіса Π’Π΅ΠΎΡ€Π΅ΠΌΠ°. Π’Ρ–Π΄Ρ€Ρ–Π·ΠΎΠΊ l Ρ” Ρ€Π΅Π±Ρ€ΠΎΠΌ ΠΎΠΏΡƒΠΊΠ»ΠΎΡ— ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ Ρ‚ΠΎΠ΄Ρ– Ρ– Ρ‚Ρ–Π»ΡŒΠΊΠΈ Ρ‚ΠΎΠ΄Ρ–, ΠΊΠΎΠ»ΠΈ всі Ρ–Π½ΡˆΡ– Ρ‚ΠΎΡ‡ΠΊΠΈ Π·Π°Π΄Π°Π½ΠΎΡ— ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ Π»Π΅ΠΆΠ°Ρ‚ΡŒ Π½Π° l Π°Π±ΠΎ Π· ΠΎΠ΄Π½ΠΎΡ— сторони Π²Ρ–Π΄ нього.

N Ρ‚ΠΎΡ‡ΠΎΠΊ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S Π²ΠΈΠ·Π½Π°Ρ‡Π°ΡŽΡ‚ΡŒ C n 2 прямих. Для ΠΊΠΎΠΆΠ½ΠΎΡ— Ρ†Ρ–Ρ”Ρ— прямої ΠΌΠΎΠΆΠ½Π° Π²ΠΈΠ·Π½Π°Ρ‡ΠΈΡ‚ΠΈ Π·Π° Π»Ρ–Π½Ρ–ΠΉΠ½ΠΈΠΉ час Ρ€ΠΎΠ·Ρ‚Π°ΡˆΡƒΠ²Π°Π½Π½Ρ Ρ–Π½ΡˆΠΈΡ… N-2 Ρ‚ΠΎΡ‡ΠΎΠΊ відносно Ρ†Ρ–Ρ”Ρ— прямої, Ρ‚ΠΈΠΌ самим ΠΏΠ΅Ρ€Π΅Π²Ρ–Ρ€ΠΈΠ²ΡˆΠΈ Ρ‡ΠΈ Π·Π°Π΄ΠΎΠ²Ρ–Π»ΡŒΠ½ΡΡ” пряма ΡƒΠΌΠΎΠ²Ρ– Ρ‚Π΅ΠΎΡ€Π΅ΠΌΠΈ. Π—Π° Ρ‡Π°Ρ O (N3) ΠΌΠΎΠΆΠ½Π° Π·Π½Π°ΠΉΡ‚ΠΈ всі ΠΏΠ°Ρ€ΠΈ Ρ‚ΠΎΡ‡ΠΎΠΊ, Ρ‰ΠΎ Π²ΠΈΠ·Π½Π°Ρ‡Π°ΡŽΡ‚ΡŒ Ρ€Π΅Π±Ρ€Π° ΠΎΠΏΡƒΠΊΠ»ΠΎΡ— ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ Ρ‚Π° Ρ€ΠΎΠ·Ρ‚Π°ΡˆΡƒΠ²Π°Ρ‚ΠΈ Ρ†Ρ– Ρ‚ΠΎΡ‡ΠΊΠΈ Ρƒ Π²ΠΈΠ³Π»ΡΠ΄Ρ– списку послідовних Π²Π΅Ρ€ΡˆΠΈΠ½ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ.

ДТарвіс ΠΏΠΎΠΊΡ€Π°Ρ‰ΠΈΠ² Ρ†Π΅ΠΉ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ ΠΏΠΎΠΌΡ–Ρ‚ΠΈΠ²ΡˆΠΈ, Ρ‰ΠΎ ΡΠΊΡ‰ΠΎ Π²Ρ–Π΄Ρ€Ρ–Π·ΠΎΠΊ pq Ρ” Ρ€Π΅Π±Ρ€ΠΎΠΌ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ, Ρ‚ΠΎ ΠΏΠΎΠ²ΠΈΠ½Π½ΠΎ існувати Ρ–Π½ΡˆΠ΅ Ρ€Π΅Π±Ρ€ΠΎ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ Π· ΠΊΡ–Π½Ρ†Π΅ΠΌ Π² Ρ‚ΠΎΡ‡Ρ†Ρ– q. НСхай Π·Π½Π°ΠΉΠ΄Π΅Π½ΠΎ Ρ‚ΠΎΡ‡ΠΊΡƒ p1, яка Π½Π°Π»Π΅ΠΆΠΈΡ‚ΡŒ ΠΎΠΏΡƒΠΊΠ»Ρ–ΠΉ ΠΎΠ±ΠΎΠ»ΠΎΠ½Ρ†Ρ– (яка, Π½Π°ΠΏΡ€ΠΈΠΊΠ»Π°Π΄, ΠΌΠ°Ρ” ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡŒΠ½Ρƒ Ρ… ΠΊΠΎΠΎΡ€Π΄ΠΈΠ½Π°Ρ‚ΡƒΠ° якщо Ρ‚Π°ΠΊΠΈΡ… Ρ‚ΠΎΡ‡ΠΎΠΊ Π΄Π΅ΠΊΡ–Π»ΡŒΠΊΠ° — Ρ‚ΠΎ ΡΠ΅Ρ€Π΅Π΄ Π½ΠΈΡ… взяти Ρ‚ΠΎΡ‡ΠΊΡƒ Π· ΠΌΡ–Π½Ρ–ΠΌΠ°Π»ΡŒΠ½ΠΎΡŽ Ρƒ ΠΊΠΎΠΎΡ€Π΄ΠΈΠ½Π°Ρ‚ΠΎΡŽ). Наступна Ρ‚ΠΎΡ‡ΠΊΠ° p2 ΠΎΠΏΡƒΠΊΠ»ΠΎΡ— ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ — Ρ†Π΅ Ρ‚ΠΎΡ‡ΠΊΠ°, яка ΠΌΠ°Ρ” наймСнший Π΄ΠΎΠ΄Π°Ρ‚Π½ΠΈΠΉ полярний ΠΊΡƒΡ‚ відносно Ρ‚ΠΎΡ‡ΠΊΠΈ p1 як ΠΏΠΎΡ‡Π°Ρ‚ΠΊΡƒ ΠΊΠΎΠΎΡ€Π΄ΠΈΠ½Π°Ρ‚. Π† Ρ‚Π°ΠΊ Π΄Π°Π»Ρ– ΡˆΡƒΠΊΠ°ΡŽΡ‚ΡŒΡΡ наступні Ρ‚ΠΎΡ‡ΠΊΠΈ ΡˆΠ»ΡΡ…ΠΎΠΌ ΠΏΡ€ΠΎΡ…ΠΎΠ΄Ρƒ Π²ΠΊΡ€ΡƒΠ³ΠΎΠ²Ρƒ ΠΎΠΏΡƒΠΊΠ»ΠΎΡ— ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ, ΠΏΠΎΡ€ΠΎΠ΄ΠΆΡƒΡŽΡ‡ΠΈ Ρƒ ΠΏΠΎΡ‚Ρ€Ρ–Π±Π½ΠΎΠΌΡƒ порядку ΠΏΠΎΡΠ»Ρ–Π΄ΠΎΠ²Π½Ρ–ΡΡ‚ΡŒ ΠΊΡ€Π°ΠΉΠ½Ρ–Ρ… Ρ‚ΠΎΡ‡ΠΎΠΊ, ΠΏΠΎ ΠΎΠ΄Π½Ρ–ΠΉ Π½Π° ΠΊΠΎΠΆΠ½ΠΎΠΌΡƒ ΠΊΡ€ΠΎΡ†Ρ–.

ΠžΠ±Ρ…Ρ–Π΄ ДТарвіса.

p[1] Ρ‚ΠΎΡ‡ΠΊΠ° Π· Π½Π°ΠΉΠΌΠ΅Π½ΡˆΠΎΡŽ y ΠΊΠΎΠΎΡ€Π΄ΠΈΠ½Π°Ρ‚ΠΎΡŽ;

p[2] Ρ‚ΠΎΡ‡ΠΊΠ° Π· ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S, для якої ΠΊΡƒΡ‚ ΠΌΡ–ΠΆ ΠΏΡ€ΡΠΌΠΎΡŽ p[2] - p[1] Ρ‚Π° Π²Ρ–ΡΡΡŽ Ox Π½Π°ΠΉΠΌΠ΅Π½ΡˆΠΈΠΉ;

print (p[1], p[2]);

i 2;

while (p[i] p[1]) do.

begin.

p[i + 1] Ρ‚ΠΎΡ‡ΠΊΠ° Π· ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S, для якої ΠΊΡƒΡ‚ p[i — 1] p[i] p[i + 1] Ρ” Π½Π°ΠΉΠ±Ρ–Π»ΡŒΡˆΠΈΠΌ;

i i + 1;

print (p[i]);

end.

Π’Π΅ΠΎΡ€Π΅ΠΌΠ°. Часова ΠΎΡ†Ρ–Π½ΠΊΠ° ΠΎΠ±Ρ…ΠΎΠ΄Ρƒ ДТарвіса Π΄ΠΎΡ€Ρ–Π²Π½ΡŽΡ” O (N2).

ΠžΡΠΊΡ–Π»ΡŒΠΊΠΈ всі N Ρ‚ΠΎΡ‡ΠΎΠΊ ΠΌΠΎΠΆΡƒΡ‚ΡŒ Π»Π΅ΠΆΠ°Ρ‚ΠΈ Π½Π° ΠΎΠΏΡƒΠΊΠ»Ρ–ΠΉ ΠΎΠ±ΠΎΠ»ΠΎΠ½Ρ†Ρ–, Π° Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ ДТарвіса Π²ΠΈΠΌΠ°Π³Π°Ρ” Π»Ρ–Π½Ρ–ΠΉΠ½ΠΈΠΉ час для знаходТСння ΠΊΠΎΠΆΠ½ΠΎΡ— наступної Ρ‚ΠΎΡ‡ΠΊΠΈ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ, Ρ‚ΠΎ Π² Π½Π°ΠΉΠ³Ρ–Ρ€ΡˆΠΎΠΌΡƒ Π²ΠΈΠΏΠ°Π΄ΠΊΡƒ часова ΠΎΡ†Ρ–Π½ΠΊΠ° Π΄ΠΎΡ€Ρ–Π²Π½ΡŽΡ” O (N2). ΠžΠ±Ρ…Ρ–Π΄ ДТарвіса Ρ” Π΅Ρ„Π΅ΠΊΡ‚ΠΈΠ²Π½ΠΈΠΌ, якщо ΠΊΡ–Π»ΡŒΠΊΡ–ΡΡ‚ΡŒ Π²Π΅Ρ€ΡˆΠΈΠ½ ΠΎΠΏΡƒΠΊΠ»ΠΎΡ— ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ h Ρ” малою Ρƒ ΠΏΠΎΡ€Ρ–внянні Π·Ρ– значСнням N — часова ΠΎΡ†Ρ–Π½ΠΊΠ° Ρƒ Ρ†ΡŒΠΎΠΌΡƒ Π²ΠΈΠΏΠ°Π΄ΠΊΡƒ Π΄ΠΎΡ€Ρ–Π²Π½ΡŽΠ²Π°Ρ‚ΠΈΠΌΠ΅ O (N * h).

Алгоритм апроксимації ΠΎΠΏΡƒΠΊΠ»ΠΎΡ— ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ ΠŸΡ€ΠΈ Π·Π½Π°Ρ…ΠΎΠ΄ΠΆΠ΅Π½Π½Ρ– Π½Π°Π±Π»ΠΈΠΆΠ΅Π½ΠΎΡ— ΠΎΠΏΡƒΠΊΠ»ΠΎΡ— ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ ΠΌΠΈ Ρ€ΠΎΠ·ΠΌΡ–Π½ΡŽΡ”ΠΌΠΎ Ρ‚ΠΎΡ‡Π½Ρ–ΡΡ‚ΡŒ Π½Π° ΠΏΡ€ΠΎΡΡ‚ΠΎΡ‚Ρƒ Ρ‚Π° Π΅Ρ„Π΅ΠΊΡ‚ΠΈΠ²Π½Ρ–ΡΡ‚ΡŒ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡƒ.

Π—Π½Π°ΠΉΠ΄Π΅ΠΌΠΎ ΠΌΡ–Π½Ρ–ΠΌΠ°Π»ΡŒΠ½Π΅ Ρ‚Π° ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡŒΠ½Π΅ значСння Ρ… ΠΊΠΎΠΎΡ€Π΄ΠΈΠ½Π°Ρ‚ΠΈ Ρ‚ΠΎΡ‡ΠΎΠΊ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S Ρ‚Π° Ρ€ΠΎΠ·Ρ–Π±'Ρ”ΠΌΠΎ Π²Π΅Ρ€Ρ‚ΠΈΠΊΠ°Π»ΡŒΠ½Ρƒ полосу ΠΌΡ–ΠΆ Π½ΠΈΠΌΠΈ Π½Π° k ΠΏΠΎΠ»ΠΎΡ Ρ€Ρ–Π²Π½ΠΎΡ— ΡˆΠΈΡ€ΠΈΠ½ΠΈ. Π’ ΠΊΠΎΠΆΠ½Ρ–ΠΉ Ρ–Π· Ρ†ΠΈΡ… k ΠΏΠΎΠ»ΠΎΡ ΡˆΡƒΠΊΠ°ΡŽΡ‚ΡŒΡΡ Π΄Π²Ρ– Ρ‚ΠΎΡ‡ΠΊΠΈ, які ΠΌΠ°ΡŽΡ‚ΡŒ ΠΌΡ–Π½Ρ–ΠΌΠ°Π»ΡŒΠ½Ρƒ Ρ‚Π° ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡŒΠ½Ρƒ Ρƒ ΠΊΠΎΠΎΡ€Π΄ΠΈΠ½Π°Ρ‚Ρƒ (ΠΎΠ±ΠΈΡ€Π°Ρ”Ρ‚ΡŒΡΡ 2k Ρ‚ΠΎΡ‡ΠΎΠΊ). ΠžΠ±ΠΈΡ€Π°ΡŽΡ‚ΡŒΡΡ Ρ‚Π°ΠΊΠΎΠΆ Ρ‚ΠΎΡ‡ΠΊΠΈ Π· Π΅ΠΊΡΡ‚Ρ€Π΅ΠΌΠ°Π»ΡŒΠ½ΠΈΠΌΠΈ значСннями Ρ… ΠΊΠΎΠΎΡ€Π΄ΠΈΠ½Π°Ρ‚иякщо Ρ—Ρ… Π΄Π΅ΠΊΡ–Π»ΡŒΠΊΠ°, Ρ‚ΠΎ ΠΎΠ±ΠΈΡ€Π°ΡŽΡ‚ΡŒΡΡ Π΄Π²Ρ– Ρ‚ΠΎΡ‡ΠΊΠΈ Π· Π΅ΠΊΡΡ‚Ρ€Π΅ΠΌΠ°Π»ΡŒΠ½ΠΈΠΌΠΈ значСннями Ρƒ ΠΊΠΎΠΎΡ€Π΄ΠΈΠ½Π°Ρ‚ΠΈ (максимум ΠΎΠ±ΠΈΡ€Π°Ρ”Ρ‚ΡŒΡΡ 4 Ρ‚ΠΎΡ‡ΠΊΠΈ). ΠžΠ±Ρ€Π°Π½Π° ΠΌΠ½ΠΎΠΆΠΈΠ½Π° ΠΌΡ–ΡΡ‚ΠΈΡ‚ΡŒ Π½Π΅ Π±Ρ–Π»ΡŒΡˆ Π½Ρ–ΠΆ 2k + 4 Ρ‚ΠΎΡ‡ΠΎΠΊ Ρ– ΠΏΠΎΠ·Π½Π°Ρ‡ΠΈΠΌΠΎ Ρ—Ρ— Ρ‡Π΅Ρ€Π΅Π· S*. Π”Π°Π»Ρ– ΠΌΠΎΠΆΠ½Π° застосувати Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ Π“Ρ€Π΅Ρ…Π΅ΠΌΠ° ΠΏΠΎΠ±ΡƒΠ΄ΠΎΠ²ΠΈ ΠΎΠΏΡƒΠΊΠ»ΠΎΡ— ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ для ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ Ρ‚ΠΎΡ‡ΠΎΠΊ S*.

ΠŸΡ€ΠΈΠΊΠ»Π°Π΄. ΠœΠ½ΠΎΠΆΠΈΠ½Ρƒ Ρ‚ΠΎΡ‡ΠΎΠΊ S Ρ€ΠΎΠ·Π±ΠΈΡ‚ΠΎ Π½Π° k = 4 полоси. Π’ ΠΊΠΎΠΆΠ½Ρ–ΠΉ полосі ΠΎΠ±Ρ€Π°Π½ΠΎ Π΄Π²Ρ– Ρ‚ΠΎΡ‡ΠΊΠΈ. Для ΡƒΡ‚Π²ΠΎΡ€Π΅Π½ΠΎΡ— ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S* ΠΏΠΎΠ±ΡƒΠ΄ΠΎΠ²Π°Π½ΠΎ ΠΎΠΏΡƒΠΊΠ»Ρƒ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΡƒ.

Π’Π΅ΠΎΡ€Π΅ΠΌΠ°. Π”ΠΎΠ²Ρ–Π»ΡŒΠ½Π° Ρ‚ΠΎΡ‡ΠΊΠ° p S, яка Π½Π΅ ΠΏΠΎΠΏΠ°Π»Π° всСрСдину Π½Π°Π±Π»ΠΈΠΆΠ΅Π½ΠΎΡ— ΠΎΠΏΡƒΠΊΠ»ΠΎΡ— ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ, Π·Π½Π°Ρ…ΠΎΠ΄ΠΈΡ‚ΡŒΡΡ Π½Π° відстані, Π½Π΅ Π±Ρ–Π»ΡŒΡˆΠΎΡ— Π·Π° Π·Π½Π°Ρ‡Π΅Π½Π½Ρ (xmax — xmin) / k.

Π¨Π²ΠΈΠ΄ΠΊΡ– ΠΌΠ΅Ρ‚ΠΎΠ΄ΠΈ ΠΏΠΎΠ±ΡƒΠ΄ΠΎΠ²ΠΈ ΠΎΠΏΡƒΠΊΠ»ΠΎΡ— ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ Π ΠΎΠ·Ρ–Π±'Ρ”ΠΌΠΎ ΠΌΠ½ΠΎΠΆΠΈΠ½Ρƒ S Π· N Ρ‚ΠΎΡ‡ΠΎΠΊ Π½Π° Π΄Π²Ρ– ΠΏΡ–Π΄ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ, ΠΊΠΎΠΆΠ½Π° Π· ΡΠΊΠΈΡ… Π±ΡƒΠ΄Π΅ містити ΠΎΠ΄Π½Ρƒ Π· Π΄Π²ΠΎΡ… Π»Π°ΠΌΠ°Π½ΠΈΡ…, ΠΎΠ±'єднання яких Π΄Π°Ρ” ΠΌΠ½ΠΎΠ³ΠΎΠΊΡƒΡ‚Π½ΠΈΠΊ ΠΎΠΏΡƒΠΊΠ»ΠΎΡ— ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ. ΠŸΠΎΡ‡Π°Ρ‚ΠΊΠΎΠ²Π΅ розбиття ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ Ρ‚ΠΎΡ‡ΠΎΠΊ Π²ΠΈΠ·Π½Π°Ρ‡Π°Ρ”Ρ‚ΡŒΡΡ ΠΏΡ€ΡΠΌΠΎΡŽ, Ρ‰ΠΎ ΠΏΡ€ΠΎΡ…ΠΎΠ΄ΠΈΡ‚ΡŒ Ρ‡Π΅Ρ€Π΅Π· Π΄Π²Ρ– Ρ‚ΠΎΡ‡ΠΊΠΈ l Ρ‚Π° r, які ΠΌΠ°ΡŽΡ‚ΡŒ Π²Ρ–Π΄ΠΏΠΎΠ²Ρ–Π΄Π½ΠΎ Π½Π°ΠΉΠΌΠ΅Π½ΡˆΡƒ Ρ‚Π° Π½Π°ΠΉΠ±Ρ–Π»ΡŒΡˆΡƒ абсцису. ΠŸΠΎΠ·Π½Π°Ρ‡ΠΈΠΌΠΎ Ρ‡Π΅Ρ€Π΅Π· S1 ΠΏΡ–Π΄ΠΌΠ½ΠΎΠΆΠΈΠ½Ρƒ Ρ‚ΠΎΡ‡ΠΎΠΊ, яка Ρ€ΠΎΠ·Ρ‚Π°ΡˆΠΎΠ²Π°Π½Π° Π²ΠΈΡ‰Π΅ Π°Π±ΠΎ Π½Π° ΠΏΡ€ΡΠΌΡ–ΠΉ, Π° Ρ‡Π΅Ρ€Π΅Π· S2 — ΠΏΡ–Π΄ΠΌΠ½ΠΎΠΆΠΈΠ½Ρƒ Ρ‚ΠΎΡ‡ΠΎΠΊ, яка Ρ€ΠΎΠ·Ρ‚Π°ΡˆΠΎΠ²Π°Π½Π° Π½ΠΈΠΆΡ‡Π΅ Π°Π±ΠΎ Π½Π° ΠΏΡ€ΡΠΌΡ–ΠΉ. Π―ΠΊΡ‰ΠΎ Π±ΡƒΡ‚ΠΈ Ρ‚ΠΎΡ‡Π½ΠΈΠΌ, Ρ‚ΠΎ {S1, S2} Π½Π΅ Ρ” розбиттям ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S, ΠΎΡΠΊΡ–Π»ΡŒΠΊΠΈ {l, r} S1 S2. Π”Π°Π»Ρ– ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S1 Ρ‚Π° S2 ΠΎΠ±Ρ€ΠΎΠ±Π»ΡΡŽΡ‚ΡŒΡΡ наступним Ρ‡ΠΈΠ½ΠΎΠΌ (розглянСмо Π½Π° ΠΏΡ€ΠΈΠΊΠ»Π°Π΄Ρ– ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S1).

Π—Π½Π°ΠΉΠ΄Π΅ΠΌΠΎ Ρ‚ΠΎΡ‡ΠΊΡƒ h, для якої Ρ‚Ρ€ΠΈΠΊΡƒΡ‚Π½ΠΈΠΊ lhr ΠΌΠ°Ρ” ΠΌΠ°ΠΊΡΠΈΠΌΠ°Π»ΡŒΠ½Ρƒ ΠΏΠ»ΠΎΡ‰Ρƒ сСрСд усіх Ρ–Π½ΡˆΠΈΡ… Ρ‚Ρ€ΠΈΠΊΡƒΡ‚Π½ΠΈΠΊΡ–Π² (якщо Ρ‚Π°ΠΊΠΈΡ… Ρ‚ΠΎΡ‡ΠΎΠΊ Π΄Π΅ΠΊΡ–Π»ΡŒΠΊΠ°, Ρ‚ΠΎ ΠΎΠ±ΠΈΡ€Π°Ρ”ΠΌΠΎ Ρ‚Ρƒ, Π² ΡΠΊΡ–ΠΉ ΠΊΡƒΡ‚ hlr Π±Ρ–Π»ΡŒΡˆΠΈΠΉ). Π’ΠΎΡ‡ΠΊΠ° h Π³Π°Ρ€Π°Π½Ρ‚ΠΎΠ²Π°Π½ΠΎ Π½Π°Π»Π΅ΠΆΠΈΡ‚ΡŒ ΠΎΠΏΡƒΠΊΠ»Ρ–ΠΉ ΠΎΠ±ΠΎΠ»ΠΎΠ½Ρ†Ρ–. Π―ΠΊΡ‰ΠΎ провСсти Ρ‡Π΅Ρ€Π΅Π· h ΠΏΡ€ΡΠΌΡƒ, ΠΏΠ°Ρ€Π°Π»Π΅Π»ΡŒΠ½Ρƒ lr, Ρ‚ΠΎ Π½Π°Π΄ Π½Ρ–ΠΉ Π½Π΅ Π±ΡƒΠ΄Π΅ ΠΆΠΎΠ΄Π½ΠΎΡ— Ρ‚ΠΎΡ‡ΠΊΠΈ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S. Π―ΠΊΡ‰ΠΎ Π½Π° Ρ†Ρ–ΠΉ прямій Π»Π΅ΠΆΠ°Ρ‚ΡŒ Π΄Π΅ΠΊΡ–Π»ΡŒΠΊΠ° Ρ‚ΠΎΡ‡ΠΎΠΊ, Ρ‚ΠΎ Π·Π³Ρ–Π΄Π½ΠΎ Π· ΠΏΡ€ΠΈΠΏΡƒΡ‰Π΅Π½Π½ΡΠΌ Ρ‚ΠΎΡ‡ΠΊΠ° h Π±ΡƒΠ΄Π΅ самою Π»Ρ–Π²ΠΎΡŽ Π· Π½ΠΈΡ….

Π‘ΡƒΠ΄ΡƒΡ”ΠΌΠΎ Π΄Π²Ρ– прямі: L1 (сполучає Ρ‚ΠΎΡ‡ΠΊΠΈ l Ρ‚Π° h) Ρ‚Π° L2 (ΠΏΡ€ΠΎΡ…ΠΎΠ΄ΠΈΡ‚ΡŒ Ρ‡Π΅Ρ€Π΅Π· Ρ‚ΠΎΡ‡ΠΊΠΈ h Ρ‚Π° r). Для ΠΊΠΎΠΆΠ½ΠΎΡ— Ρ‚ΠΎΡ‡ΠΊΠΈ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S1 Π²ΠΈΠ·Π½Π°Ρ‡Π°Ρ”ΠΌΠΎ Ρ—Ρ— полоТСння відносно Ρ†ΠΈΡ… прямих. Π’ΠΎΡ‡ΠΊΠΈ, які ΠΏΠΎΠΏΠ°Π»ΠΈ Π² Ρ‚Ρ€ΠΈΠΊΡƒΡ‚Π½ΠΈΠΊ lhr, ΠΌΠΎΠΆΡƒΡ‚ΡŒ Π±ΡƒΡ‚ΠΈ Π²ΠΈΠ»ΡƒΡ‡Π΅Π½Ρ– Π· ΠΏΠΎΠ΄Π°Π»ΡŒΡˆΠΎΡ— ΠΎΠ±Ρ€ΠΎΠ±ΠΊΠΈ. Π–ΠΎΠ΄Π½Π° Π· Ρ‚ΠΎΡ‡ΠΎΠΊ Π½Π΅ Π·Π½Π°Ρ…ΠΎΠ΄ΠΈΡ‚ΡŒΡΡ Π·Π»Ρ–Π²Π° Π²Ρ–Π΄ L1 Ρ‚Π° Π·Π»Ρ–Π²Π° Π²Ρ–Π΄ L2 (напрямки прямих Π²ΠΊΠ°Π·Π°Π½ΠΎ Π½Π° Ρ€ΠΈΡΡƒΠ½ΠΊΡƒ). Π’ΠΎΡ‡ΠΊΠΈ, Ρ€ΠΎΠ·Ρ‚Π°ΡˆΠΎΠ²Π°Π½Ρ– Π·Π»Ρ–Π²Π° Π²Ρ–Π΄ L1 Ρ‡ΠΈ Π½Π° Π½Ρ–ΠΉ, ΡƒΡ‚Π²ΠΎΡ€ΡŽΡŽΡ‚ΡŒ ΠΌΠ½ΠΎΠΆΠΈΠ½Ρƒ S11. Аналогічно ΡƒΡ‚Π²ΠΎΡ€ΡŽΡ”Ρ‚ΡŒΡΡ ΠΌΠ½ΠΎΠΆΠΈΠ½Π° S12. Π£Ρ‚Π²ΠΎΡ€Π΅Π½Ρ– ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S11 Ρ‚Π° S12 ΠΏΠ΅Ρ€Π΅Π΄Π°ΡŽΡ‚ΡŒΡΡ Π΄Π°Π»Ρ– Π½Π° Π½Π°ΡΡ‚ΡƒΠΏΠ½ΠΈΠΉ Ρ€Ρ–Π²Π΅Π½ΡŒ рСкурсивної ΠΎΠ±Ρ€ΠΎΠ±ΠΊΠΈ.

Π’ΠΈΠ±Ρ–Ρ€ ΠΏΠΎΡ‡Π°Ρ‚ΠΊΠΎΠ²ΠΈΡ… Π·Π½Π°Ρ‡Π΅Π½ΡŒ {l0, r0} Ρ‚ΠΎΡ‡ΠΎΠΊ l Ρ‚Π° r ΠΌΠΎΠΆΠ½Π° спростити. Π’ ΡΠΊΠΎΡΡ‚Ρ– l Π²Ρ–Π·ΡŒΠΌΠ΅ΠΌΠΎ Ρ‚ΠΎΡ‡ΠΊΡƒ (x0, y0), яка ΠΌΠ°Ρ” Π½Π°ΠΉΠΌΠ΅Π½ΡˆΡƒ абсцису, Π° Π² ΡΠΊΠΎΡΡ‚Ρ– r Π²Ρ–Π·ΡŒΠΌΠ΅ΠΌΠΎ Ρ‚ΠΎΡ‡ΠΊΡƒ (x0, y0 — e), Π΄Π΅ e — ΠΌΠ°Π»Π΅ Π΄ΠΎΠ΄Π°Ρ‚Π½Π΅ число. Π’Π΅Ρ€Ρ‚ΠΈΠΊΠ°Π»ΡŒΠ½Π° пряма, Ρ‰ΠΎ ΠΏΡ€ΠΎΡ…ΠΎΠ΄ΠΈΡ‚ΡŒ Ρ‡Π΅Ρ€Π΅Π· l, Π±ΡƒΠ΄Π΅ ΠΏΠ΅Ρ€ΡˆΠΎΡŽ ΠΏΡ€ΡΠΌΠΎΡŽ, яка Ρ€ΠΎΠ·Π±ΠΈΠ²Π°Ρ” ΠΌΠ½ΠΎΠΆΠΈΠ½Ρƒ Ρ‚ΠΎΡ‡ΠΎΠΊ S. Π”Ρ€ΡƒΠ³ΠΎΡŽ ΠΏΡ€ΡΠΌΠΎΡŽ Π±ΡƒΠ΄Π΅ пряма, Ρ‰ΠΎ ΠΏΡ€ΠΎΡ…ΠΎΠ΄ΠΈΡ‚ΡŒ Ρ‡Π΅Ρ€Π΅Π· Ρ‚ΠΎΡ‡ΠΊΠΈ Π· Π΅ΠΊΡΡ‚Ρ€Π΅ΠΌΠ°Π»ΡŒΠ½ΠΈΠΌΠΈ абсцисами.

Π§Π΅Ρ€Π΅Π· * Π΄Π°Π»Ρ– ΠΏΠΎΠ·Π½Π°Ρ‡Π΅Π½ΠΎ ΠΎΠΏΠ΅Ρ€Π°Ρ†Ρ–ΡŽ ΠΊΠΎΠ½ΠΊΠ°Ρ‚Π΅Π½Π°Ρ†Ρ–Ρ— списків.

Π¨Π²ΠΈΠ΄ΠΊΠ° ΠΎΠΏΡƒΠΊΠ»Π° ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠ° (S, l, r).

if (S = {l, r}) then return (l, r) /* ΠΎΠΏΡƒΠΊΠ»Π° ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠ° ΡΠΊΠ»Π°Π΄Π°Ρ”Ρ‚ΡŒΡΡ Π· Ρ”Π΄ΠΈΠ½ΠΎΠ³ΠΎ ΠΎΡ€Ρ–Ρ”Π½Ρ‚ΠΎΠ²Π°Π½ΠΎΠ³ΠΎ Ρ€Π΅Π±Ρ€Π° */.

else.

begin.

h ΡΠ°ΠΌΠ° дальня Ρ‚ΠΎΡ‡ΠΊΠ° (S, l, r);

S1 Ρ‚ΠΎΡ‡ΠΊΠΈ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S, Ρ€ΠΎΠ·Ρ‚Π°ΡˆΠΎΠ²Π°Π½Ρ– Π·Π»Ρ–Π²Π° Π²Ρ–Π΄ прямої lh Ρ‡ΠΈ Π½Π° Π½Ρ–ΠΉ;

S2 Ρ‚ΠΎΡ‡ΠΊΠΈ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S, Ρ€ΠΎΠ·Ρ‚Π°ΡˆΠΎΠ²Π°Π½Ρ– Π·Π»Ρ–Π²Π° Π²Ρ–Π΄ прямої hr Ρ‡ΠΈ Π½Π° Π½Ρ–ΠΉ;

return Π¨Π²ΠΈΠ΄ΠΊΠ° ΠΎΠΏΡƒΠΊΠ»Π° ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠ° (S1, l, r) * (Π¨Π²ΠΈΠ΄ΠΊΠ° ΠΎΠΏΡƒΠΊΠ»Π° ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠ° (S2, h, r) — h);

end;

begin.

l0 (x0, y0) Ρ‚ΠΎΡ‡ΠΊΠ° ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S Π· Π½Π°ΠΉΠΌΠ΅Π½ΡˆΠΎΡŽ Π°Π±ΡΡ†ΠΈΡΠΎΡŽ;

r0 (x0, y0 — e);

Π¨Π²ΠΈΠ΄ΠΊΠ° ΠΎΠΏΡƒΠΊΠ»Π° ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠ° (S, l0, r0);

Π²ΠΈΠ΄Π°Π»ΠΈΡ‚ΠΈ Ρ‚ΠΎΡ‡ΠΊΡƒ r0 /* Ρ†Π΅ Π΅ΠΊΠ²Ρ–Π²Π°Π»Π΅Π½Ρ‚Π½ΠΎ Ρ‚ΠΎΠΌΡƒ, якщо покласти e = 0 */.

end.

Алгоритм Ρ‚ΠΈΠΏΡƒ розділяй Ρ‚Π° ΠΏΠ°Π½ΡƒΠΉ ΠŸΡ€ΠΈΠΏΡƒΡΡ‚ΠΈΠΌΠΎ, Ρ‰ΠΎ ΠΏΡ€ΠΈ Ρ€ΠΎΠ·Π²’язку Π·Π°Π΄Π°Ρ‡Ρ– ΠΏΠΎΠ±ΡƒΠ΄ΠΎΠ²ΠΈ ΠΎΠΏΡƒΠΊΠ»ΠΎΡ— ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ ΠΏΠΎΡ‡Π°Ρ‚ΠΊΠΎΠ²Π° ΠΌΠ½ΠΎΠΆΠΈΠ½Π° Ρ‚ΠΎΡ‡ΠΎΠΊ S Π±ΡƒΠ»Π° Ρ€ΠΎΠ·Π±ΠΈΡ‚Π° Π½Π° Π΄Π²Ρ– частини S1 Ρ‚Π° S2, ΠΊΠΎΠΆΠ½Π° Π· ΡΠΊΠΈΡ… ΠΌΡ–ΡΡ‚ΠΈΡ‚ΡŒ ΠΏΠΎΠ»ΠΎΠ²ΠΈΠ½Ρƒ Ρ‚ΠΎΡ‡ΠΎΠΊ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S. Π―ΠΊΡ‰ΠΎ Ρ‚Π΅ΠΏΠ΅Ρ€ рСкурсивно Π·Π½Π°ΠΉΡ‚ΠΈ CH (S1) Ρ‚Π° CH (S2), Ρ‚ΠΎ ΠΎΠΏΡƒΠΊΠ»Ρƒ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΡƒ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S ΠΌΠΎΠΆΠ½Π° Π·Π½Π°ΠΉΡ‚ΠΈ Π· рівності: CH (S1) = CH (CH (S1) (S2)). ΠŸΡ€ΠΈ Ρ†ΡŒΠΎΠΌΡƒ Ρ‚Ρ€Π΅Π±Π° ΠΏΠ°ΠΌ’ятати, Ρ‰ΠΎ CH (S1) Ρ‚Π° CH (S2) — Ρ†Π΅ ΠΎΠΏΡƒΠΊΠ»Ρ– ΠΌΠ½ΠΎΠ³ΠΎΠΊΡƒΡ‚Π½ΠΈΠΊΠΈ. Алгоритм розділяй Ρ‚Π° ΠΏΠ°Π½ΡƒΠΉ ΠΌΠ°Ρ” наступний вигляд:

1. Π―ΠΊΡ‰ΠΎ |S| k (k — Π½Π΅Π²Π΅Π»ΠΈΠΊΠ΅ Ρ†Ρ–Π»Π΅ число), Ρ‚ΠΎ ΠΏΠΎΠ±ΡƒΠ΄ΡƒΠ²Π°Ρ‚ΠΈ ΠΎΠΏΡƒΠΊΠ»Ρƒ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΡƒ ΠΎΠ΄Π½ΠΈΠΌ Ρ–Π· прямих ΠΌΠ΅Ρ‚ΠΎΠ΄Ρ–Π² Ρ‚Π° Π·ΡƒΠΏΠΈΠ½ΠΈΡ‚ΠΈΡΡΡ–Π½Π°ΠΊΡˆΠ΅ ΠΏΠ΅Ρ€Π΅ΠΉΡ‚ΠΈ Π΄ΠΎ ΠΊΡ€ΠΎΠΊΡƒ 2.

2. Π ΠΎΠ·Π±ΠΈΡ‚ΠΈ ΠΌΠ½ΠΎΠΆΠΈΠ½Ρƒ S Π΄ΠΎΠ²Ρ–Π»ΡŒΠ½ΠΈΠΌ Ρ‡ΠΈΠ½ΠΎΠΌ Π½Π° Π΄Π²Ρ– ΠΏΡ€ΠΈΠ±Π»ΠΈΠ·Π½ΠΎ Ρ€Ρ–Π²Π½Ρ– Π·Π° ΠΏΠΎΡ‚ΡƒΠΆΠ½Ρ–ΡΡ‚ΡŽ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ S1 Ρ‚Π° S2.

3. РСкурсивно Π·Π½Π°ΠΉΡ‚ΠΈ ΠΎΠΏΡƒΠΊΠ»Ρ– ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ CH (S1) Ρ‚Π° CH (S2).

4. Π—Π»ΠΈΡ‚ΠΈ Π΄Π²Ρ– ΠΎΡ‚Ρ€ΠΈΠΌΠ°Π½Ρ– ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ, ΡƒΡ‚Π²ΠΎΡ€ΠΈΠ²ΡˆΠΈ CH (S).

Π—Π°Π΄Π°Ρ‡Π°. ΠžΠΏΡƒΠΊΠ»Π° ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠ° ΠΎΠ±'єднання ΠΎΠΏΡƒΠΊΠ»ΠΈΡ… ΠΌΠ½ΠΎΠ³ΠΎΠΊΡƒΡ‚Π½ΠΈΠΊΡ–Π². Π”Π°Π½ΠΎ Π΄Π²Π° ΠΎΠΏΡƒΠΊΠ»ΠΈΡ… ΠΌΠ½ΠΎΠ³ΠΎΠΊΡƒΡ‚Π½ΠΈΠΊΠ° P1 Ρ‚Π° P2. Π—Π½Π°ΠΉΡ‚ΠΈ ΠΎΠΏΡƒΠΊΠ»Ρƒ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΡƒ Ρ—Ρ… ΠΎΠ±'єднання.

Алгоритм ШСймоса.

1. Π—Π½Π°ΠΉΡ‚ΠΈ дСяку Π²Π½ΡƒΡ‚Ρ€Ρ–ΡˆΠ½ΡŽ Ρ‚ΠΎΡ‡ΠΊΡƒ p ΠΌΠ½ΠΎΠ³ΠΎΠΊΡƒΡ‚Π½ΠΈΠΊΠ° P1 — Π½Π°ΠΏΡ€ΠΈΠΊΠ»Π°Π΄, Ρ†Π΅Π½Ρ‚Ρ€ΠΎΡ—Π΄ Ρ‚Ρ€ΡŒΠΎΡ… Π΄ΠΎΠ²Ρ–Π»ΡŒΠ½ΠΈΡ… Π²Π΅Ρ€ΡˆΠΈΠ½ P1. Ця Ρ‚ΠΎΡ‡ΠΊΠ° Π±ΡƒΠ΄Π΅ Π²Π½ΡƒΡ‚Ρ€Ρ–ΡˆΠ½ΡŒΠΎΡŽ Ρ‚ΠΎΡ‡ΠΊΠΎΡŽ CH (P1).

2. Π’ΠΈΠ·Π½Π°Ρ‡ΠΈΡ‚ΠΈ, Ρ‡ΠΈ Ρ” p Π²Π½ΡƒΡ‚Ρ€Ρ–ΡˆΠ½ΡŒΠΎΡŽ Ρ‚ΠΎΡ‡ΠΊΠΎΡŽ P2. Π―ΠΊΡ‰ΠΎ p Π½Π΅ Ρ” Π²Π½ΡƒΡ‚Ρ€Ρ–ΡˆΠ½ΡŒΠΎΡŽ Ρ‚ΠΎΡ‡ΠΊΠΎΡŽ P2, Ρ‚ΠΎ ΠΏΠ΅Ρ€Π΅ΠΉΡ‚ΠΈ Π΄ΠΎ ΠΊΡ€ΠΎΠΊΡƒ 4.

3. p Ρ” Π²Π½ΡƒΡ‚Ρ€Ρ–ΡˆΠ½ΡŒΠΎΡŽ Ρ‚ΠΎΡ‡ΠΊΠΎΡŽ P2. Π’Π΅Ρ€ΡˆΠΈΠ½ΠΈ P1 Ρ‚Π° P2 Ρ” впорядкованими Ρƒ відповідності Π·Ρ– значСнням полярного ΠΊΡƒΡ‚Π° відносно Ρ‚ΠΎΡ‡ΠΊΠΈ p. Π—Π° Ρ‡Π°Ρ O (N) ΠΌΠΎΠΆΠ½Π° Π·Π»ΠΈΡ‚ΠΈ список Π²Π΅Ρ€ΡˆΠΈΠ½ Ρ†ΠΈΡ… ΠΌΠ½ΠΎΠ³ΠΎΠΊΡƒΡ‚Π½ΠΈΠΊΡ–Π², ΠΎΡ‚Ρ€ΠΈΠΌΠ°Π²ΡˆΠΈ впорядкований список Π²Π΅Ρ€ΡˆΠΈΠ½ як P1, Ρ‚Π°ΠΊ Ρ– P2. ΠŸΠ΅Ρ€Π΅ΠΉΡ‚ΠΈ Π΄ΠΎ ΠΊΡ€ΠΎΠΊΡƒ 5.

4. p Π½Π΅ Ρ” Π²Π½ΡƒΡ‚Ρ€Ρ–ΡˆΠ½ΡŒΠΎΡŽ Ρ‚ΠΎΡ‡ΠΊΠΎΡŽ P2. Π―ΠΊΡ‰ΠΎ дивитися Π· Ρ‚ΠΎΡ‡ΠΊΠΈ p, Ρ‚ΠΎ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡƒΡ‚Π½ΠΈΠΊ P2 Π»Π΅ΠΆΠΈΡ‚ΡŒ Ρƒ ΠΊΠ»Ρ–Π½Ρ– Π· ΠΊΡƒΡ‚ΠΎΠΌ Ρ€ΠΎΠ·Π²ΠΎΡ€ΠΎΡ‚Ρƒ мСншим Ρ‡ΠΈ Ρ€Ρ–Π²Π½ΠΈΠΌ Π¦Π΅ΠΉ ΠΊΠ»ΠΈΠ½ Π²ΠΈΠ·Π½Π°Ρ‡Π°Ρ”Ρ‚ΡŒΡΡ Π΄Π²ΠΎΠΌΠ° Π²Π΅Ρ€ΡˆΠΈΠ½Π°ΠΌΠΈ u Ρ‚Π° v ΠΌΠ½ΠΎΠ³ΠΎΠΊΡƒΡ‚Π½ΠΈΠΊΠ° P2, які ΠΌΠΎΠΆΡƒΡ‚ΡŒ Π±ΡƒΡ‚ΠΈ Π·Π½Π°ΠΉΠ΄Π΅Π½Ρ– Π·Π° Π»Ρ–Π½Ρ–ΠΉΠ½ΠΈΠΉ час Π·Π° ΠΎΠ΄ΠΈΠ½ ΠΎΠ±Ρ…Ρ–Π΄ Π²Π΅Ρ€ΡˆΠΈΠ½ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡƒΡ‚Π½ΠΈΠΊΠ° P2. Π¦Ρ– Π²Π΅Ρ€ΡˆΠΈΠ½ΠΈ Ρ€ΠΎΠ·Π±ΠΈΠ²Π°ΡŽΡ‚ΡŒ Π³Ρ€Π°Π½ΠΈΡ†ΡŽ P2 Π½Π° Π΄Π²Π° Π»Π°Π½Ρ†ΡŽΠ³Π° Π²Π΅Ρ€ΡˆΠΈΠ½, які Ρ” ΠΌΠΎΠ½ΠΎΡ‚ΠΎΠ½Π½ΠΈΠΌΠΈ відносно Π·ΠΌΡ–Π½ΠΈ полярного ΠΊΡƒΡ‚Π° Π· ΠΏΠΎΡ‡Π°Ρ‚ΠΊΠΎΠΌ Π² p. ΠŸΡ€ΠΈ русі ΠΏΠΎ ΠΎΠ΄Π½ΠΎΠΌΡƒ Π»Π°Π½Ρ†ΡŽΠ³Ρƒ ΠΊΡƒΡ‚ Π·Π±Ρ–Π»ΡŒΡˆΡƒΡ”Ρ‚ΡŒΡΡ, ΠΏΡ€ΠΈ русі ΠΏΠΎ Π΄Ρ€ΡƒΠ³ΠΎΠΌΡƒ — Π·ΠΌΠ΅Π½ΡˆΡƒΡ”Ρ‚ΡŒΡΡ. Один Π· Π»Π°Π½Ρ†ΡŽΠ³Ρ–Π², який Ρ” ΠΎΠΏΡƒΠΊΠ»ΠΈΠΌ ΠΏΠΎ Π½Π°ΠΏΡ€ΡΠΌΠΊΡƒ Π΄ΠΎ Ρ‚ΠΎΡ‡ΠΊΠΈ p, ΠΌΠΎΠΆΠ΅ Π±ΡƒΡ‚ΠΈ Π²ΠΈΠ΄Π°Π»Π΅Π½ΠΈΠΉ, ΠΎΡΠΊΡ–Π»ΡŒΠΊΠΈ ΠΉΠΎΠ³ΠΎ Π²Π΅Ρ€ΡˆΠΈΠ½ΠΈ Π±ΡƒΠ΄ΡƒΡ‚ΡŒ Π²Π½ΡƒΡ‚Ρ€Ρ–ΡˆΠ½Ρ–ΠΌΠΈ Ρ‚ΠΎΡ‡ΠΊΠ°ΠΌΠΈ CH (P1). Π”Ρ€ΡƒΠ³ΠΈΠΉ Π»Π°Π½Ρ†ΡŽΠ³ P2 Ρ‚Π° Π³Ρ€Π°Π½ΠΈΡ†ΡŽ P1 ΠΌΠΎΠΆΠ½Π° Π·Π»ΠΈΡ‚ΠΈ Π² ΠΎΠ΄ΠΈΠ½ впорядкований список (Π·Π° ΠΏΠΎΠ»ΡΡ€Π½ΠΈΠΌ ΠΊΡƒΡ‚ΠΎΠΌ відносно Ρ‚ΠΎΡ‡ΠΊΠΈ p) Π·Π° Π»Ρ–Π½Ρ–ΠΉΠ½ΠΈΠΉ час.

5. Π”ΠΎ ΠΎΡ‚Ρ€ΠΈΠΌΠ°Π½ΠΎΠ³ΠΎ впорядкованого списку Π²Π΅Ρ€ΡˆΠΈΠ½ застосувати ΠΌΠ΅Ρ‚ΠΎΠ΄ ΠΎΠ±Ρ…ΠΎΠ΄Ρƒ Π“Ρ€Π΅Ρ…Π΅ΠΌΠ°, який Π²ΠΈΠΌΠ°Π³Π°Ρ” Π»Ρ–Π½Ρ–ΠΉΠ½ΠΈΠΉ час.

Π’Π΅ΠΎΡ€Π΅ΠΌΠ°. ΠžΠΏΡƒΠΊΠ»Π° ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠ° ΠΎΠ±'єднання Π΄Π²ΠΎΡ… ΠΎΠΏΡƒΠΊΠ»ΠΈΡ… ΠΌΠ½ΠΎΠ³ΠΎΠΊΡƒΡ‚Π½ΠΈΠΊΡ–Π² ΠΌΠΎΠΆΠ΅ Π±ΡƒΡ‚ΠΈ Π·Π½Π°ΠΉΠ΄Π΅Π½Π° Π·Π° Ρ‡Π°Ρ, ΠΏΡ€ΠΎΠΏΠΎΡ€Ρ†Ρ–ΠΉΠ½ΠΈΠΉ сумарній ΠΊΡ–Π»ΡŒΠΊΠΎΡΡ‚Ρ– Ρ—Ρ… Π²Π΅Ρ€ΡˆΠΈΠ½.

ΠžΠ·Π½Π°Ρ‡Π΅Π½Π½Ρ. ΠžΠΏΠΎΡ€Π½ΠΎΡŽ ΠΏΡ€ΡΠΌΠΎΡŽ Π΄ΠΎ ΠΎΠΏΡƒΠΊΠ»ΠΎΠ³ΠΎ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡƒΡ‚Π½ΠΈΠΊΠ° Π½Π°Π·ΠΈΠ²Π°Ρ”Ρ‚ΡŒΡΡ пряма l, яка ΠΏΡ€ΠΎΡ…ΠΎΠ΄ΠΈΡ‚ΡŒ Ρ‡Π΅Ρ€Π΅Π· дСяку Π²Π΅Ρ€ΡˆΠΈΠ½Ρƒ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡƒΡ‚Π½ΠΈΠΊΠ° P Ρ‚Π°ΠΊΠΈΠΌ Ρ‡ΠΈΠ½ΠΎΠΌ, Ρ‰ΠΎ Π²Π½ΡƒΡ‚Ρ€Ρ–ΡˆΠ½Ρ частина P Ρ†Ρ–Π»ΠΊΠΎΠΌ Π·Π½Π°Ρ…ΠΎΠ΄ΠΈΡ‚ΡŒΡΡ ΠΏΠΎ ΠΎΠ΄Π½Ρƒ сторону Π²Ρ–Π΄ l.

ΠŸΠΎΠ±Ρ–Ρ‡Π½ΠΈΠΌ Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚ΠΎΠΌ описаного ΠΌΠ΅Ρ‚ΠΎΠ΄Π° злиття Ρ” знаходТСння ΠΎΠΏΠΎΡ€Π½ΠΈΡ… прямих для Π΄Π²ΠΎΡ… ΠΎΠΏΡƒΠΊΠ»ΠΈΡ… ΠΌΠ½ΠΎΠ³ΠΎΠΊΡƒΡ‚Π½ΠΈΠΊΡ–Π². Π”Π²Π° ΠΎΠΏΡƒΠΊΠ»ΠΈΡ… ΠΌΠ½ΠΎΠ³ΠΎΠΊΡƒΡ‚Π½ΠΈΠΊΠ° P1 Ρ‚Π° P2 Π· n Ρ‚Π° m Π²Π΅Ρ€ΡˆΠΈΠ½Π°ΠΌΠΈ Π²Ρ–Π΄ΠΏΠΎΠ²Ρ–Π΄Π½ΠΎ, Ρ‚Π°ΠΊΠΈΡ… Ρ‰ΠΎ ΠΎΠ΄ΠΈΠ½ Π½Π΅ Π»Π΅ΠΆΠΈΡ‚ΡŒ Ρ†Ρ–Π»ΠΊΠΎΠΌ всСрСдині Ρ–Π½ΡˆΠΎΠ³ΠΎ, ΠΌΠ°ΡŽΡ‚ΡŒ Π½Π΅ Π±Ρ–Π»ΡŒΡˆ Π½Ρ–ΠΆ 2 * min (n, m) ΠΎΠΏΠΎΡ€Π½ΠΈΡ… прямих. Π―ΠΊΡ‰ΠΎ Π²ΠΆΠ΅ ΠΎΡ‚Ρ€ΠΈΠΌΠ°Π½ΠΎ ΠΎΠΏΡƒΠΊΠ»Ρƒ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΡƒ ΠΎΠ±'єднання P1 Ρ‚Π° P2, Ρ‚ΠΎ ΠΎΠΏΠΎΡ€Π½Ρ– прямі ΠΎΠ±Ρ‡ΠΈΡΠ»ΡŽΡŽΡ‚ΡŒΡΡ Π² Ρ€Π΅Π·ΡƒΠ»ΡŒΡ‚Π°Ρ‚Ρ– пСрСгляду списку Π²Π΅Ρ€ΡˆΠΈΠ½ CH (P1).

Π’Π΅ΠΎΡ€Π΅ΠΌΠ°. КоТна ΠΏΠ°Ρ€Π° послідовних Π²Π΅Ρ€ΡˆΠΈΠ½ CH (P1), ΠΎΠ΄Π½Π° Π· ΡΠΊΠΈΡ… Π½Π°Π»Π΅ΠΆΠΈΡ‚ΡŒ P1, Π° Π΄Ρ€ΡƒΠ³Π° P2, Π²ΠΈΠ·Π½Π°Ρ‡Π°Ρ” ΠΎΠΏΠΎΡ€Π½Ρƒ пряму.

ΠŸΠΎΠ±ΡƒΠ΄ΠΎΠ²Π° ΠΎΠΏΡƒΠΊΠ»ΠΎΡ— ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ простого ΠΌΠ½ΠΎΠ³ΠΎΠΊΡƒΡ‚Π½ΠΈΠΊΠ° Алгоритм Π›Ρ–. НСхай p1 — сама Π»Ρ–Π²Π° Π²Π΅Ρ€ΡˆΠΈΠ½Π° Π·Π°Π΄Π°Π½ΠΎΠ³ΠΎ простого ΠΌΠ½ΠΎΠ³ΠΎΠΊΡƒΡ‚Π½ΠΈΠΊΠ° P, Π° (p1, p2, …, pN) — впорядкована Ρ†ΠΈΠΊΠ»Ρ–Ρ‡Π½Π° ΠΏΠΎΡΠ»Ρ–Π΄ΠΎΠ²Π½Ρ–ΡΡ‚ΡŒ ΠΉΠΎΠ³ΠΎ Π²Π΅Ρ€ΡˆΠΈΠ½ (Π·Π° Π²Π΅Ρ€ΡˆΠΈΠ½ΠΎΡŽ pN ΠΉΠ΄Π΅ p1). Π’Π½ΡƒΡ‚Ρ€Ρ–ΡˆΠ½Ρ–ΡΡ‚ΡŒ P Π·Π°Π»ΠΈΡˆΠ°Ρ”Ρ‚ΡŒΡΡ ΠΏΠΎ ΠΏΡ€Π°Π²Ρƒ сторону ΠΏΡ€ΠΈ ΠΎΠ±Ρ…ΠΎΠ΄Ρ– ΠΉΠΎΠ³ΠΎ Π³Ρ€Π°Π½ΠΈΡ†Ρ– Π² ΡƒΠΊΠ°Π·Π°Π½ΠΎΠΌΡƒ порядку. НСхай pM — сама ΠΏΡ€Π°Π²Π° Π²Π΅Ρ€ΡˆΠΈΠ½Π°. p1 Ρ‚Π° pM Ρ” Π³Ρ€Π°Π½ΠΈΡ‡Π½ΠΈΠΌΠΈ Ρ‚ΠΎΡ‡ΠΊΠ°ΠΌΠΈ ΠΎΠΏΡƒΠΊΠ»ΠΎΡ— ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡƒΡ‚Π½ΠΈΠΊΠ° P. Π’ΠΎΠ½ΠΈ Ρ€ΠΎΠ·Π±ΠΈΠ²Π°ΡŽΡ‚ΡŒ ΠΏΠΎΡΠ»Ρ–Π΄ΠΎΠ²Π½Ρ–ΡΡ‚ΡŒ Π²Π΅Ρ€ΡˆΠΈΠ½ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡƒΡ‚Π½ΠΈΠΊΠ° Π½Π° Π΄Π²Π° Π»Π°Π½Ρ†ΡŽΠ³ΠΈ: ΠΎΠ΄ΠΈΠ½ Π²Ρ–Π΄ p1 Π΄ΠΎ pM, Π΄Ρ€ΡƒΠ³ΠΈΠΉ — Π²Ρ–Π΄ pM Π΄ΠΎ p1. Π”ΠΎΡΡ‚Π°Ρ‚Π½ΡŒΠΎ дослідити ΠΏΠΎΠ±ΡƒΠ΄ΠΎΠ²Ρƒ ΠΎΠΏΡƒΠΊΠ»ΠΎΡ— ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ для Π»Π°Π½Ρ†ΡŽΠ³Π° (p1, p2, …, pM), яку Π±ΡƒΠ΄Π΅ΠΌΠΎ Π½Π°Π·ΠΈΠ²Π°Ρ‚ΠΈ Π²Π΅Ρ€Ρ…Π½ΡŒΠΎΡŽ оболонкою.

НСхай (q1, q2, …, qR) — ΠΏΡ–Π΄ΠΏΠΎΡΠ»Ρ–Π΄ΠΎΠ²Π½Ρ–ΡΡ‚ΡŒ (p1, p2, …, pM), Π² ΡΠΊΡ–ΠΉ q1 = p1 Ρ‚Π° qR = pM — ΡˆΡƒΠΊΠ°Π½Π° ΠΎΠΏΡƒΠΊΠ»Π° ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠ° ΠΌΠ½ΠΎΠ³ΠΎΠΊΡƒΡ‚Π½ΠΈΠΊΠ°. КоТнС Ρ€Π΅Π±Ρ€ΠΎ qiqi+1 Ρ” «ΠΊΡ€ΠΈΡˆΠΊΠΎΡŽ ΠΊΠ°Ρ€ΠΌΠ°Π½Π°» Ki, Π΄Π΅ ΠΊΠ°Ρ€ΠΌΠ°Π½ Ki — Ρ†Π΅ Π»Π°Π½Ρ†ΡŽΠ³ послідовності (p1, p2, …, pM), ΠΏΠ΅Ρ€ΡˆΠΎΡŽ Ρ‚Π° ΠΎΡΡ‚Π°Π½Π½ΡŒΠΎΡŽ Π²Π΅Ρ€ΡˆΠΈΠ½Π°ΠΌΠΈ якої Ρ” qi Ρ‚Π° qi+1 Π²Ρ–Π΄ΠΏΠΎΠ²Ρ–Π΄Π½ΠΎ.

Алгоритм Π›Ρ– ΠΏΡ€ΠΎΡ…ΠΎΠ΄ΠΈΡ‚ΡŒ Π»Π°Π½Ρ†ΡŽΠ³ Ρ‚Π° ΠΏΠΎΡΠ»Ρ–Π΄ΠΎΠ²Π½ΠΎ Π±ΡƒΠ΄ΡƒΡ” ΠΊΡ€ΠΈΡˆΠΊΠΈ усіх ΠΊΠ°Ρ€ΠΌΠ°Π½Ρ–Π². ΠšΡ€ΠΈΡ‚ΠΈΡ‡Π½ΠΎΡŽ Π±ΡƒΠ΄Π΅ΠΌΠΎ Π½Π°Π·ΠΈΠ²Π°Ρ‚ΠΈ Π²Π΅Ρ€ΡˆΠΈΠ½Ρƒ, яка Π· ΠΎΡΡ‚Π°Π½Π½ΡŒΠΎΡŽ знайдСною Π²Π΅Ρ€ΡˆΠΈΠ½ΠΎΡŽ Ρ‚ΠΈΠΏΡƒ q ΡƒΡ‚Π²ΠΎΡ€ΡŽΡ” ΠΊΠ°Ρ€ΠΌΠ°Π½. АлС Π½Π΅ ΠΊΠΎΠΆΠ½Π° ΠΊΡ€ΠΈΡ‚ΠΈΡ‡Π½Π° Π²Π΅Ρ€ΡˆΠΈΠ½Π° Π½Π°Π»Π΅ΠΆΠΈΡ‚ΡŒ ΠΊΡ–Π½Ρ†Π΅Π²Ρ–ΠΉ ΠΎΠΏΡƒΠΊΠ»Ρ–ΠΉ ΠΎΠ±ΠΎΠ»ΠΎΠ½Ρ†Ρ–. ΠšΡ€ΠΎΠΊΠΎΠΌ просунСння Π±ΡƒΠ΄Π΅ΠΌΠΎ Π½Π°Π·ΠΈΠ²Π°Ρ‚ΠΈ ΠΏΠ΅Ρ€Π΅Ρ…Ρ–Π΄ Π²Ρ–Π΄ ΠΎΠ΄Π½Ρ–Ρ”Ρ— ΠΊΡ€ΠΈΡ‚ΠΈΡ‡Π½ΠΎΡ— Π²Π΅Ρ€ΡˆΠΈΠ½ΠΈ Π΄ΠΎ Ρ–Π½ΡˆΠΎΡ—. Наприклад, Π½Π° Ρ‚Ρ€Π΅Ρ‚ΡŒΠΎΠΌΡƒ ΠΊΡ€ΠΎΡ†Ρ– ΠΊΡ€ΠΈΡ‚ΠΈΡ‡Π½ΠΎΡŽ Ρ‚ΠΎΡ‡ΠΊΠΎΡŽ Ρ” p4. ΠΠ°ΡΡ‚ΡƒΠΏΠ½ΠΎΡŽ ΠΊΡ€ΠΈΡ‚ΠΈΡ‡Π½ΠΎΡŽ Ρ‚ΠΎΡ‡ΠΊΠΎΡŽ Π±ΡƒΠ΄Π΅ p7. ΠŸΡ€ΠΈ Ρ†ΡŒΠΎΠΌΡƒ ΠΊΡ€ΠΈΡ‚ΠΈΡ‡Π½Π° Ρ‚ΠΎΡ‡ΠΊΠ° p4 Π½Π΅ Π½Π°Π»Π΅ΠΆΠΈΡ‚ΡŒ ΠΎΠΏΡƒΠΊΠ»Ρ–ΠΉ ΠΎΠ±ΠΎΠ»ΠΎΠ½Ρ†Ρ–.

1 ΠΊΡ€ΠΎΠΊ 2 ΠΊΡ€ΠΎΠΊ 3 ΠΊΡ€ΠΎΠΊ 4 ΠΊΡ€ΠΎΠΊ.

ΠŸΡ€ΠΈΠΏΡƒΡΡ‚ΠΈΠΌΠΎ, Ρ‰ΠΎ Π³Ρ€Π°Π½ΠΈΡ†Ρ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡƒΡ‚Π½ΠΈΠΊΠ° проглянута Π²Ρ–Π΄ Π²Π΅Ρ€ΡˆΠΈΠ½ΠΈ p1 Π΄ΠΎ ps (s M) Ρ– Π²Π΅Ρ€ΡˆΠΈΠ½Π° ps = qi Ρ” ΠΊΡ€ΠΈΡ‚ΠΈΡ‡Π½ΠΎΡŽ. ΠŸΠΎΠ·Π½Π°Ρ‡ΠΈΠΌΠΎ Ρ‡Π΅Ρ€Π΅Π· u Π²Π΅Ρ€ΡˆΠΈΠ½Ρƒ Π³Ρ€Π°Π½ΠΈΡ†Ρ– Π , яка Ρ” ΠΏΠΎΠΏΠ΅Ρ€Π΅Π΄Π½ΡŒΠΎΡŽ Π΄ΠΎ qi. Π’ Π·Π°Π»Π΅ΠΆΠ½ΠΎΡΡ‚Ρ– Π²Ρ–Π΄ полоТСння u відносно ΠΎΡ€Ρ–Ρ”Π½Ρ‚ΠΎΠ²Π°Π½ΠΎΠ³ΠΎ Π²Ρ–Π΄Ρ€Ρ–Π·ΠΊΠ° qMqi ΠΌΠ°ΡŽΡ‚ΡŒ місцС Π΄Π²Π° Π²ΠΈΠΏΠ°Π΄ΠΊΠΈ:

1. Π’Π΅Ρ€ΡˆΠΈΠ½Π° u Π·Π½Π°Ρ…ΠΎΠ΄ΠΈΡ‚ΡŒΡΡ справа Π²Ρ–Π΄ qMqi Π°Π±ΠΎ Π½Π° Π½ΡŒΠΎΠΌΡƒ. Π’ΠΎΠ΄Ρ– Ρ‚Ρ€Π΅Π±Π° дослідити Ρ‚Ρ€ΠΈ області, які Π²ΠΈΠ·Π½Π°Ρ‡Π°ΡŽΡ‚ΡŒΡΡ: ΠΏΡ€ΡΠΌΠΎΡŽ, Ρ‰ΠΎ ΠΏΡ€ΠΎΡ…ΠΎΠ΄ΠΈΡ‚ΡŒ Ρ‡Π΅Ρ€Π΅Π· Ρ‚ΠΎΡ‡ΠΊΠΈ qi-1 Ρ‚Π° qiΠΏΡ€ΠΎΠΌΡ–Π½Π΅ΠΌ, який Ρ” продовТСнням Π²Ρ–Π΄Ρ€Ρ–Π·ΠΊΡƒ qiu Ρ‚Π° Ρ‡Π°ΡΡ‚ΠΈΠ½ΠΎΡŽ Ρ‚Π° Ρ‡Π°ΡΡ‚ΠΈΠ½ΠΎΡŽ Π³Ρ€Π°Π½ΠΈΡ†Ρ– ΠΌΠ½ΠΎΠ³ΠΎΠΊΡƒΡ‚Π½ΠΈΠΊΠ° P, яка Π²Ρ–Π΄ΠΏΠΎΠ²Ρ–Π΄Π°Ρ” ΠΊΠ°Ρ€ΠΌΠ°Π½Ρƒ Ki-1.

2. Π’Π΅Ρ€ΡˆΠΈΠ½Π° u Π·Π½Π°Ρ…ΠΎΠ΄ΠΈΡ‚ΡŒΡΡ Π·Π»Ρ–Π²Π° Π²Ρ–Π΄ qMqi. Π”ΠΎ Π΄ΠΎΡΠ»Ρ–дТСння Ρ‚Ρ€Π΅Π±Π° Π΄ΠΎΠ΄Π°Ρ‚ΠΈ Ρ‡Π΅Ρ‚Π²Π΅Ρ€Ρ‚Ρƒ ΠΎΠ±Π»Π°ΡΡ‚ΡŒ.

ΠŸΠΎΠ·Π½Π°Ρ‡ΠΈΠΌΠΎ Ρ‡Π΅Ρ€Π΅Π· v Π²Π΅Ρ€ΡˆΠΈΠ½Ρƒ, яка ΠΉΠ΄Π΅ Π·Π° qi Π½Π° Π³Ρ€Π°Π½ΠΈΡ†Ρ– ΠΌΠ½ΠΎΠ³ΠΎΠΊΡƒΡ‚Π½ΠΈΠΊΠ° P. Ця Π²Π΅Ρ€ΡˆΠΈΠ½Π° v ΠΌΠΎΠΆΠ΅ знаходитися Π² ΠΎΠ΄Π½Ρ–ΠΉ Ρ–Π· областСй, які Π²ΠΈΠ·Π½Π°Ρ‡Π΅Π½ΠΎ Π²ΠΈΡ‰Π΅. Π’ ΠΎΠ±Π»Π°ΡΡ‚ях 2 Ρ‚Π° 3 Π²Π΅Ρ€ΡˆΠΈΠ½Π° v Π±ΡƒΠ΄Π΅ ΠΊΡ€ΠΈΡ‚ΠΈΡ‡Π½ΠΎΡŽ, Π² Ρ–Π½ΡˆΠΈΡ… — Π½Ρ–. Дослідимо Π²ΠΈΠΏΠ°Π΄ΠΊΠΈ Ρ€ΠΎΠ·Ρ‚Π°ΡˆΡƒΠ²Π°Π½Π½Ρ Π²Π΅Ρ€ΡˆΠΈΠ½ΠΈ v Π² ΠΊΠΎΠΆΠ½Ρ–ΠΉ Ρ–Π· Ρ†ΠΈΡ… областСй.

ΠžΠ±Π»Π°ΡΡ‚ΡŒ 1. Границя ΠΌΠ½ΠΎΠ³ΠΎΠΊΡƒΡ‚Π½ΠΈΠΊΠ° Π·Π°Ρ…ΠΎΠ΄ΠΈΡ‚ΡŒ Π΄ΠΎ ΠΊΠ°Ρ€ΠΌΠ°Π½Ρƒ. Рухаємося ΠΏΠΎ Π³Ρ€Π°Π½ΠΈΡ†Ρ– Π΄ΠΎ Ρ‚ΠΈΡ… ΠΏΡ–Ρ€, ΠΏΠΎΠΊΠΈ Π½Π΅ Π΄ΠΎΡΡΠ³Π½Π΅ΠΌΠΎ ΠΏΠ΅Ρ€ΡˆΠΎΠ³ΠΎ Ρ€Π΅Π±Ρ€Π° Π³Ρ€Π°Π½ΠΈΡ†Ρ–, ΠΎΠ΄Π½Π° Π· Π²Π΅Ρ€ΡˆΠΈΠ½ w ΡΠΊΠΎΠ³ΠΎ Π·Π½Π°Ρ…ΠΎΠ΄ΠΈΡ‚ΡŒΡΡ Π·ΠΎΠ²Π½Ρ– ΠΊΠ°Ρ€ΠΌΠ°Π½Π° (Ρ‚ΠΎΠ±Ρ‚ΠΎ Π² ΠΎΠ±Π»Π°ΡΡ‚Ρ– 2). Π¦Π΅ ΠΎΠ±ΠΎΠ²’язково Π²Ρ–Π΄Π±ΡƒΠ΄Π΅Ρ‚ΡŒΡΡ, ΠΎΡΠΊΡ–Π»ΡŒΠΊΠΈ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡƒΡ‚Π½ΠΈΠΊ простий.

ΠžΠ±Π»Π°ΡΡ‚ΡŒ 2. Π¨ΡƒΠΊΠ°Ρ”Ρ‚ΡŒΡΡ ΠΎΠΏΠΎΡ€Π½Π° пряма Π· Π²Π΅Ρ€ΡˆΠΈΠ½ΠΈ v Π΄ΠΎ Π»Π°Π½Ρ†ΡŽΠ³Π° (q1, q2, …, qi-1). Π―ΠΊΡ‰ΠΎ ця ΠΏΡ€ΡΠΌΠ° ΠΌΡ–ΡΡ‚ΠΈΡ‚ΡŒ qr (r < i), Ρ‚ΠΎ Π²Π΅Ρ€ΡˆΠΈΠ½ΠΈ (qr+1, qr+2, …, qi) Π²ΠΈΠ΄Π°Π»ΡΡŽΡ‚ΡŒΡΡ, Π° v Π±Π΅Ρ€Π΅Ρ‚ΡŒΡΡ Π² ΡΠΊΠΎΡΡ‚Ρ– Π½ΠΎΠ²ΠΎΡ— qr+1.

ΠžΠ±Π»Π°ΡΡ‚ΡŒ 3. Π’Π΅Ρ€ΡˆΠΈΠ½Π° v Ρ” ΠΊΡ€ΠΈΡ‚ΠΈΡ‡Π½ΠΎΡŽ Ρ– Π±Π΅Ρ€Π΅Ρ‚ΡŒΡΡ Π² ΡΠΊΠΎΡΡ‚Ρ– qi+1.

ΠžΠ±Π»Π°ΡΡ‚ΡŒ 4. Границя ΠΌΠ½ΠΎΠ³ΠΎΠΊΡƒΡ‚Π½ΠΈΠΊΠ° Π·Π°Ρ…ΠΎΠ΄ΠΈΡ‚ΡŒ всСрСдину ΠΎΠΏΡƒΠΊΠ»ΠΎΡ— ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ. Π―ΠΊ Ρ– Π² ΠΏΠ΅Ρ€ΡˆΠΎΠΌΡƒ Π²ΠΈΠΏΠ°Π΄ΠΊΡƒ Π±ΡƒΠ΄Π΅ΠΌΠΎ рухатися ΠΏΠΎ Π³Ρ€Π°Π½ΠΈΡ†Ρ– ΠΌΠ½ΠΎΠ³ΠΎΠΊΡƒΡ‚Π½ΠΈΠΊΠ° Π΄ΠΎ Ρ‚ΠΈΡ… ΠΏΡ–Ρ€, ΠΏΠΎΠΊΠΈ Π½Π΅ Π΄ΠΎΡΡΠ³Π½Π΅ΠΌΠΎ ΠΏΠ΅Ρ€ΡˆΠΎΠ³ΠΎ Ρ€Π΅Π±Ρ€Π°, якС ΠΌΠ°Ρ” наступні властивості: ΠΎΠ΄Π½Π° Π· ΠΉΠΎΠ³ΠΎ Π²Π΅Ρ€ΡˆΠΈΠ½ Ρ” Π·ΠΎΠ²Π½Ρ–ΡˆΠ½ΡŒΠΎΡŽ ΠΏΠΎ Π²Ρ–Π΄Π½ΠΎΡˆΠ΅Π½Π½ΡŽ Π΄ΠΎ ΠΎΠ±Π»Π°ΡΡ‚Ρ– 4 Π°Π±ΠΎ співпадає Π· qM.

Π’Π΅ΠΎΡ€Π΅ΠΌΠ°. ΠžΠΏΡƒΠΊΠ»Π° ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠ° простого ΠΌΠ½ΠΎΠ³ΠΎΠΊΡƒΡ‚Π½ΠΈΠΊΠ° Π· N Π²Π΅Ρ€ΡˆΠΈΠ½Π°ΠΌΠΈ ΠΌΠΎΠΆΠ΅ Π±ΡƒΡ‚ΠΈ ΠΏΠΎΠ±ΡƒΠ΄ΠΎΠ²Π°Π½Π° Π·Π° ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΈΠΉ час O (N) Π· Π²ΠΈΠΊΠΎΡ€ΠΈΡΡ‚анням ΠΏΠ°ΠΌ’яті ΠΎΠ±'Ρ”ΠΌΠΎΠΌ O (N).

Π”ΠΈΠ½Π°ΠΌΡ–Ρ‡Π½Ρ– Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΠΈ ΠΏΠΎΠ±ΡƒΠ΄ΠΎΠ²ΠΈ ΠΎΠΏΡƒΠΊΠ»ΠΎΡ— ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ ΠžΠ·Π½Π°Ρ‡Π΅Π½Π½Ρ. Алгоритм, який обробляє Π΄Π°Π½Ρ– ΠΏΠΎ ΠΌΡ–Ρ€Ρ– Ρ—Ρ… надходТСння, Π½Π°Π·ΠΈΠ²Π°Ρ”Ρ‚ΡŒΡΡ Π²Ρ–Π΄ΠΊΡ€ΠΈΡ‚ΠΈΠΌ. Алгоритм, якийобробляє всю ΡΡƒΠΊΡƒΠΏΠ½Ρ–ΡΡ‚ΡŒ Π΄Π°Π½ΠΈΡ… Π²Ρ†Ρ–Π»ΠΎΠΌΡƒ, Π½Π°Π·ΠΈΠ²Π°Ρ”Ρ‚ΡŒΡΡ Π·Π°ΠΊΡ€ΠΈΡ‚ΠΈΠΌ.

ΠžΠ·Π½Π°Ρ‡Π΅Π½Π½Ρ. Часовий ΠΏΡ€ΠΎΠΌΡ–ΠΆΠΎΠΊ ΠΌΡ–ΠΆ Π²Π²ΠΎΠ΄ΠΎΠΌ Π΄Π²ΠΎΡ… послідовних Π΅Π»Π΅ΠΌΠ΅Π½Ρ‚Ρ–Π² Π΄Π°Π½ΠΈΡ… Π½Π°Π·ΠΈΠ²Π°Ρ”Ρ‚ΡŒΡΡ Π·Π°Ρ‚Ρ€ΠΈΠΌΠΊΠΎΡŽ надходТСння Π΄Π°Π½ΠΈΡ….

Π—Π°Π΄Π°Ρ‡Π°. Π’Ρ–Π΄ΠΊΡ€ΠΈΡ‚ΠΈΠΉ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ для ΠΎΠΏΡƒΠΊΠ»ΠΎΡ— ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ. На ΠΏΠ»ΠΎΡ‰ΠΈΠ½Ρ– Π·Π°Π΄Π°Π½Π° ΠΏΠΎΡΠ»Ρ–Π΄ΠΎΠ²Π½Ρ–ΡΡ‚ΡŒ N Ρ‚ΠΎΡ‡ΠΎΠΊ p1, p2, …, pN. НСобхідно Π·Π½Π°ΠΉΡ‚ΠΈ Ρ—Ρ… ΠΎΠΏΡƒΠΊΠ»Ρƒ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΡƒ Ρ‚Π°ΠΊΠΈΠΌ Ρ‡ΠΈΠ½ΠΎΠΌ, Ρ‰ΠΎΠ± після ΠΎΠ±Ρ€ΠΎΠ±ΠΊΠΈ Ρ‚ΠΎΡ‡ΠΊΠΈ pi Π±ΡƒΠ»Π° ΠΏΠΎΠ±ΡƒΠ΄ΠΎΠ²Π°Π½Π° CH (p1, p2, …, pi). Алгоритм ΠΏΠΎΠ²ΠΈΠ½Π΅Π½ ΠΏΡ–Π΄Ρ‚Ρ€ΠΈΠΌΡƒΠ²Π°Ρ‚ΠΈ дСякС прСдставлСння ΠΏΠΎΡ‚ΠΎΡ‡Π½ΠΎΡ— ΠΎΠΏΡƒΠΊΠ»ΠΎΡ— ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ Ρ‚Π° ΠΊΠΎΡ€Π΅ΠΊΡ‚ΡƒΠ²Π°Ρ‚ΠΈ ΠΉΠΎΠ³ΠΎ ΠΏΠΎ ΠΌΡ–Ρ€Ρ– надходТСння Ρ‚ΠΎΡ‡ΠΎΠΊ.

Π―ΠΊΡ‰ΠΎ Π½Π΅ Π±Ρ€Π°Ρ‚ΠΈ Π΄ΠΎ ΡƒΠ²Π°Π³ΠΈ часову ΠΎΡ†Ρ–Π½ΠΊΡƒ, Ρ‚ΠΎ ΠΌΠΎΠΆΠ½Π° Π·Π°ΠΏΡ€ΠΎΠΏΠΎΠ½ΡƒΠ²Π°Ρ‚ΠΈ наступний Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ:

1. Π’Π²ΠΎΠ΄ΠΈΡ‚ΠΈ Ρ‚ΠΎΡ‡ΠΊΠΈ ΠΏΠΎΠΊΠΈ Π½Π΅ Π±ΡƒΠ΄Π΅ Π·Π½Π°ΠΉΠ΄Π΅Π½ΠΎ Ρ‚Ρ€ΠΈ Π½Π΅ΠΊΠΎΠ»Ρ–Π½Π΅Π°Ρ€Π½Ρ– Ρ‚ΠΎΡ‡ΠΊΠΈ. Π‡Ρ… Ρ†Π΅Π½Ρ‚Ρ€ΠΎΡ—Π΄ Π±ΡƒΠ΄Π΅ Π²Π½ΡƒΡ‚Ρ€Ρ–ΡˆΠ½ΡŒΠΎΡŽ Ρ‚ΠΎΡ‡ΠΊΠΎΡŽ ΠΊΡ–Π½Ρ†Π΅Π²ΠΎΡ— ΠΎΠΏΡƒΠΊΠ»ΠΎΡ— ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ, Π° ΠΎΡ‚ΠΆΠ΅ ΠΏΡ–Π΄Ρ…ΠΎΠ΄ΠΈΡ‚ΡŒ Π² ΡΠΊΠΎΡΡ‚Ρ– ΠΏΠΎΡ‡Π°Ρ‚ΠΊΡƒ ΠΊΠΎΠΎΡ€Π΄ΠΈΠ½Π°Ρ‚, відносно якого Π²ΠΈΠ·Π½Π°Ρ‡Π°ΡŽΡ‚ΡŒΡΡ полярні ΠΊΡƒΡ‚ΠΈ Ρ‚ΠΎΡ‡ΠΎΠΊ ΠΏΡ€ΠΈ сортуванні.

2. ΠŸΡ–Π΄Ρ‚Ρ€ΠΈΠΌΡƒΠ²Π°Ρ‚ΠΈ Π·Π²’язаний список впорядкованих ΠΊΡ€Π°ΠΉΠ½Ρ–Ρ… Ρ‚ΠΎΡ‡ΠΎΠΊ. ΠŸΡ€ΠΈ Π½Π°Π΄Ρ…ΠΎΠ΄ΠΆΠ΅Π½Π½Ρ– Ρ‚ΠΎΡ‡ΠΊΠΈ pi Π²ΡΡ‚Π°Π²ΠΈΡ‚ΠΈ Ρ—Ρ— Ρƒ ΡΠΏΠΈΡΠΎΠΊ Π²Ρ–Π΄ΠΏΠΎΠ²Ρ–Π΄Π½ΠΎ Π΄ΠΎ Ρ—Ρ— полярного ΠΊΡƒΡ‚Π°, Π²ΠΈΡ‚Ρ€Π°Ρ‚ΠΈΠ²ΡˆΠΈ час O (i).

3. Π’ΠΈΠΊΠΎΠ½Π°Ρ‚ΠΈ пСрСгляд Π·Π²’язаного списку ΠΊΡ€Π°ΠΉΠ½Ρ–Ρ… Ρ‚ΠΎΡ‡ΠΎΠΊΠΌΠ΅Ρ‚ΠΎΠ΄ΠΎΠΌ Π“Ρ€Π΅Ρ…Π΅ΠΌΠ°. ΠœΠΎΠΆΠ»ΠΈΠ²Ρ– Ρ‚Ρ€ΠΈ Π²Π°Ρ€Ρ–Π°Π½Ρ‚ΠΈ Ρ†ΡŒΠΎΠ³ΠΎ ΠΊΡ€ΠΎΠΊΡƒ:

Π°) Ρ‚ΠΎΡ‡ΠΊΠ° pi Ρ” ΠΊΡ€Π°ΠΉΠ½ΡŒΠΎΡŽ Ρ– Ρ—Ρ— Π²ΠΊΠ»ΡŽΡ‡Π΅Π½Π½Ρ Π²ΠΈΠΊΠ»ΠΈΠΊΠ°Ρ” видалСння дСяких Ρ–Π½ΡˆΠΈΡ… Ρ‚ΠΎΡ‡ΠΎΠΊ;

Π±) Ρ‚ΠΎΡ‡ΠΊΠ° pi Ρ” ΠΊΡ€Π°ΠΉΠ½ΡŒΠΎΡŽ, Π°Π»Π΅ Ρ—Ρ— Π²ΠΊΠ»ΡŽΡ‡Π΅Π½Π½Ρ Π½Π΅ Π²ΠΈΠΊΠ»ΠΈΠΊΠ°Ρ” видалСння Ρ–Π½ΡˆΠΈΡ… Ρ‚ΠΎΡ‡ΠΎΠΊ;

Π²) Ρ‚ΠΎΡ‡ΠΊΠ° pi Ρ” Π²Π½ΡƒΡ‚Ρ€Ρ–ΡˆΠ½ΡŒΠΎΡŽ Ρ– Ρ‚ΠΎΠΌΡƒ Π²ΠΎΠ½Π° Π²ΠΈΠ΄Π°Π»ΡΡ”Ρ‚ΡŒΡΡ.

Π’Π΅ΠΎΡ€Π΅ΠΌΠ°. Π”ΠΎΠ²Ρ–Π»ΡŒΠ½ΠΈΠΉ Π²Ρ–Π΄ΠΊΡ€ΠΈΡ‚ΠΈΠΉ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌ ΠΏΠΎΠ±ΡƒΠ΄ΠΎΠ²ΠΈ ΠΎΠΏΡƒΠΊΠ»ΠΎΡ— ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠΈ Π² Π½Π°ΠΉΠ³Ρ–Ρ€ΡˆΠΎΠΌΡƒ Π²ΠΈΠΏΠ°Π΄ΠΊΡƒ ΠΏΠΎΠ²ΠΈΠ½Π΅Π½ Π²ΠΈΡ‚Ρ€Π°Ρ‡ΡƒΠ²Π°Ρ‚ΠΈ Π½Π° ΠΎΠ±Ρ€ΠΎΠ±ΠΊΡƒ ΠΌΡ–ΠΆ надходТСнням послідовних Π΅Π»Π΅ΠΌΠ΅Π½Ρ‚Ρ–Π² Π΄Π°Π½ΠΈΡ… час O (log N).

Π•Ρ„Π΅ΠΊΡ‚ΠΈΠ²Π½Ρ–ΡΡ‚ΡŒ Π²Ρ–Π΄ΠΊΡ€ΠΈΡ‚ΠΎΠ³ΠΎ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡƒ полягає Ρƒ ΠΌΠΎΠΆΠ»ΠΈΠ²ΠΎΡΡ‚Ρ– швидко Π±ΡƒΠ΄ΡƒΠ²Π°Ρ‚ΠΈ Π΄Π²Ρ– ΠΎΠΏΠΎΡ€Π½Ρ– прямі Π΄ΠΎ ΠΎΠΏΡƒΠΊΠ»ΠΎΠ³ΠΎ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡƒΡ‚Π½ΠΈΠΊΠ°, Ρ‰ΠΎ ΠΏΡ€ΠΎΡ…ΠΎΠ΄ΡΡ‚ΡŒ Ρ‡Π΅Ρ€Π΅Π· Π·Π°Π΄Π°Π½Ρƒ Ρ‚ΠΎΡ‡ΠΊΡƒ. ΠŸΠΎΠ·Π½Π°Ρ‡ΠΈΠΌΠΎ Ρ‡Π΅Ρ€Π΅Π· Ci-1 ΠΎΠΏΡƒΠΊΠ»Ρƒ ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΡƒ ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ {p1, p2, …, pi-1}. НСобхідно ΠΏΠΎΠ±ΡƒΠ΄ΡƒΠ²Π°Ρ‚ΠΈ Π· Ρ‚ΠΎΡ‡ΠΊΠΈ pi ΠΎΠΏΠΎΡ€Π½Ρ– прямі Π΄ΠΎ Ci-1, якщо Π²ΠΎΠ½ΠΈ Ρ–ΡΠ½ΡƒΡŽΡ‚ΡŒ (ΠΊΠΎΠ»ΠΈ pi Ρ” Π·ΠΎΠ²Π½Ρ–ΡˆΠ½ΡŒΠΎΡŽ для Ci-1). Π‘ΡƒΠ΄Π΅ΠΌΠΎ Π½Π°Π·ΠΈΠ²Π°Ρ‚ΠΈ ΠΎΠΏΠΎΡ€Π½Ρƒ пряму Π»Ρ–Π²ΠΎΡŽ Ρ‡ΠΈ ΠΏΡ€Π°Π²ΠΎΡŽ Π² Π·Π°Π»Π΅ΠΆΠ½ΠΎΡΡ‚Ρ– Π²Ρ–Π΄ Ρ‚ΠΎΠ³ΠΎ, ΠΏΠΎ ΡΠΊΡƒ сторону Π²ΠΎΠ½Π° Π·Π½Π°Ρ…ΠΎΠ΄ΠΈΡ‚ΡŒΡΡ якщо дивитися Π· Ρ‚ΠΎΡ‡ΠΊΠΈ pi Π½Π° Ci-1.

p.

.

p.

.

v.

.

v.

.

v.

.

.

ΠΎΠΏΡƒΠΊΠ»Π°.

.

ΠΎΠΏΠΎΡ€Π½Π°.

.

Π²ΠΎΠ³Π½ΡƒΡ‚Π°.

.

.

ΠžΠ·Π½Π°Ρ‡Π΅Π½Π½Ρ. Π’Π΅Ρ€ΡˆΠΈΠ½Π° v Π½Π°Π·ΠΈΠ²Π°Ρ”Ρ‚ΡŒΡΡ Π²ΠΎΠ³Π½ΡƒΡ‚ΠΎΡŽ, якщо Π²Ρ–Π΄Ρ€Ρ–Π·ΠΎΠΊ pv ΠΏΠ΅Ρ€Π΅Ρ‚ΠΈΠ½Π°Ρ” Π²Π½ΡƒΡ‚Ρ€Ρ–ΡˆΠ½ΡŽ частину ΠΌΠ½ΠΎΠ³ΠΎΠΊΡƒΡ‚Π½ΠΈΠΊΠ°. Π―ΠΊΡ‰ΠΎ Π΄Π²Ρ– суміТні Π· v Π²Π΅Ρ€ΡˆΠΈΠ½ΠΈ Π»Π΅ΠΆΠ°Ρ‚ΡŒ ΠΏΠΎ ΠΎΠ΄Π½Ρƒ сторону Π²Ρ–Π΄ прямої, Ρ‰ΠΎ ΠΏΡ€ΠΎΡ…ΠΎΠ΄ΠΈΡ‚ΡŒ Ρ‡Π΅Ρ€Π΅Π· p Ρ‚Π° v, Ρ‚ΠΎ Π²Π΅Ρ€ΡˆΠΈΠ½Π° Π½Π°Π·ΠΈΠ²Π°Ρ”Ρ‚ΡŒΡΡ ΠΎΠΏΠΎΡ€Π½ΠΎΡŽ. Π†Π½Π°ΠΊΡˆΠ΅ Π²Π΅Ρ€ΡˆΠΈΠ½Π° Π½Π°Π·ΠΈΠ²Π°Ρ”Ρ‚ΡŒΡΡ ΠΎΠΏΡƒΠΊΠ»ΠΎΡŽ.

Π―ΠΊΡ‰ΠΎ v — ΠΎΠΏΠΎΡ€Π½Π° Π²Π΅Ρ€ΡˆΠΈΠ½Π°, Ρ‚ΠΎ Ρ€ΠΎΠ·Π²’язок Π·Π°Π΄Π°Ρ‡Ρ– Π·Π°Π²Π΅Ρ€ΡˆΡƒΡ”Ρ‚ΡŒΡΡ. Π†Π½Π°ΠΊΡˆΠ΅ Π±ΡƒΠ΄ΡƒΡ”ΠΌΠΎ ΠΎΠΏΠΎΡ€Π½Ρ– прямі. Для знаходТСння, Π½Π°ΠΏΡ€ΠΈΠΊΠ»Π°Π΄, Π»Ρ–Π²ΠΎΡ— ΠΎΠΏΠΎΡ€Π½ΠΎΡ— прямої, Π½Π΅ΠΎΠ±Ρ…Ρ–Π΄Π½ΠΎ рухатися ΠΏΠΎ Π²Π΅Ρ€ΡˆΠΈΠ½Π°ΠΌ ΠΌΠ½ΠΎΠ³ΠΎΠΊΡƒΡ‚Π½ΠΈΠΊΠ° ΠΏΡ€ΠΎΡ‚ΠΈ Ρ‡ΠΈ Π·Π° Π³ΠΎΠ΄ΠΈΠ½Π½ΠΈΠΊΠΎΠ²ΠΎΡŽ ΡΡ‚Ρ€Ρ–Π»ΠΊΠΎΡŽ (Π² Π·Π°Π»Π΅ΠΆΠ½ΠΎΡΡ‚Ρ– Π²Ρ–Π΄ опуклості Ρ‡ΠΈ Π²ΠΎΠ³Π½ΡƒΡ‚ості Π²Π΅Ρ€ΡˆΠΈΠ½ΠΈ v). Π’Π°ΠΊΠΈΠΌ Ρ‡ΠΈΠ½ΠΎΠΌ Π²ΠΈΠ·Π½Π°Ρ‡Π°ΡŽΡ‚ΡŒΡΡ Π΄Π²Ρ– ΠΎΠΏΠΎΡ€Π½Ρ– Ρ‚ΠΎΡ‡ΠΊΠΈ.

Π’Π΅ΠΎΡ€Π΅ΠΌΠ°. ΠžΠΏΡƒΠΊΠ»Π° ΠΎΠ±ΠΎΠ»ΠΎΠ½ΠΊΠ° ΠΌΠ½ΠΎΠΆΠΈΠ½ΠΈ Π· N Ρ‚ΠΎΡ‡ΠΎΠΊ Π½Π° ΠΏΠ»ΠΎΡ‰ΠΈΠ½Ρ– ΠΌΠΎΠΆΠ΅ Π±ΡƒΡ‚ΠΈ ΠΏΠΎΠ±ΡƒΠ΄ΠΎΠ²Π°Π½Π° Π·Π° Π΄ΠΎΠΏΠΎΠΌΠΎΠ³ΠΎΡŽ Π²Ρ–Π΄ΠΊΡ€ΠΈΡ‚ΠΎΠ³ΠΎ Π°Π»Π³ΠΎΡ€ΠΈΡ‚ΠΌΡƒ Π·Π° Ρ‡Π°Ρ O (N * log N) Π· Ρ‡Π°ΡΠΎΠΌ ΠΊΠΎΡ€Π΅ΠΊΡ†Ρ–Ρ— O (log N).

ΠŸΠΎΠΊΠ°Π·Π°Ρ‚ΠΈ вСсь тСкст
Π—Π°ΠΏΠΎΠ²Π½ΠΈΡ‚ΠΈ Ρ„ΠΎΡ€ΠΌΡƒ ΠΏΠΎΡ‚ΠΎΡ‡Π½ΠΎΡŽ Ρ€ΠΎΠ±ΠΎΡ‚ΠΎΡŽ