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

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

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

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

Тип

Через pntn обозначим бинарное отношение на Xintn х Yintn, определяемое следующим соотношением

Тип

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

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

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

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

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

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >