Задачи поиска на декартовых произведениях линейно-упорядоченных множеств данных (задача о доминировании)

Задачу о доминировании так же как и задачу интервального поиска, можно отнести к интенсивно развивающемуся сейчас направлению, называемому вычислительная геометрия [64, 86, 193). Эта область, посвященная исследованию сложности алгоритмов решения геометрических (в широком понимании этого слова) задач, имеет очень широкий круг применений. Это робототехника, распознавание образов, проектирование СБИС, базы данных, машинная графика, раскрой материалов и т. д. Популярность вычислительной геометрии непосредственно связана с визуализацией вычислений и, как следствие, с удобством геометрической интерпретации необязательно геометрических объектов.

Примером многомерной задачи о доминировании является случай, когда отдел кадров предприятия желает получить список всех сотрудников в возрасте от 30 лет, получающих более 10 000 рублей в год. Различные алгоритмы решения задачи о доминировании, имеющие различные соотношения времени поиска в худшем случае и размера необходимой памяти можно найти в [64, 118) и [86, с. 54−57,445−451].

Многомерная задача о доминировании состоит в поиске в конечном подмножестве n-мерного пространства всех тех точек, которые нс больше по каждой из компонент, чем запрос, являющийся в данном случае точкой n-мерного пространства, где п ^ 1. Опишем тип задач поиска, который соответствует n-мерной задаче о доминировании.

Пусть Ydom = (0,1]^п — множество записей и Xdom = [ 0,1)^п — множество запросов. Пусть на множестве Xdom задано вероятностное пространство (Xj_om, a, Р), где Р задается функцией плотности вероятности р (х).

Отношение поиска Pdom определено на Xdom ^х Ydom и задается следующим соотношением:

Тогда тип Sdom = {хdom, Ydom, Pdom, V, P) назовем типом задачи о доминировании.