Е-расширение задач о доминировании и интервального поиска

Пусть е — действительное число.

Через Pd_om обозначим бинарное отношение на Х^т ^х определяемое следующим соотношением.

назовем типом ерасширения задач о доминировании.

Тип Через p_ntn обозначим бинарное отношение на Xi_ntn х Yi_ntn, определяемое следующим соотношением.

Тип

назовем типом ?-расширения интервального поиска.

Так как^{-расширение} задач о доминировании и интервального поиска приводит лишь к вымыванию «малых» запросов, то понятно, что для этих задач результаты, описанные в теоремах 39 и 50, полностью сохраняются. Причем ИГ, на которых достигаются эти оценки, строятся по аналогии с тем, как это делалось в теореме 54, т. е. задачи о близости решаются не для самих библиотек, а для библиотек сдвинутых на е. Тем самым, справедливо следующее утверждение.

Утверждение 4. Канонический эффект устойчив по отношению к е-расширению запроса для задач о доминировании и интервального поиска.

Суммируя результаты утверждений 1−4, можем сформулировать следующее интегральное утверждение.

Утверждение 5. Канонический эффект устойчив по отношению к ?-расширению запроса, но при вариации базового множества или объема ИГ мы уходим от канонического эффекта.