Міра та периметр об"єднання прямокутників (реферат)

Реферат на тему:

Міра та периметр об'єднання прямокутників

Задача. Міра об'єднання інтервалів. Дано N інтервалів [a1, b1], [a2, b2], …, [aN, bN] на дійсній прямій. Необхідно знайти їх міру об'єднання.

Відсортуємо абсциси a1, b1, a2, b2, …, aN, bN у масиві X[1: 2N], при чому права кінцева точка розташовується у масиві після лівої точки з такою ж абсцисою: якщо ai розташовано в X[h], bj — в X[k] і ai = bj, то h < k. Далі за лінійний час преглядається масив і обчислюється міра об'єднання інтервалів.

Приклад. Нехай дано 5 інтервалів: {3,7},{2,5},{5,12}, {14,20},{5,13}.

Вони покривають інтервали від 2 до 13 та від 14 до 20, отже їх міра дорівнює 11 + 6 = 17.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20.

Міра об'єднання інтервалів на осі.

X[0] 1];

m /* міра об'єднання */.

C /* кількість інтервалів що перетинаються */.

for i to 2*N do.

begin.

if (C 0) then m + X[i] - X[i — 1];

if (X[i] - ліва кінцева точка) then C + 1;

else C — 1;

end;

Задача. eблизькість. Дано N + 1 дійсне число x1, x2, …, xN та e > 0. Чи знаходяться деякі два числа xi та xj на відстані, меншій за e одне від іншого.

Теорема. Задача eблизькість лінійно зводиться до задачі міра об'єднання інтервалів.

Доведення. Побудуємо інтервали [xi, xi + e] для i = 1, 2, …, N, які будуть входом для процедури міра об'єднання інтервалів. Результатом її роботи буде значення m (міра). Жодні два числа з множини {x1, x2, …, xN} не будуть знаходитися на відстані, меншій за e одне від іншого тоді і тільки тоді, коли m = N * e.